Maximum triangle path sum

Maximum triangle path sum
You are encouraged to solve this task according to the task description, using any language you may know.

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.

Ada

<lang ada>with Ada.Text_Io; use Ada.Text_Io;

procedure Max_Sum is

  Triangle : array (Positive range <>) of integer :=
                                    (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);

  Last  : Integer := Triangle'Length;
  Tn    : Integer := 1;

begin

  while (Tn * (Tn + 1) / 2) < Last  loop
     Tn := Tn + 1;
  end loop;
  for N in reverse 2 .. Tn loop
     for I in 2 .. N loop

Triangle (Last - N) := Triangle (Last - N) + Integer'Max(Triangle (Last - 1), Triangle (Last)); Last := Last - 1;

     end loop;
     Last := Last - 1;
  end loop;
  Put_Line(Integer'Image(Triangle(1)));

end Max_Sum;</lang>

Output:

 1320

ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.6.win32

Basically the same algorithm as Ada and C++ but using a triangular matrix. <lang algol68># create a triangular array of the required values #

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

[18]REF[]INT triangle := ( row 1, row 2, row 3, row 4, row 5, row 6

                        , row  7, row  8, row  9, row 10, row 11, row 12
                        , row 13, row 14, row 15, row 16, row 17, row 18
                        );

PROC max = ( INT a, INT b )INT: IF a > b THEN a ELSE b FI;

1. working backwards, we replace the elements of each row with the sum of that #
2. element and the maximum of the two elements below it. #
3. That destroys the triangle but leaves element [1][1] equal to the required #
4. maximum #

FOR row FROM UPB triangle - 1 BY -1 TO 1 DO

   FOR element FROM 1 TO UPB triangle[row]
   DO
       # the elements "under" triangle[row][element] are                     #
       # triangle[row+1][element] and triangle[row+1][element+1]             #
       triangle[row][element]
           +:= max( triangle[row+1][element], triangle[row+1][element+1] )
   OD

OD;

print( ( triangle[1][1], newline ) ) </lang>

Output:

      +1320

C

<lang C>

1. include <stdio.h>
2. include <math.h>

1. define max(x,y) ((x) > (y) ? (x) : (y))

int tri[] = {

       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 };

int main(void) {

   const int len  = sizeof(tri) / sizeof(tri[0]);
   const int base = (sqrt(8*len + 1) - 1) / 2;
   int step       = base - 1;
   int stepc      = 0;

   int i;
   for (i = len - base - 1; i >= 0; --i) {
       tri[i] += max(tri[i + step], tri[i + step + 1]);
       if (++stepc == step) {
           step--;
           stepc = 0;
       }
   }

   printf("%d\n", tri[0]);
   return 0;

} </lang>

Output:

1320

C++

Translation of: Ada

<lang cpp>

1. include <iostream>

int main( int argc, char* argv[] ) {

   int triangle[] = 
   {

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

   };

   int last = sizeof( triangle ) / sizeof( int ),

tn = 1;

   while( ( tn * ( tn + 1 ) / 2 ) < last ) tn += 1;

   last--;
   for( int n = tn; n >= 2; n-- )
   {

for( int i = 2; i <= n; i++ ) { triangle[last - n] = triangle[last - n] + std::max( triangle[last - 1], triangle[last] ); last--; } last--;

   }
   std::cout << "Maximum total: " << triangle[0] << "\n\n";
   return system( "pause" );

} </lang>

Output:

Maximum total: 1320

Common Lisp

<lang lisp>(defun find-max-path-sum (s)

 (let ((triangle (loop for line = (read-line s NIL NIL) 
                       while line 
                       collect (with-input-from-string (str line) 
                                 (loop for n = (read str NIL NIL) 
                                       while n 
                                       collect n)))))
   (flet ((get-max-of-pairs (xs)
            (maplist (lambda (ys) 
                       (and (cdr ys) (max (car ys) (cadr ys))))
                     xs)))
     (car (reduce (lambda (xs ys) 
                    (mapcar #'+ (get-max-of-pairs xs) ys))
                  (reverse triangle))))))

(defparameter *small-triangle*

 "    55
    94 48
   95 30 96
 77 71 26 67")

(format T "~a~%" (with-input-from-string (s *small-triangle*)

                  (find-max-path-sum s)))

(format T "~a~%" (with-open-file (f "triangle.txt")

                  (find-max-path-sum f)))</lang>

Output:

321
1320

D

<lang d>void main() {

   import std.stdio, std.algorithm, std.range, std.file, std.conv;

   "triangle.txt".File.byLine.map!split.map!(to!(int[])).array.retro
   .reduce!((x, y) => zip(y, x, x.dropOne)
                      .map!(t => t[0] + t[1 .. $].max)
                      .array)[0]
   .writeln;

}</lang>

Output:

1320

Go

<lang go>package main

import (

   "fmt"
   "strconv"
   "strings"

)

const t = ` 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`

func main() {

   lines := strings.Split(t, "\n")
   f := strings.Fields(lines[len(lines)-1])
   d := make([]int, len(f))
   var err error
   for i, s := range f {
       if d[i], err = strconv.Atoi(s); err != nil {
           panic(err)
       }
   }
   d1 := d[1:]
   var l, r, u int
   for row := len(lines) - 2; row >= 0; row-- {
       l = d[0]
       for i, s := range strings.Fields(lines[row]) {
           if u, err = strconv.Atoi(s); err != nil {
               panic(err)
           }
           if r = d1[i]; l > r {
               d[i] = u + l
           } else {
               d[i] = u + r
           }
           l = r
       }
   }
   fmt.Println(d[0])

}</lang>

Output:

1320

Haskell

<lang haskell>parse = map (map read . words) . lines f x y z = x + max y z g xs ys = zipWith3 f xs ys $ tail ys solve = head . foldr1 g main = readFile "triangle.txt" >>= print . solve . parse</lang>

Output:

1320

J

<lang j>padTri=: 0 ". [: ];._2 ] NB. parse triangle and pad with zeros maxSum=: [: {. (+ (0 ,~ 2 >./\ ]))/ NB. find max triangle path sum</lang>

Example Usage <lang j> maxSum padTri freads 'triangle.txt' 1320</lang>

Java

Works with: Java version 8

<lang java>import java.nio.file.*; import static java.util.Arrays.stream;

public class MaxPathSum {

   public static void main(String[] args) throws Exception {
       int[][] data = Files.lines(Paths.get("triangle.txt"))
               .map(s -> stream(s.trim().split("\\s+"))
                       .mapToInt(Integer::parseInt)
                       .toArray())
               .toArray(int[][]::new);

       for (int r = data.length - 1; r > 0; r--)
           for (int c = 0; c < data[r].length - 1; c++)
               data[r - 1][c] += Math.max(data[r][c], data[r][c + 1]);

       System.out.println(data[0][0]);
   }

}</lang>

1320

JavaScript

<lang javascript> var arr = [ [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] ];

while (arr.length !== 1) {

 var len = arr.length;
 var row = [];
 var current = arr[len-2];
 var currentLen = current.length - 1;
 var end = arr[len-1];

 for ( var i = 0; i <= currentLen; i++ ) {
   row.push(Math.max(current[i] + end[i] || 0, current[i] + end[i+1] || 0) )
 }

 arr.pop();
 arr.pop();

 arr.push(row);

}

console.log(arr); </lang>

Output:

<lang javascript> [ [ 1320 ] ] </lang>

jq

The following implementation illustrates the use of an inner function as a helper function, which is used here mainly for clarity. The inner function in effect implements the inner loop; the outer loop is implemented using reduce.

The input array is identical to that in the Javascript section and is therefore omitted here.<lang jq># Usage: TRIANGLE | solve def solve:

 # update(next) updates the input row of maxima:
 def update(next):
   . as $maxima
   | [ range(0; next|length)
      | next[.] + ([$maxima[.], $maxima[. + 1]] | max) ];
 
 . as $in
 | reduce range(length -2; -1; -1) as $i 
     ($in[-1];  update( $in[$i] ) ) ;</lang>

Mathematica

<lang Mathematica>nums={{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}}; ClearAll[DoStep,MaximumTrianglePathSum] DoStep[lst1_List,lst2_List]:=lst2+Join[{First[lst1]},Max/@Partition[lst1,2,1],{Last[lst1]}] MaximumTrianglePathSum[triangle_List]:=Max[Fold[DoStep,First[triangle],Rest[triangle]]]</lang>

Output:

MaximumTrianglePathSum[nums]
1320

Nimrod

Translation of: Python

<lang nimrod>import strutils, future

proc solve(tri): int =

 var tri = tri
 while tri.len > 1:
   let t0 = tri.pop
   for i, t in tri[tri.high]: tri[tri.high][i] = max(t0[i], t0[i+1]) + t
 tri[0][0]

const data = """

                         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"""

echo solve data.splitLines.map((x: string) => x.split.map parseInt)</lang>

Output:

1320

PARI/GP

<lang parigp>V=[[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]]; forstep(i=#V,2,-1,V[i-1]+=vector(i-1,j,max(V[i][j],V[i][j+1]))); V[1][1]</lang>

Output:

%1 = 1320

Perl

<lang perl>use 5.10.0; use List::Util 'max';

my @sum; while (<>) { my @x = split; @sum = ($x[0] + $sum[0], map($x[$_] + max(@sum[$_-1, $_]), 1 .. @x-2), $x[-1] + $sum[-1]); }

say max(@sum);</lang>

Output:

% perl maxpath.pl triangle.txt
1320

Perl 6

The Z+ and Zmax are examples of the zipwith metaoperator. We ought to be able to use [Z+]= as an assignment operator here, but rakudo has a bug. Note also we can use the Zmax metaoperator form because max is define as an infix in Perl 6. <lang perl6>my @rows = slurp("triangle.txt").lines.map: { [.words] }

while @rows > 1 {

   my @last := @rows.pop;
   @rows[*-1] = @rows[*-1][] Z+ (@last Zmax @last[1..*]);

}

say @rows;</lang>

Output:

1320

Here's a more FPish version with the same output. We define our own operator and the use it in the reduction metaoperator form, [op], which turns any infix into a list operator. <lang perl6>sub infix:<op>(@a,@b) { (@a Zmax @a[1..*]) Z+ @b }

say [op] slurp("triangle.txt").lines.reverse.map: { [.words] }</lang> Instead of using reverse, one could also define the op as right-associative. <lang perl6>sub infix:<op>(@a,@b) is assoc('right') { @a Z+ (@b Zmax @b[1..*]) }

say [op] slurp("triangle.txt").lines.map: { [.words] }</lang>

Python

A simple mostly imperative solution: <lang python>def solve(tri):

   while len(tri) > 1:
       t0 = tri.pop()
       t1 = tri.pop()
       tri.append([max(t0[i], t0[i+1]) + t for i,t in enumerate(t1)])
   return tri[0][0]

def main():

   data = """\
                         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"""

   print solve([map(int, row.split()) for row in data.splitlines()])

main()</lang>

Output:

1320

A more functional version, similar to the Haskell entry (same output): <lang python>from itertools import imap

f = lambda x, y, z: x + max(y, z) g = lambda xs, ys: list(imap(f, ys, xs, xs[1:])) data = [map(int, row.split()) for row in open("triangle.txt")][::-1] print reduce(g, data)[0]</lang>

Racket

<lang racket>#lang racket (require math/number-theory)

(define (trinv n) ; OEIS A002024

 (exact-floor (/ (+ 1 (sqrt (* 1 (* 8 n)))) 2)))

(define (triangle-neighbour-bl n)

 (define row (trinv n))
 (+ n (- (triangle-number row) (triangle-number (- row 1)))))

(define (maximum-triangle-path-sum T)

 (define n-rows (trinv (vector-length T)))
 (define memo# (make-hash))
 (define (inner i)
   (hash-ref!
    memo# i
    (λ ()
      (+ (vector-ref T (sub1 i)) ; index is 1-based (so vector-refs need -1'ing)
         (cond [(= (trinv i) n-rows) 0]
               [else
                (define bl (triangle-neighbour-bl i))
                (max (inner bl) (inner (add1 bl)))])))))
 (inner 1))

(module+ main

 (maximum-triangle-path-sum
  #(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)))

(module+ test

 (require rackunit)
 (check-equal? (for/list ((n (in-range 1 (add1 10)))) (trinv n)) '(1 2 2 3 3 3 4 4 4 4))
 ;    1
 ;   2 3
 ;  4 5 6
 ; 7 8 9 10
 (check-eq? (triangle-neighbour-bl 1) 2)
 (check-eq? (triangle-neighbour-bl 3) 5)
 (check-eq? (triangle-neighbour-bl 5) 8)
 (define test-triangle
   #(55   94 48   95 30 96   77 71 26 67))
 (check-equal? (maximum-triangle-path-sum test-triangle) 321)
 )</lang>

Output:

1320

REXX

The method used is very efficient and performs very well for triangles that have thousands of rows (lines).
For an expanded discussion of the method's efficiency, see the discussion page. <lang rexx>/*REXX program finds the max sum of a "column" of numbers in a triangle.*/ @. = @.1 = 55 @.2 = 94 48 @.3 = 95 30 96 @.4 = 77 71 26 67 @.5 = 97 13 76 38 45 @.6 = 07 36 79 16 37 68 @.7 = 48 07 09 18 70 26 06 @.8 = 18 72 79 46 59 79 29 90 @.9 = 20 76 87 11 32 07 07 49 18 @.10 = 27 83 58 35 71 11 25 57 29 85 @.11 = 14 64 36 96 27 11 58 56 92 18 55 @.12 = 02 90 03 60 48 49 41 46 33 36 47 23 @.13 = 92 50 48 02 36 59 42 79 72 20 82 77 42 @.14 = 56 78 38 80 39 75 02 71 66 66 01 03 55 72 @.15 = 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36 @.16 = 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52 @.17 = 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15 @.18 = 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93

        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*/

rows=r-1 /*compute the number of rows. */

        do r=rows  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   /*replace previous #. */
            end   /*k*/
        end       /*r*/

say 'maximum path sum:' #.1.1 /*display the top (row 1) number.*/

                                      /*stick a fork in it, we're done.*/</lang>

output using the data within the REXX program:

maximum path sum: 1320

Ruby

<lang ruby> triangle = " 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"

ar = triangle.each_line.map{|line| line.strip.split.map(&:to_i)} until ar.size == 1 do

 maxes = ar.pop.each_cons(2).map(&:max)
 ar[-1]= ar[-1].zip(maxes).map{|r1,r2| r1 + r2}.flatten

end puts ar # => 1320</lang>

Scala

<lang Scala>object MaximumTrianglePathSum extends App {

   // Solution:
   def sum(triangle: Array[Array[Int]]) =
       triangle.reduceRight((upper, lower) =>
           upper zip (lower zip lower.tail)
           map {case (above, (left, right)) => above + Math.max(left, right)}
       ).head

   // Tests:
   def triangle = """   
                         55
                       94 48
                      95 30 96
                    77 71 26 67
   """
   def parse(s: String) = s.trim.split("\\s+").map(_.toInt)
   def parseLines(s: String) = s.trim.split("\n").map(parse)
   def parseFile(f: String) = scala.io.Source.fromFile(f).getLines.map(parse).toArray
   println(sum(parseLines(triangle)))
   println(sum(parseFile("triangle.txt")))

}</lang>

Output:

321
1320

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

proc maxTrianglePathSum {definition} {

   # Parse the definition, stripping whitespace and leading zeroes.
   set lines [lmap line [split [string trim $definition] "\n"] {

lmap val $line {scan $val %d}

   }]
   # Paths are bit strings (0 = go left, 1 = go right).
   # Enumerate the possible paths.
   set numPaths [expr {2 ** [llength $lines]}]
   for {set path 0; set max -inf} {$path < $numPaths} {incr path} {

# Work out how much the current path costs. set sum [set idx [set row 0]] for {set bit 1} {$row < [llength $lines]} {incr row} { incr sum [lindex $lines $row $idx] if {$path & $bit} {incr idx} set bit [expr {$bit << 1}] } # Remember the max so far. if {$sum > $max} {set max $sum}

   }
   return $max

}

puts [maxTrianglePathSum {

                         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 }]

1. Reading from a file is left as an exercise…</lang>

Output:

1320

zkl

Translation of: Python

The two Python solutions: <lang zkl>tri:=File("triangle.txt").pump(List,fcn(s){ s.strip().split(" ").apply("toInt") }).copy(); while(tri.len()>1){

  t0:=tri.pop();
  t1:=tri.pop();
  tri.append( [[(it); t1.enumerate(); 

'wrap([(i,t)]){ t + t0[i].max(t0[i+1]) }]]) } tri[0][0].println();</lang> <lang zkl>data:=File("triangle.txt").pump(List,fcn(s){ s.strip().split(" ").apply("toInt") }); fcn f(x,y,z){ x + y.max(z) } fcn g(xs,ys){ Utils.zipWith(f,ys,xs,xs[1,*]); } data.reverse().reduce(g)[0].println();</lang>

Translation of: Go

<lang zkl>lines:=File("triangle.txt").pump(List,fcn(s){ s.strip().split(" ").apply("toInt") }); d:=lines[-1].copy(); foreach row in ([lines.len()-2..0,-1]){

  d1:=d[1,*];
  l :=d[0];
  foreach i,u in (lines[row].enumerate()){
      d[i] = u + l.max(r:=d1[i]);
      l    = r;
   }

} println(d[0]);</lang>

Output:

1320
1320
1320