Starting from the top of a pyramid of numbers like this, you can walk down going one step on the right or on the left, until you reach the bottom row:

                          55
                        94 48
                       95 30 96
                     77 71 26 67

One of such walks is 55 - 94 - 30 - 26.
You can compute the total of the numbers you have seen in such walk,
in this case it's 205.

Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it's 321.



Task

Find the maximum total in the triangle below:

                          55
                        94 48
                       95 30 96
                     77 71 26 67
                    97 13 76 38 45
                  07 36 79 16 37 68
                 48 07 09 18 70 26 06
               18 72 79 46 59 79 29 90
              20 76 87 11 32 07 07 49 18
            27 83 58 35 71 11 25 57 29 85
           14 64 36 96 27 11 58 56 92 18 55
         02 90 03 60 48 49 41 46 33 36 47 23
        92 50 48 02 36 59 42 79 72 20 82 77 42
      56 78 38 80 39 75 02 71 66 66 01 03 55 72
     44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93

Such numbers can be included in the solution code, or read from a "triangle.txt" file.

This task is derived from the Euler Problem #18.




 
\ Triangle representation; words created by this defining word return the address of element
\ specified by its row number and position within that row, both indexed from 0.
: TRIANGLE ( "name" -- |DOES: row pos -- addr )
   CREATE DOES> ROT DUP 1+ * 2/ CELLS +  SWAP CELLS +
;
 
18 CONSTANT #ROWS   \ total number of rows in triangle
TRIANGLE triang
                                             55 ,
                                           94 , 48 ,
                                        95 , 30 , 96 ,
                                      77 , 71 , 26 , 67 ,
                                   97 , 13 , 76 , 38 , 45 ,
                                  7 , 36 , 79 , 16 , 37 , 68 ,
                              48 ,  7 ,  9 , 18 , 70 , 26 ,  6 ,
                            18 , 72 , 79 , 46 , 59 , 79 , 29 , 90 ,
                         20 , 76 , 87 , 11 , 32 ,  7 ,  7 , 49 , 18 ,
                       27 , 83 , 58 , 35 , 71 , 11 , 25 , 57 , 29 , 85 ,
                    14 , 64 , 36 , 96 , 27 , 11 , 58 , 56 , 92 , 18 , 55 ,
                   2 , 90 ,  3 , 60 , 48 , 49 , 41 , 46 , 33 , 36 , 47 , 23 ,
               92 , 50 , 48 ,  2 , 36 , 59 , 42 , 79 , 72 , 20 , 82 , 77 , 42 ,
             56 , 78 , 38 , 80 , 39 , 75 ,  2 , 71 , 66 , 66 ,  1 ,  3 , 55 , 72 ,
          44 , 25 , 67 , 84 , 71 , 67 , 11 , 61 , 40 , 57 , 58 , 89 , 40 , 56 , 36 ,
        85 , 32 , 25 , 85 , 57 , 48 , 84 , 35 , 47 , 62 , 17 ,  1 ,  1 , 99 , 89 , 52 ,
      6 , 71 , 28 , 75 , 94 , 48 , 37 , 10 , 23 , 51 ,  6 , 48 , 53 , 18 , 74 , 98 , 15 ,
   27 ,  2 , 92 , 23 ,  8 , 71 , 76 , 84 , 15 , 52 , 92 , 63 , 81 , 10 , 44 , 10 , 69 , 93 ,
 
\ Starting from the row above the bottom row and ending on the top, for every item in row
\ find the bigger number from the two neighbours underneath and add it to this item. At
\ the end, the result will be returned from the top element of the triangle.
: MAX-SUM ( -- n )
   0 #ROWS 2 - DO
      I 1+ 0 DO
         J 1+ I triang @  J 1+ I 1+ triang @
         MAX  J I triang  +!
      LOOP
   -1 +LOOP
   0 0 triang @
;
 
MAX-SUM .