package io.tree

import io.utils.runTests

// https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/530/week-3/3303/
class MinPathSum {

  fun execute(grid: Array<IntArray>): Int {
    val height = grid.size
    val width: Int = grid.first().size
    for (row in 0 until height) {
      for (col in 0 until width) {
        grid[row][col] = if (row == 0 && col == 0) grid[row][col]
        else if (row == 0 && col != 0) grid[row][col] + grid[row][col - 1]
        else if (col == 0 && row != 0) grid[row][col] + grid[row - 1][col]
        else grid[row][col] + minOf(grid[row - 1][col], grid[row][col - 1])
      }
    }
    return grid[height - 1][width - 1]
  }

}

fun main() {
  runTests(listOf(
      arrayOf(intArrayOf(1, 3, 1), intArrayOf(1, 5, 1), intArrayOf(4, 2, 1)) to 7,
      arrayOf(
          intArrayOf(3, 8, 6, 0, 5, 9, 9, 6, 3, 4, 0, 5, 7, 3, 9, 3),
          intArrayOf(0, 9, 2, 5, 5, 4, 9, 1, 4, 6, 9, 5, 6, 7, 3, 2),
          intArrayOf(8, 2, 2, 3, 3, 3, 1, 6, 9, 1, 1, 6, 6, 2, 1, 9),
          intArrayOf(1, 3, 6, 9, 9, 5, 0, 3, 4, 9, 1, 0, 9, 6, 2, 7),
          intArrayOf(8, 6, 2, 2, 1, 3, 0, 0, 7, 2, 7, 5, 4, 8, 4, 8),
          intArrayOf(4, 1, 9, 5, 8, 9, 9, 2, 0, 2, 5, 1, 8, 7, 0, 9),
          intArrayOf(6, 2, 1, 7, 8, 1, 8, 5, 5, 7, 0, 2, 5, 7, 2, 1),
          intArrayOf(8, 1, 7, 6, 2, 8, 1, 2, 2, 6, 4, 0, 5, 4, 1, 3),
          intArrayOf(9, 2, 1, 7, 6, 1, 4, 3, 8, 6, 5, 5, 3, 9, 7, 3),
          intArrayOf(0, 6, 0, 2, 4, 3, 7, 6, 1, 3, 8, 6, 9, 0, 0, 8),
          intArrayOf(4, 3, 7, 2, 4, 3, 6, 4, 0, 3, 9, 5, 3, 6, 9, 3),
          intArrayOf(2, 1, 8, 8, 4, 5, 6, 5, 8, 7, 3, 7, 7, 5, 8, 3),
          intArrayOf(0, 7, 6, 6, 1, 2, 0, 3, 5, 0, 8, 0, 8, 7, 4, 3),
          intArrayOf(0, 4, 3, 4, 9, 0, 1, 9, 7, 7, 8, 6, 4, 6, 9, 5),
          intArrayOf(6, 5, 1, 9, 9, 2, 2, 7, 4, 2, 7, 2, 2, 3, 7, 2),
          intArrayOf(7, 1, 9, 6, 1, 2, 7, 0, 9, 6, 6, 4, 4, 5, 1, 0),
          intArrayOf(3, 4, 9, 2, 8, 3, 1, 2, 6, 9, 7, 0, 2, 4, 2, 0),
          intArrayOf(5, 1, 8, 8, 4, 6, 8, 5, 2, 4, 1, 6, 2, 2, 9, 7)
      ) to 83,
      arrayOf(
          intArrayOf(1, 4, 8, 6, 2, 2, 1, 7),
          intArrayOf(4, 7, 3, 1, 4, 5, 5, 1),
          intArrayOf(8, 8, 2, 1, 1, 8, 0, 1),
          intArrayOf(8, 9, 2, 9, 8, 0, 8, 9),
          intArrayOf(5, 7, 5, 7, 1, 8, 5, 5),
          intArrayOf(7, 0, 9, 4, 5, 6, 5, 6),
          intArrayOf(4, 9, 9, 7, 9, 1, 9, 0)
      ) to 47
  )) { (input, value) -> value to MinPathSum().execute(input) }
}