/* 

  Euler #18 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 of the triangle below:

   75
   95 64
   17 47 82
   18 35 87 10
   20 04 82 47 65
   19 01 23 75 03 34
   88 02 77 73 07 63 67
   99 65 04 28 06 16 70 92
   41 41 26 56 83 40 80 70 33
   41 48 72 33 47 32 37 16 94 29
   53 71 44 65 25 43 91 52 97 51 14
   70 11 33 28 77 73 17 78 39 68 17 57
   91 71 52 38 17 14 91 43 58 50 27 29 48
   63 66 04 68 89 53 67 30 73 16 69 87 40 31
   04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

  NOTE: As there are only 16384 routes, it is possible to solve this problem 
  by trying every route. However, Problem 67, is the same challenge with a 
  triangle containing one-hundred rows; it cannot be solved by brute force, 
  and requires a clever method! ;o)
  """


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

*/


main => time(go).

go => euler18c.

euler18 =>
  euler18c.

p18(Triangle) => 
Triangle  = 
[[75],
 [95,64],
 [17,47,82],
 [18,35,87,10],
 [20, 4,82,47,65],
 [19, 1,23,75, 3,34],
 [88, 2,77,73, 7,63,67],
 [99,65, 4,28, 6,16,70,92],
 [41,41,26,56,83,40,80,70,33],
 [41,48,72,33,47,32,37,16,94,29],
 [53,71,44,65,25,43,91,52,97,51,14],
 [70,11,33,28,77,73,17,78,39,68,17,57],
 [91,71,52,38,17,14,91,43,58,50,27,29,48],
 [63,66, 4,68,89,53,67,30,73,16,69,87,40,31],
 [ 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23]].


euler18a => 
  p18(Tri),
  M = new_map(),
  M.put(max_val,0),
  pp(1,1, Tri[1,1], Tri, M),
  writeln(max_val=M.get(max_val)).

pp(Row, Column, Sum, Tri, M) =>
  if Sum > M.get(max_val) then
     M.put(max_val,Sum)
  end,
  Row := Row + 1,
  if Row <= Tri.length then
    foreach(I in 0..1) 
       pp(Row,Column+I, Sum+Tri[Row,Column+I], Tri, M)
     end
  end.


euler18b => 
  p18(Tri),
  get_global_map().put(max_val,0),
  pp2(1,1, Tri[1,1], Tri),
  writeln(max_val=get_global_map().get(max_val)).



pp2(Row, Column, Sum, Tri) =>
  G = get_global_map(),
  if Sum > G.get(max_val) then
     G.put(max_val,Sum)
  end,
  Row := Row + 1,
  if Row <= Tri.length then
    foreach(I in 0..1) 
      pp2(Row,Column+I, Sum+Tri[Row,Column+I], Tri)
    end
  end.



% Neng-Fa's approach:
% This is slightly faster than euler18a and euler18b
p18c(Triangle) => 
Triangle  = 
{{75},
{95,64},
{17,47,82},
{18,35,87,10},
{20,4,82,47,65},
{19,1,23,75,3,34},
{88,2,77,73,7,63,67},
{99,65,4,28,6,16,70,92},
{41,41,26,56,83,40,80,70,33},
{41,48,72,33,47,32,37,16,94,29},
{53,71,44,65,25,43,91,52,97,51,14},
{70,11,33,28,77,73,17,78,39,68,17,57},
{91,71,52,38,17,14,91,43,58,50,27,29,48},
{63,66,4,68,89,53,67,30,73,16,69,87,40,31},
{ 4,62,98,27,23,9,70,98,73,93,38,53,60,4,23}}.

euler18c =>
  p18c(Tri),
  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].