Project Euler : Using an efficient algorithm find the maximal sum in the triangle?

Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

Solution (in Ruby)

To attack this problem, we should think in the reverse order as exploring all the possible routes would take 20 billion years to solve this problem!! We should start at the bottom but before level. For each number in that level, replace with the sum of that number and the maximum of the below two numbers. Do this for each level and bingo! we will arrive at the solution. So easy now isnt it? :) Thats 'after' you know it. Ruby code is presented below. There is another problem (Problem 18) (the minor input version) which also is the same one like the one above.

input = ''

f = File.new("/triangle.txt","r")
while (line = f.gets)
  input += line
end

class Row
  attr_accessor :index, :data
end

index = 0
triangle =  input.lines.map{|each_line| r = Row.new; r.index = index; r.data=[]; index+=1; sub_index = 0
  each_line.split.map{|n| r.data[sub_index] = n.to_i; sub_index+=1}; r}

(triangle.size - 2).downto(0) do |n|
  0.upto(triangle[n].data.size-1) do |sub_index|
    triangle[n].data[sub_index] += [ triangle[n+1].data[sub_index+1] , triangle[n+1].data[sub_index] ].max
  end
end

puts "The maximum value is #{triangle[0].data}"

Hover here to see the solution

Cheers!!
Bragaadeesh