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 5
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.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

p67()->
	File=binary_to_list(element(2,file:read_file("triangle.txt"))),
	Lines=string:tokens(File,"\r\n"),
	Triangle=lists:map(fun(L)->
				lists:map(fun list_to_integer/1,string:tokens(L," ")) end,Lines),
	p67(lists:reverse(Triangle)).
p67([[A]])->io:format("~w~n",[A]);
p67([Base,Next|Others])->
	p67([p67(Base,Next,[])|Others]).
p67(_,[],New)->lists:reverse(New);
p67([BigItem1,BigItem2|BigOthers],[SmallItem|SmallOthers],New)->
	p67([BigItem2|BigOthers],SmallOthers,[SmallItem+lists:max([BigItem1,BigItem2])|New]).

def p67
  p=File.read("triangle.txt").split("\n").map{|l|l.split(" ").map{|m|m.to_i}}
  while(p.length>1)
    last=p.pop
    (0...(p[-1].length)).each do |i|
      p[-1][i]+=last[i..(i+1)].max
    end
  end
  puts p[0][0]
end