Skip to content

Instantly share code, notes, and snippets.

@alex-rogachev

alex-rogachev/solution.rb

Last active Feb 28, 2019
Embed
What would you like to do?
Minimum grid path solution
# Given a m x n grid filled with non-negative numbers, find a path from top left
# to bottom right which minimizes the sum of all numbers along its path.
def minimum_path_sum(grid)
m, n = detect_grid_size(grid)
validate_grid!(grid, n)
# Prepare table that contains path cost
path_cost = Array.new(m) { Array.new(n) { 0 } }
# Initialize top left cell
path_cost[0][0] = grid[0][0]
# Initialize first column
for i in 1..(m - 1)
path_cost[i][0] = path_cost[i - 1][0] + grid[i][0]
end
# Initialize first row
for j in 1..(n - 1)
path_cost[0][j] = path_cost[0][j - 1] + grid[0][j]
end
# Fill the rest of path_cost table
for i in 1..(m - 1)
for j in 1..(n - 1)
path_cost[i][j] = grid[i][j] + [path_cost[i - 1][j - 1], path_cost[i - 1][j], path_cost[i][j - 1]].min
end
end
path_cost[m - 1][n - 1]
end
# Returns size of m x n grid
def detect_grid_size(grid)
[grid.size, grid.first.size]
end
def validate_grid!(grid, n)
grid.each do |row|
raise ArgumentError, 'Grid has rows of different sizes!' unless row.size == n
row.each do |value|
raise ArgumentError, 'Grid values shoud be Integer!' unless value.is_a? Integer
raise ArgumentError, 'Grid values should be positive!' unless value.positive?
end
end
end
def assertEqual(actual, expected)
raise "#{actual} != #{expected}" if actual != expected
end
# Results check:
# 1 1 1
# 1 1 1
# 1 1 1
grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
assertEqual(minimum_path_sum(grid), 3)
# 1 2 1
# 1 1 2
# 2 1 1
grid = [[1, 2, 1], [1, 1, 2], [2, 1, 1]]
assertEqual(minimum_path_sum(grid), 3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.