Project Euler : Find the minimal path sum from the left column to the right column.

Problem 82
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.

Solution(in Ruby)

This problem has to be attacked in the reverse order ie starting from the right to left. Lets take the last but before column. For each cell in that column, find the minimum possible sum for that cell. To find the minimum possible sum, you will have to find all the 'L' paths explored, their sum has be calculated and stored and the minimum sum has to be stored in that cell. After traversing that entire column, replace that particular column value with the minimal sum. Repeat this process for the immediate left column until you exhaust all the columns reaching the left most column. The minimal value of the leftmost column is the minimal sum which is exactly what we look for.

require 'matrix'

input = ''
file = File.new("/matrix.txt","r")
while (line = file.gets) 
  input += line
end

class Cell
  attr_accessor :min_sum, :value
end

x = Matrix.rows(input.lines.map{|each_line| each_line.split(/,/).map{
      |n|
      c = Cell.new
      c.min_sum = c.value = n.to_i
      c
    }})

MAX = x.row_size

(MAX-2).downto(0) do |column|
  0.upto(MAX-1) do |row|
    val_array = []
    aggregate = x[row,column].value
    val_array << aggregate + x[row,column+1].value
    (row+1).upto(MAX-1) do |down_traverse|
      aggregate += x[down_traverse,column].value
      val_array << aggregate + x[down_traverse,column+1].value
    end
    aggregate = x[row,column].value
    (row-1).downto(0) do |up_traverse|
      aggregate += x[up_traverse,column].value
      val_array << aggregate + x[up_traverse,column+1].value
    end
    x[row,column].min_sum = val_array.min
  end
  0.upto(MAX-1) do |each_row|
    x[each_row,column].value = x[each_row,column].min_sum
  end
end
val_array = []
0.upto(MAX-1) do |val|
  val_array << x[val,0].value
end

puts "The minimum sum is #{val_array.min}"

Hover here to see the solution

Cheers!!
Bragaadeesh.