/* 

  Euler #67 in Picat.

  """
  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 
  [ http://projecteuler.net/project/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^99 altogether! 
  If you could check one trillion (10^12) routes every second it would take 
  over twenty billion years to check them all. There is an efficient algorithm 
  to solve it. ;o)
  """


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.

main => go.

go => euler67.

% from euler18
euler67 =>
  Tri = [ [I.to_integer() : I in Line.split()] :  Line in read_file_lines("euler67_triangle.txt")],
  pp(1,1,Tri,Sum),
  writeln(max_val=Sum).

table (+,+,+,max)  
pp(Row,_Column,Tri,Sum),Row>Tri.length => Sum=0.
pp(Row,Column,Tri,Sum) ?=> 
  pp(Row+1,Column,Tri,Sum1),
  Sum = Sum1+Tri[Row,Column].
pp(Row,Column,Tri,Sum) => 
  pp(Row+1,Column+1,Tri,Sum1),
  Sum = Sum1+Tri[Row,Column].