Talk:Maximum triangle path sum

numbers in the triangle

Just a curiosity, where those numbers in the given triangle chosen at random? -- Gerard Schildberger (talk) 09:02, 25 February 2014 (UTC)

efficiency of the REXX solution

To find the efficiency of the REXX solution, a system of defining the lines (rows) of the triangle was chosen such that each row could be easily be generated, and more importantly, have a verifiable answer (for some even largish number of rows).

The algorithm used was to start (the left end) with unity, and increase each column number by one, so that the 53^rd number on row 53 (and every other higher row) 53. Verifications of the maximum triangle path sum (for some triangles) is easily seen by the results (below).

A triangle of nine rows looks like:

             1
            1 2
           1 2 3
          1 2 3 4
         1 2 3 4 5
        1 2 3 4 5 6
       1 2 3 4 5 6 7
      1 2 3 4 5 6 7 8
     1 2 3 4 5 6 7 8 9

The REXX program is: <lang rexx>/*REXX program finds the max sum of a "column" of numbers in a triangle.*/ parse arg L . /*get number of lines in triangle*/ if L== then L=100 /*Not given? Then use the default*/ @.=

        do r=1  for L;     q=0        /*construct lines of the triangle*/
          do c=1  for r;   q=q+1      /*leftmost number is always unity*/
          @.r=@.r q                   /*append number to triangle line.*/
          end   /*c*/                 /*each line is:  1 2 3 4 5 6 ··· */
        end     /*r*/

.=0

        do r=1  while  @.r\==       /*build a version of the triangle*/
            do k=1  for words(@.r)    /*build a row, number by number. */
            #.r.k=word(@.r,k)         /*assign a number to an array num*/
            end   /*k*/
        end       /*r*/

        do r=L  by -1 to 2;    p=r-1  /*traipse through triangle rows. */
            do k=1  for p;     kn=k+1 /*re-calculate the previous row. */
            #.p.k=max(#.r.k,#.r.kn)+#.p.k   /*maybe replace the prev #.*/
            end   /*k*/
        end       /*r*/

say 'The maximum path sum:' right(#.1.1,digits()), /*display top row # */

   " for "    L    ' rows.'                       /* and the # of rows.*/ 
                                      /*stick a fork in it, we're done.*/</lang>

output for various runs are (multiple runs have their output consolidated):

The maximum path sum:       5050  for  100  rows.
The maximum path sum:      20100  for  200  rows.
The maximum path sum:      45150  for  300  rows.
The maximum path sum:      80200  for  400  rows.
The maximum path sum:     125250  for  500  rows.
The maximum path sum:     180300  for  600  rows.
The maximum path sum:     245350  for  700  rows.
The maximum path sum:     320400  for  800  rows.
The maximum path sum:     405450  for  900  rows.
The maximum path sum:     500500  for  1000  rows.
The maximum path sum:    2001000  for  2000  rows.
The maximum path sum:    8002000  for  4000  rows.
The maximum path sum:   50005000  for  10000  rows.