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
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;
- working backwards, we replace the elements of each row with the sum of that #
- element and the maximum of the two elements below it. #
- That destroys the triangle but leaves element [1][1] equal to the required #
- 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
AutoHotkey
<lang AutoHotkey></lang> Examples:<lang AutoHotkey>data :=[ (join ltrim
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 )]
i := data.MaxIndex() row := Ceil((Sqrt(8*i+1) - 1) / 2) path:=[]
loop % row { path[i] := data[i] i-- }
while i { row := Ceil((Sqrt(8*i+1) - 1) / 2) path[i] := data[i] "+" (data[i+row] > data[i+row+1] ? path[i+row] : path[i+row+1]) data[i] += data[i+row] > data[i+row+1] ? data[i+row] : data[i+row+1] i -- }
MsgBox % data[1] "`n" path[1]</lang>
Outputs:
1320 55+94+95+77+97+7+48+72+76+83+64+90+48+80+84+85+94+71
Bracmat
<lang bracmat>( "
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 "
: ?triangle
& ( max
= a b . !arg:(?a.?b)&(!a:>!b|!b) )
& 0:?accumulator & whl
' ( @(!triangle:?row (\n|\r) ?triangle)
& :?newaccumulator
& 0:?first
& whl
' ( @(!row:? #%?n (" " ?row|:?row))
& !accumulator:#%?second ?accumulator
& !newaccumulator max$(!first.!second)+!n:?newaccumulator
& !second:?first
)
& !newaccumulator 0:?accumulator
)
& ( -1:?Max
& !accumulator
: ? (%@:>!Max:?Max&~) ?
| out$!Max
)
)</lang>
- Output:
1320
C
<lang C>
- include <stdio.h>
- include <math.h>
- 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++
<lang cpp>
- 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
};
const int size = sizeof( triangle ) / sizeof( int ); const int tn = static_cast<int>(sqrt(2.0 * size)); assert(tn * (tn + 1) == 2 * size); // size should be a triangular number
// walk backward by rows, replacing each element with max attainable therefrom
for (int n = tn - 1; n > 0; --n) // n is size of row, note we do not process last row
for (int k = (n * (n-1)) / 2; k < (n * (n+2)) / 2; ++k)
triangle[k] += std::max(triangle[k + n], triangle[k + n + 1]);
std::cout << "Maximum total: " << triangle[0] << "\n\n";
} </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
Elixir
<lang elixir>defmodule Maximum do
def triangle_path(text) do
String.split(text, "\n", trim: true)
|> Enum.map(fn line -> String.split(line) |> Enum.map(&String.to_integer(&1)) end)
|> Enum.reduce([], fn x,total ->
Enum.chunk([0]++total++[0], 2, 1)
|> Enum.map(&Enum.max(&1))
|> Enum.zip(x)
|> Enum.map(fn{a,b} -> a+b end)
end)
|> Enum.max
end
end
text = """
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 """
IO.puts Maximum.triangle_path(text)</lang>
- Output:
1320
ERRE
<lang ERRE> PROGRAM TRIANGLE_PATH
CONST ROW=18
DIM TRI[200]
! ! for rosettacode,org !
FUNCTION MAX(X,Y)
MAX=-X*(X>=Y)-Y*(X<Y)
END FUNCTION
BEGIN
DATA(55)
DATA(94,48)
DATA(95,30,96)
DATA(77,71,26,67)
DATA(97,13,76,38,45)
DATA(7,36,79,16,37,68)
DATA(48,7,9,18,70,26,6)
DATA(18,72,79,46,59,79,29,90)
DATA(20,76,87,11,32,7,7,49,18)
DATA(27,83,58,35,71,11,25,57,29,85)
DATA(14,64,36,96,27,11,58,56,92,18,55)
DATA(2,90,3,60,48,49,41,46,33,36,47,23)
DATA(92,50,48,2,36,59,42,79,72,20,82,77,42)
DATA(56,78,38,80,39,75,2,71,66,66,1,3,55,72)
DATA(44,25,67,84,71,67,11,61,40,57,58,89,40,56,36)
DATA(85,32,25,85,57,48,84,35,47,62,17,1,1,99,89,52)
DATA(6,71,28,75,94,48,37,10,23,51,6,48,53,18,74,98,15)
DATA(27,2,92,23,8,71,76,84,15,52,92,63,81,10,44,10,69,93)
PRINT(CHR$(12);) !CLS
LUNG=ROW*(ROW+1)/2
FOR I%=0 TO LUNG-1 DO
READ(TRI[I%])
END FOR
BSE=(SQR(8*LUNG+1)-1)/2
STP=BSE-1
STEPC=0
FOR I%=LUNG-BSE-1 TO 0 STEP -1 DO
TRI[I%]=TRI[I%]+MAX(TRI[I%+STP],TRI[I%+STP+1])
STEPC=STEPC+1
IF STEPC=STP THEN
STP=STP-1
STEPC=0
END IF
END FOR
PRINT(TRI[0])
END PROGRAM </lang>
FreeBASIC
<lang FreeBASIC>' version 21-06-2015 ' compile with: fbc -s console
Data " 55" Data " 94 48" Data " 95 30 96" Data " 77 71 26 67" Data " 97 13 76 38 45" Data " 07 36 79 16 37 68" Data " 48 07 09 18 70 26 06" Data " 18 72 79 46 59 79 29 90" Data " 20 76 87 11 32 07 07 49 18" Data " 27 83 58 35 71 11 25 57 29 85" Data " 14 64 36 96 27 11 58 56 92 18 55" Data " 02 90 03 60 48 49 41 46 33 36 47 23" Data " 92 50 48 02 36 59 42 79 72 20 82 77 42" Data " 56 78 38 80 39 75 02 71 66 66 01 03 55 72" Data " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" Data " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" Data " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" Data " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" Data "END" ' no more data
' ------=< MAIN >=------
Dim As String ln Dim As Integer matrix(1 To 20, 1 To 20) Dim As Integer x = 1, y, s1, s2, size
Do
Read ln
ln = Trim(ln)
If ln = "END" Then Exit Do
For y = 1 To x
matrix(x, y) = Val(Left(ln, 2))
ln = Mid(ln, 4)
Next
x += 1
size += 1
Loop
For x = size - 1 To 1 Step - 1
For y = 1 To x
s1 = matrix(x + 1, y)
s2 = matrix(x + 1, y + 1)
If s1 > s2 Then
matrix(x, y) += s1
Else
matrix(x, y) += s2
End If
Next
Next
Print Print " maximum triangle path sum ="; matrix(1, 1)
' empty keyboard buffer While InKey <> "" : Var _key_ = InKey : Wend Print : Print "hit any key to end program" Sleep End</lang>
- Output:
maximum triangle path sum = 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 (implicitly) pad with zeros maxSum=: [: {. (+ (0 ,~ 2 >./\ ]))/ NB. find max triangle path sum</lang>
Example Usage <lang j> maxSum padTri freads 'triangle.txt' 1320</lang>
Explanation:
First, we pad all short rows with trailing zeros so that all rows are the same length. This eliminates some ambiguity and simplifies the expression of both the data and the code.
Second, starting with the last row, for each pair of numbers we find the largest of the two (resulting in a list slightly shorter than before, so of course we pad it with a trailing zero) and add that row to the previous row. After repeating this through all the rows, the first value of the resulting row is the maximum we were looking for.
Instead of padding, we could instead trim the other argument to match the current reduced row length.
<lang J>maxsum=: ((] + #@] {. [)2 >./\ ])/</lang>
However, this turns out to be a slightly slower approach, because we are doing a little more work for each row.
(Note that the cost of padding every row to the same width averages out to an average 2x cost in space and time. So what we are saying here is that the interpreter overhead for changing the size of the memory region used in each operation with each row winds up being more than a 2x cost. You can probably beat that using compiled code, but of course the cost of compiling the program will itself be more than 2x - so not worth paying in a one-off experiment. You wind up with similar issues in any system involving one-off tests.)
Java
<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
Imperative
<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>
Functional (ES5)
<lang JavaScript>(function () {
// Right fold using final element as initial accumulator
// (a -> a -> a) -> t a -> a
function foldr1(f, lst) {
return lst.length > 1 ? (
f(lst[0], foldr1(f, lst.slice(1)))
) : lst[0];
}
// function of arity 3 mapped over nth items of each of 3 lists
// (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
function zipWith3(f, xs, ys, zs) {
return zs.length ? [f(xs[0] || [], ys[0] || [], zs[0])].concat(
zipWith3(f, xs.slice(1), ys.slice(1), zs.slice(1))) : [];
}
return foldr1(
function (xs, ys) {
return zipWith3(
function (x, y, z) {
return x + (y < z ? z : y);
},
xs, ys, ys.slice(1)
);
}, [
[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]
]
)[0];
})();</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>
Lua
While the solutions here are clever, I found most of them to be hard to follow. In fact, none of them are very good for showing how the algorithm works. So I wrote this Lua version for maximum readability.
<lang lua>local triangleSmall = {
{ 55 },
{ 94, 48 },
{ 95, 30, 96 },
{ 77, 71, 26, 67 },
}
local triangleLarge = {
{ 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 },
};
function solve(triangle)
-- Get total number of rows in triangle. local nRows = table.getn(triangle)
-- Start at 2nd-to-last row and work up to the top. for row = nRows-1, 1, -1 do
-- For each value in row, add the max of the 2 children beneath it.
for i = 1, row do
local child1 = triangle[row+1][i]
local child2 = triangle[row+1][i+1]
triangle[row][i] = triangle[row][i] + math.max(child1, child2)
end
end
-- The top of the triangle now holds the answer. return triangle[1][1];
end
print(solve(triangleSmall)) print(solve(triangleLarge)) </lang>
- Output:
321 1320
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
Nim
<lang nim>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
Pascal
testet with freepascal, should run under Turbo Pascal, therefore using static array and val, and Delphi too. <lang pascal>program TriSum; {'triangle.txt'
- one element per line
55 94 48 95 30 96 ...} const
cMaxTriHeight = 18; cMaxTriElemCnt = (cMaxTriHeight+1)*cMaxTriHeight DIV 2 +1;
type
tElem = longint; tbaseRow = array[0..cMaxTriHeight] of tElem; tmyTri = array[0..cMaxTriElemCnt] of tElem;
function ReadTri( fname:string;
out t:tmyTri):integer;
{read triangle values into t and returns height} var
f : text; s : string; i : integer; ValCode : word;
begin
i := 0; fillchar(t,Sizeof(t),#0);
Assign(f,fname);
{$I-}
reset(f);
IF ioResult <> 0 then
begin
writeln('IO-Error ',ioResult);
close(f);
ReadTri := i;
EXIT;
end;
{$I+}
while NOT(EOF(f)) AND (i<cMaxTriElemCnt) do
begin
readln(f,s);
val(s,t[i],ValCode);
inc(i);
IF ValCode <> 0 then
begin
writeln(ValCode,' conversion error at line ',i);
fillchar(t,Sizeof(t),#0);
i := 0;
BREAK;
end;
end;
close(f);
ReadTri := round(sqrt(2*(i-1)));
end;
function TriMaxSum(var t: tmyTri;hei:integer):integer; {sums up higher values bottom to top} var
i,r,h,tmpMax : integer; idxN : integer; sumrow : tbaseRow;
begin
h := hei;
idxN := (h*(h+1)) div 2 -1;
{copy base row}
move(t[idxN-h+1],sumrow[0],SizeOf(tElem)*h);
dec(h);
{ for r := 0 to h do write(sumrow[r]:4);writeln;}
idxN := idxN-h;
while idxN >0 do
begin
i := idxN-h;
r := 0;
while r < h do
begin
tmpMax:= sumrow[r];
IF tmpMax<sumrow[r+1] then
tmpMax:=sumrow[r+1];
sumrow[r]:= tmpMax+t[i];
inc(i);
inc(r);
end;
idxN := idxN-h;
dec(h);
{ for r := 0 to h do write(sumrow[r]:4);writeln;}
end; TriMaxSum := sumrow[0];
end;
var
h : integer; triangle : tmyTri;
Begin { writeln(TriMaxSum(triangle,ReadTri('triangle.txt',triangle))); -> 1320}
h := ReadTri('triangle.txt',triangle);
writeln('height sum');
while h > 0 do
begin
writeln(h:4,TriMaxSum(triangle,h):7);
dec(h);
end;
end.</lang>
- Output:
height sum 18 1320 17 1249 .... 4 321 3 244 2 149 1 55
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>
PicoLisp
<lang PicoLisp>(de maxpath (Lst)
(let (Lst (reverse Lst) R (car Lst))
(for I (cdr Lst)
(setq R
(mapcar
+
(maplist
'((L)
(and (cdr L) (max (car L) (cadr L))) )
R )
I ) ) )
(car R) ) )</lang>
PL/I
<lang pli>*process source xref attributes or(!);
triang: Proc Options(Main); Dcl nn(18,18) Bin Fixed(31); Dcl (rows,i,j) Bin Fixed(31); Dcl (p,k,kn) Bin Fixed(31); Call f_r(1 ,' 55 '); Call f_r(2 ,' 94 48 '); Call f_r(3 ,' 95 30 96 '); Call f_r(4 ,' 77 71 26 67 '); Call f_r(5 ,' 97 13 76 38 45 '); Call f_r(6 ,' 07 36 79 16 37 68 '); Call f_r(7 ,' 48 07 09 18 70 26 06 '); Call f_r(8 ,' 18 72 79 46 59 79 29 90 '); Call f_r(9 ,' 20 76 87 11 32 07 07 49 18 '); Call f_r(10,' 27 83 58 35 71 11 25 57 29 85 '); Call f_r(11,' 14 64 36 96 27 11 58 56 92 18 55 '); Call f_r(12,' 02 90 03 60 48 49 41 46 33 36 47 23 '); Call f_r(13,' 92 50 48 02 36 59 42 79 72 20 82 77 42 '); Call f_r(14,' 56 78 38 80 39 75 02 71 66 66 01 03 55 72 '); Call f_r(15,' 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36 '); Call f_r(16,' 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52 '); Call f_r(17,' 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15 '); Call f_r(18,' 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93'); rows=hbound(nn,1);
do r=rows by -1 to 2;
p=r-1; /*traipse through triangle rows. */
do k=1 to p;
kn=k+1; /*re-calculate the previous row. */
nn(p,k)=max(nn(r,k),nn(r,kn))+nn(p,k); /*replace previous nn */
end;
end;
Put Edit('maximum path sum:',nn(1,1))(Skip,a,f(5)); /*display result*/
f_r: Proc(r,vl);
/* fill row r with r values */
Dcl r Bin Fixed(31);
Dcl vl Char(*);
Dcl vla Char(100) Var;
vla=' '!!trim(vl);
get string(vla) Edit((nn(r,j) Do j=1 To r))(f(3));
End;
End;</lang>
- Output:
maximum path sum: 1320
Prolog
<lang Prolog>max_path(N, V) :- data(N, T), path(0, T, V).
path(_N, [], 0) . path(N, [H | T], V) :- nth0(N, H, V0), N1 is N+1, path(N, T, V1), path(N1, T, V2), V is V0 + max(V1, V2).
data(1, P) :- P = [ [55], [94, 48], [95, 30, 96], [77, 71, 26, 67]].
data(2, P) :-
P =
[ [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]].
</lang>
- Output:
?- max_path(1, V). V = 321 . ?- max_path(2, V). V = 1320 .
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]
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()])</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.split.map(&:to_i)} puts ar.inject([]){|res,x|
maxes = [0, *res, 0].each_cons(2).map(&:max)
x.zip(maxes).map{|a,b| a+b}
}.max
- => 1320</lang>
Rust
<lang rust>use std::cmp::max;
fn max_path(vector: &mut Vec<Vec<u32>>) -> u32 {
while vector.len() > 1 {
let last = vector.pop().unwrap();
let ante = vector.pop().unwrap();
let mut new: Vec<u32> = Vec::new();
for (i, value) in ante.iter().enumerate() {
new.push(max(last[i], last[i+1]) + value);
};
vector.push(new);
};
vector[0][0]
}
fn main() {
let mut 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";
let mut vector = data.split("\n").map(|x| x.split(" ").map(|s: &str| s.parse::<u32>().unwrap())
.collect::<Vec<u32>>()).collect::<Vec<Vec<u32>>>();
let max_value = max_path(&mut vector);
println!("{}", max_value);
//=> 7273
}</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
Sidef
Iterative solution: <lang ruby>var sum = [0];
ARGF.each { |line|
var x = line.words.map{.to_i};
sum = [
x.first + sum.first,
1 ... x.len-2 -> map{|i| x[i] + [sum[i-1, i]].max}...,
x.last + sum.last,
];
}
say sum.max;</lang>
Recursive solution: <lang ruby>var triangle = ARGF.slurp.lines.map{.words.map{.to_i}};
func max_value(i=0, j=0) is cached {
i == triangle.len && return 0; triangle[i][j] + [max_value(i+1, j), max_value(i+1, j+1)].max;
}
say max_value();</lang>
- Output:
% sidef maxpath.sf triangle.txt 1320
Tcl
<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 }]
- Reading from a file is left as an exercise…</lang>
- Output:
1320
VBScript
<lang vb> 'Solution derived from http://stackoverflow.com/questions/8002252/euler-project-18-approach.
Set objfso = CreateObject("Scripting.FileSystemObject") Set objinfile = objfso.OpenTextFile(objfso.GetParentFolderName(WScript.ScriptFullName) &_ "\triangle.txt",1,False)
row = Split(objinfile.ReadAll,vbCrLf)
For i = UBound(row) To 0 Step -1 row(i) = Split(row(i)," ") If i < UBound(row) Then For j = 0 To UBound(row(i)) If (row(i)(j) + row(i+1)(j)) > (row(i)(j) + row(i+1)(j+1)) Then row(i)(j) = CInt(row(i)(j)) + CInt(row(i+1)(j)) Else row(i)(j) = CInt(row(i)(j)) + CInt(row(i+1)(j+1)) End If Next End If Next
WScript.Echo row(0)(0)
objinfile.Close Set objfso = Nothing </lang>
- Input:
Input file
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
- Output:
1320
zkl
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>
<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