Maximum triangle path sum: Difference between revisions

← Older edit

Maximum triangle path sum (view source)

Revision as of 19:09, 18 February 2024

134,676 bytes added , 4 months ago

m

→‎{{header|EasyLang}}

Chkas

2,067

edits

Revision as of 20:11, 11 April 2014 (view source) rosettacode>TimToady (→‎{{header\|Perl 6}}: update to latest semantics) ← Older edit		Latest revision as of 19:09, 18 February 2024 (view source) Chkas (talk \| contribs) m (→‎{{header\|EasyLang}})
(160 intermediate revisions by 67 users not shown)
Line 1: {{task}} 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: <pre> Line 4 ⟶ 6: 94 48 95 30 96 77 71 26 67~~</pre>~~ </pre> 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.~~ 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:~~ ;Task: Find the maximum total in the triangle below: <pre> 55 Line 29 ⟶ 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~~</pre>~~ </pre> Such numbers can be included in the solution code, or read from a "triangle.txt" file. This task is derived from the [http://projecteuler.net/problem=18 Euler Problem #18]. <br><br> =={{header\|11l}}== {{trans\|Python}} <syntaxhighlight lang="11l">F solve(&tri) L tri.len > 1 V t0 = tri.pop() V t1 = tri.pop() tri.append(enumerate(t1).map((i, t) -> max(@t0[i], @t0[i + 1]) + t)) R tri[0][0] V 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(&data.split("\n").map(row -> row.split(‘ ’, group_delimiters' 1B).map(Int))))</syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|360 Assembly}}== <syntaxhighlight lang="360asm">* Maximum triangle path sum - 28/04/2023 MAXTRIA CSECT USING MAXTRIA,R13 base register B 72(R15) skip savearea DC 17F'0' savearea SAVE (14,12) save previous context ST R13,4(R15) link backward ST R15,8(R13) link forward LR R13,R15 set addressability LA R9,1 k=1 LA R6,1 i=1 DO WHILE=(CH,R6,LE,=AL2(N)) do i=1 to hbound(t) LR R1,R6 i BCTR R1,0 -1 MH R1,=AL2(X) x LA R14,T(R1) @t(i) MVC C,0(R14) c=t(i) LA R7,1 j=1 DO WHILE=(CR,R7,LE,R9) do j=1 to k MVC CC,C cc=substr(c,1,2) MVC XDEC,=CL12' ' clear MVC XDEC(L'CC),CC cc XDECI R2,XDEC r2=int(cc) LR R1,R9 k BCTR R1,0 -1 MH R1,=AL2(N) n LR R0,R7 j BCTR R0,0 -1 AR R1,R0 (k-1)n+(j-1) SLA R1,1 2 (H) STH R2,MM(R1) m(k,j)=xdeci(substr(c,1,2),2) LA R10,X l=length(c) DO WHILE=(CH,R10,GE,=AL2(1)) do l=length(c) to 1 by -1 LA R14,C-1 @c-1 AR R14,R10 +l MVC CL,0(R14) cl=substr(c,l,1) IF CLI,CL,NE,C' ' THEN if substr(c,l,1)^=' ' then B LEAVEL leave l ENDIF , endif BCTR R10,0 l-- ENDDO , enddo l LEAVEL EQU * IF CH,R10,GT,=AL2(4) THEN if l>4 then LR R5,R10 l SH R5,=H'3' l-3 (mvcl source length) LA R3,L'C64 x (mvcl target length) LA R4,C+3 @c+3 (mvcl source) LA R2,C64 @c64 (mvcl target) ICM R3,B'1000',=C' ' padding char MVCL R2,R4 mvcl @c64[64] <- @c+3[l-3] MVC C,C64 c=substr(c,4,l-3) ENDIF , endif LA R7,1(R7) j++ ENDDO , enddo j LA R9,1(R9) k=k+1 LA R6,1(R6) i++ ENDDO , enddo i LR R6,R9 k SH R6,=H'2' k-2 DO WHILE=(CH,R6,GE,=AL2(1)) do i=k-2 to 1 by -1 LA R7,1 j=1 DO WHILE=(CR,R7,LE,R6) do j=1 to i LR R1,R6 i MH R1,=AL2(N) n LR R0,R7 j BCTR R0,0 j-1 AR R1,R0 in+(j-1) SLA R1,1 2 (H) LH R2,MM(R1) m(i+1,j) STH R2,S1 s1=m(i+1,j) LR R1,R6 i MH R1,=AL2(N) n AR R1,R7 in+j SLA R1,1 2 (H) LH R2,MM(R1) m(i+1,j+1) STH R2,S2 s2=m(i+1,j+1) LH R4,S1 s1 IF CH,R4,GT,S2 THEN if s1>s2 then LH R8,S1 sm=s1 ELSE , else LH R8,S2 sm=s2 ENDIF , endif LR R1,R6 i BCTR R1,0 i-1 MH R1,=AL2(N) n LR R0,R7 j BCTR R0,0 j-1 AR R1,R0 (i-1)n+(j-1) SLA R1,1 2 (H) LH R2,MM(R1) m(i,j) LR R10,R1 index m(i,j) AR R2,R8 m(i,j)+sm STH R2,MM(R10) m(i,j)=m(i,j)+sm LA R7,1(R7) j++ ENDDO , enddo j BCTR R6,0 i-- ENDDO , enddo i LH R1,MM m(1,1) XDECO R1,PG edit m(1,1) XPRNT PG,L'PG output m(1,1) L R13,4(0,R13) restore previous savearea pointer RETURN (14,12),RC=0 restore registers from calling save N EQU 18 n X EQU 64 x MM DS (NN)H m(n,n) S1 DS H s1 S2 DS H s2 C DS CL(X) c CC DS CL2 cc CL DS CL1 cl C64 DS CL(X) c64 PG DC CL80' ' buffer XDEC DS CL12 temp for xdeci xdeco T DC CL(X)'55' t(18) char(64) DC CL(X)'94 48' DC CL(X)'95 30 96' DC CL(X)'77 71 26 67' DC CL(X)'97 13 76 38 45' DC CL(X)'07 36 79 16 37 68' DC CL(X)'48 07 09 18 70 26 06' DC CL(X)'18 72 79 46 59 79 29 90' DC CL(X)'20 76 87 11 32 07 07 49 18' DC CL(X)'27 83 58 35 71 11 25 57 29 85' DC CL(X)'14 64 36 96 27 11 58 56 92 18 55' DC CL(X)'02 90 03 60 48 49 41 46 33 36 47 23' DC CL(X)'92 50 48 02 36 59 42 79 72 20 82 77 42' DC CL(X)'56 78 38 80 39 75 02 71 66 66 01 03 55 72' DC CL(X)'44 25 67 84 71 67 11 61 40 57 58 89 40 56 36' DC CL(X)'85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52' DC CL(X)'06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15' DC CL(X)'27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93' REGEQU END MAXTRIA</syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|Action!}}== <syntaxhighlight lang="action!">INT FUNC Max(INT a,b) IF a>b THEN RETURN (a) FI RETURN (b) PROC Main() DEFINE ROWCOUNT="18" INT i,row,len,a,b INT ARRAY rows(ROWCOUNT) INT ARRAY 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] row=0 len=1 FOR i=0 TO ROWCOUNT-1 DO rows(i)=row row==+len len==+1 OD row=ROWCOUNT-2 WHILE row>=0 DO len=row+1 FOR i=0 TO len-1 DO a=data(rows(row+1)+i) b=data(rows(row+1)+i+1) data(rows(row)+i)==+Max(a,b) OD row==-1 OD PrintI(data(0)) RETURN</syntaxhighlight> {{out}} [https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Maximum_triangle_path_sum.png Screenshot from Atari 8-bit computer] <pre> 1320 </pre> =={{header\|Ada}}== <~~lang~~syntaxhighlight lang="ada">with Ada.Text_Io; use Ada.Text_Io; procedure Max_Sum is Line 75 ⟶ 317: end loop; Put_Line(Integer'Image(Triangle(1))); end Max_Sum;</~~lang~~syntaxhighlight> {{out}} ~~Output:~~ <pre> 1320 </pre> =={{header\|ALGOL 68}}== {{works with\|ALGOL 68G\|Any - tested with release 2.6.win32}} Basically the same algorithm as Ada and C++ but using a triangular matrix. <syntaxhighlight 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 ) ) </syntaxhighlight> {{out}} <pre> +1320 </pre> =={{header\|APL}}== {{works with\|Dyalog APL}} <syntaxhighlight lang="apl">parse ← ⍎¨(~∊)∘⎕TC⊆⊢ maxpath ← ⊃(⊣+2⌈/⊢)/ ⎕ ← maxpath parse ⊃⎕NGET'G:\triangle.txt'</syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|AppleScript}}== {{Trans\|JavaScript}} <syntaxhighlight lang="applescript">---------------- MAXIMUM TRIANGLE PATH SUM --------------- -- Working from the bottom of the triangle upwards, -- summing each number with the larger of the two below -- until the maximum emerges at the top. -- maxPathSum :: [[Int]] -> Int on maxPathSum(xss) -- With the last row as the initial accumulator, -- folding from the penultimate line, -- towards the top of the triangle: -- sumWithRowBelow :: [Int] -> [Int] -> [Int] script sumWithRowBelow on \|λ\|(row, accum) -- plusGreaterOfTwoBelow :: Int -> Int -> Int -> Int script plusGreaterOfTwoBelow on \|λ\|(x, intLeft, intRight) x + max(intLeft, intRight) end \|λ\| end script -- The accumulator, zipped with the tail of the -- accumulator, yields pairs of adjacent sums so far. zipWith3(plusGreaterOfTwoBelow, row, accum, tail(accum)) end \|λ\| end script -- A list of lists folded down to a list of just one remaining integer. -- Head returns that integer from the list. head(foldr1(sumWithRowBelow, xss)) end maxPathSum --------------------------- TEST ------------------------- on run maxPathSum({¬ {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} ¬ }) --> 1320 end run -------------------- GENERIC FUNCTIONS ------------------- -- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs) tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to \|λ\|(v, item i of xs, i, xs) end repeat return v end tell end foldl -- foldr1 :: (a -> a -> a) -> [a] -> a on foldr1(f, xs) if length of xs > 1 then tell mReturn(f) set v to item -1 of xs set lng to length of xs repeat with i from lng - 1 to 1 by -1 set v to \|λ\|(item i of xs, v, i, xs) end repeat return v end tell else xs end if end foldr1 -- head :: [a] -> a on head(xs) if length of xs > 0 then item 1 of xs else missing value end if end head -- max :: Ord a => a -> a -> a on max(x, y) if x > y then x else y end if end max -- min :: Ord a => a -> a -> a on min(x, y) if y < x then y else x end if end min -- minimum :: [a] -> a on minimum(xs) script min on \|λ\|(a, x) if x < a or a is missing value then x else a end if end \|λ\| end script foldl(min, missing value, xs) end minimum -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f) if class of f is script then f else script property \|λ\| : f end script end if end mReturn -- tail :: [a] -> [a] on tail(xs) if length of xs > 1 then items 2 thru -1 of xs else {} end if end tail -- zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] on zipWith3(f, xs, ys, zs) set lng to minimum({length of xs, length of ys, length of zs}) set lst to {} tell mReturn(f) repeat with i from 1 to lng set end of lst to \|λ\|(item i of xs, item i of ys, item i of zs) end repeat return lst end tell end zipWith3</syntaxhighlight> {{Out}} <pre>1320</pre> =={{header\|Arturo}}== <syntaxhighlight lang="arturo">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 :} solve: function [triangle][ tri: triangle while [1 < size tri][ t0: last tri chop 'tri loop.with:'i tri\[dec size tri] 't -> tri\[dec size tri]\[i]: t + max @[t0\[i] t0\[inc i]] ] tri\0\0 ] print solve map split.lines strip data 'x -> map split.by:" " strip x 'y -> to :integer y </syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|Astro}}== <syntaxhighlight lang="python">fun maxpathsum(t): #: Array{Array{I}} let a = val t for i in a.length-1..-1..1, c in linearindices a[r]: a[r, c] += max(a[r+1, c], a[r=1, c+1]) return a[1, 1] let test = [ [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 maxpathsum test </syntaxhighlight> =={{header\|AutoHotkey}}== Examples:<syntaxhighlight 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(8i+1) - 1) / 2) path:=[] loop % row { path[i] := data[i] i-- } while i { row := Ceil((Sqrt(8i+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]</syntaxhighlight> Outputs:<pre>1320 55+94+95+77+97+7+48+72+76+83+64+90+48+80+84+85+94+71</pre> =={{header\|AWK}}== <syntaxhighlight lang="awk"> # syntax: GAWK -f MAXIMUM_TRIANGLE_PATH_SUM.AWK filename(s) { printf("%s\n",$0) cols[FNR] = NF for (i=1; i<=NF; i++) { arr[FNR][i] = $i } } ENDFILE { for (row=FNR-1; row>0; row--) { for (col=1; col<=cols[row]; col++) { arr[row][col] += max(arr[row+1][col],arr[row+1][col+1]) } } printf("%d using %s\n\n",arr[1][1],FILENAME) delete arr delete cols } END { exit(0) } function max(x,y) { return((x > y) ? x : y) } </syntaxhighlight> {{out}} <pre> 55 94 48 95 30 96 77 71 26 67 321 using MAXIMUM_TRIANGLE_PATH_SUM_4.TXT 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 1320 using MAXIMUM_TRIANGLE_PATH_SUM_18.TXT </pre> =={{header\|Bracmat}}== <syntaxhighlight 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 ) )</syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|BASIC}}== ==={{header\|Applesoft BASIC}}=== The [[#Chipmunk Basic\|Chipmunk Basic]] solution works without any changes. ==={{header\|BASIC256}}=== <syntaxhighlight lang="freebasic">arraybase 1 dim ln(19) ln[1] = " 55" ln[2] = " 94 48" ln[3] = " 95 30 96" ln[4] = " 77 71 26 67" ln[5] = " 97 13 76 38 45" ln[6] = " 07 36 79 16 37 68" ln[7] = " 48 07 09 18 70 26 06" ln[8] = " 18 72 79 46 59 79 29 90" ln[9] = " 20 76 87 11 32 07 07 49 18" ln[10] = " 27 83 58 35 71 11 25 57 29 85" ln[11] = " 14 64 36 96 27 11 58 56 92 18 55" ln[12] = " 02 90 03 60 48 49 41 46 33 36 47 23" ln[13] = " 92 50 48 02 36 59 42 79 72 20 82 77 42" ln[14] = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72" ln[15] = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" ln[16] = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" ln[17] = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" ln[18] = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" ln[19] = "end" dim matrix(20,20) x = 1 tam = 0 for n = 1 to length(ln) - 1 ln2 = trim(ln[n]) for y = 1 to x matrix[x, y] = fromradix((left(ln2, 2)), 10) if length(ln2) > 4 then ln2 = mid(ln2, 4, length(ln2)-4) next y x += 1 tam += 1 next n for x = tam - 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] = matrix[x, y] + s1 else matrix[x, y] = matrix[x, y] + s2 end if next y next x print " maximum triangle path sum = " + matrix[1, 1]</syntaxhighlight> {{out}} <pre> maximum triangle path sum = 1320</pre> ==={{header\|Chipmunk Basic}}=== {{works with\|Chipmunk Basic\|3.6.4}} {{works with\|Applesoft BASIC}} {{works with\|GW-BASIC}} {{works with\|Just BASIC}} {{works with\|PC-BASIC\|any}} {{works with\|QBasic}} <syntaxhighlight lang="qbasic">100 DIM LN$(19) 110 LN$(1) = "55" 120 LN$(2) = "94 48" 130 LN$(3) = "95 30 96" 140 LN$(4) = "77 71 26 67" 150 LN$(5) = "97 13 76 38 45" 160 LN$(6) = "07 36 79 16 37 68" 170 LN$(7) = "48 07 09 18 70 26 06" 180 LN$(8) = "18 72 79 46 59 79 29 90" 190 LN$(9) = "20 76 87 11 32 07 07 49 18" 200 LN$(10) = "27 83 58 35 71 11 25 57 29 85" 210 LN$(11) = "14 64 36 96 27 11 58 56 92 18 55" 220 LN$(12) = "02 90 03 60 48 49 41 46 33 36 47 23" 230 LN$(13) = "92 50 48 02 36 59 42 79 72 20 82 77 42" 240 LN$(14) = "56 78 38 80 39 75 02 71 66 66 01 03 55 72" 250 LN$(15) = "44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" 260 LN$(16) = "85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" 270 LN$(17) = "06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" 280 LN$(18) = "27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" 290 LN$(19) = "end" 300 DIM MATRIX(20,20) 310 X = 1 320 TAM = 0 330 FOR N = 1 TO 19 340 LN2$ = LN$(N) 350 FOR Y = 1 TO X 360 MATRIX(X,Y) = VAL(LEFT$(LN2$,2)) 370 IF LEN(LN2$) > 4 THEN LN2$ = MID$(LN2$,4,LEN(LN2$)-4) 380 NEXT Y 390 X = X+1 400 TAM = TAM+1 410 NEXT N 420 FOR Z = TAM-1 TO 1 STEP -1 430 FOR Y = 1 TO Z 440 S1 = MATRIX(Z+1,Y) 450 S2 = MATRIX(Z+1,Y+1) 460 IF S1 > S2 THEN MATRIX(Z,Y) = MATRIX(Z,Y)+S1 470 IF S1 <= S2 THEN MATRIX(Z,Y) = MATRIX(Z,Y)+S2 480 NEXT Y 490 NEXT Z 500 PRINT " maximum triangle path sum = ";MATRIX(1,1)</syntaxhighlight> {{out}} <pre> maximum triangle path sum = 1320</pre> ==={{header\|GW-BASIC}}=== The [[#Chipmunk Basic\|Chipmunk Basic]] solution works without any changes. ==={{header\|MSX Basic}}=== The [[#Chipmunk Basic\|Chipmunk Basic]] solution works without any changes. ==={{header\|PureBasic}}=== {{trans\|FreeBASIC}} <syntaxhighlight lang="PureBasic">OpenConsole() Dim ln.s(19) ln(1) = " 55" ln(2) = " 94 48" ln(3) = " 95 30 96" ln(4) = " 77 71 26 67" ln(5) = " 97 13 76 38 45" ln(6) = " 07 36 79 16 37 68" ln(7) = " 48 07 09 18 70 26 06" ln(8) = " 18 72 79 46 59 79 29 90" ln(9) = " 20 76 87 11 32 07 07 49 18" ln(10) = " 27 83 58 35 71 11 25 57 29 85" ln(11) = " 14 64 36 96 27 11 58 56 92 18 55" ln(12) = " 02 90 03 60 48 49 41 46 33 36 47 23" ln(13) = " 92 50 48 02 36 59 42 79 72 20 82 77 42" ln(14) = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72" ln(15) = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" ln(16) = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" ln(17) = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" ln(18) = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" ln(19) = "end" Dim matrix.i(20,20) Define.i x = 1, tam = 0 Define.i i, y, s1, s2, n For n = 1 To ArraySize(ln(),1) - 1 ln2.s = LTrim(ln(n)) For y = 1 To x matrix(x, y) = Val(Left(ln2, 2)) If Len(ln2) > 4: ln2 = Mid(ln2, 4, Len(ln2)-4) EndIf Next y x + 1 tam + 1 Next n For x = tam - 1 To 1 Step - 1 For y = 1 To x s1 = matrix(x+1, y) s2 = matrix(x+1, y+1) If s1 > s2: matrix(x, y) = matrix(x, y) + s1 Else matrix(x, y) = matrix(x, y) + s2 EndIf Next y Next x PrintN(#CRLF$ + " maximum triangle path sum = " + Str(matrix(1, 1))) Input() CloseConsole()</syntaxhighlight> {{out}} <pre> maximum triangle path sum = 1320</pre> ==={{header\|QBasic}}=== {{works with\|QBasic\|1.1}} The [[#Chipmunk Basic\|Chipmunk Basic]] solution works without any changes. ==={{header\|Run BASIC}}=== {{works with\|Just BASIC}} {{works with\|Liberty BASIC}} <syntaxhighlight lang="freebasic">dim ln$(19) ln$(1) = " 55" ln$(2) = " 94 48" ln$(3) = " 95 30 96" ln$(4) = " 77 71 26 67" ln$(5) = " 97 13 76 38 45" ln$(6) = " 07 36 79 16 37 68" ln$(7) = " 48 07 09 18 70 26 06" ln$(8) = " 18 72 79 46 59 79 29 90" ln$(9) = " 20 76 87 11 32 07 07 49 18" ln$(10) = " 27 83 58 35 71 11 25 57 29 85" ln$(11) = " 14 64 36 96 27 11 58 56 92 18 55" ln$(12) = " 02 90 03 60 48 49 41 46 33 36 47 23" ln$(13) = " 92 50 48 02 36 59 42 79 72 20 82 77 42" ln$(14) = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72" ln$(15) = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" ln$(16) = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" ln$(17) = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" ln$(18) = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" ln$(19) = "end" dim matrix(20,20) x = 1 tam = 0 for n = 1 to 19 'ubound(ln$) - 1 ln2$ = trim$(ln$(n)) for y = 1 to x matrix(x, y) = val(left$(ln2$, 2)) if len(ln2$) > 4 then ln2$ = mid$(ln2$, 4, len(ln2$)-4) next y x = x +1 tam = tam +1 next n for z = tam-1 to 1 step -1 for y = 1 to z s1 = matrix(z+1, y) s2 = matrix(z+1, y+1) if s1 > s2 then matrix(z, y) = matrix(z, y) +s1 else matrix(z, y) = matrix(z, y) +s2 end if next y next z print " maximum triangle path sum = "; matrix(1, 1)</syntaxhighlight> {{out}} <pre> maximum triangle path sum = 1320</pre> ==={{header\|True BASIC}}=== <syntaxhighlight lang="qbasic">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 DIM matrix(1 TO 20, 1 TO 20) LET x = 1 DO READ ln$ LET ln$ = LTRIM$(RTRIM$(ln$)) IF ln$ = "END" THEN EXIT DO FOR y = 1 TO x LET matrix(x, y) = VAL((ln$)[1:2]) LET ln$ = (ln$)[4:maxnum] NEXT y LET x = x+1 LET tam = tam+1 LOOP FOR x = tam-1 TO 1 STEP -1 FOR y = 1 TO x LET s1 = matrix(x+1, y) LET s2 = matrix(x+1, y+1) IF s1 > s2 THEN LET matrix(x, y) = matrix(x, y)+s1 ELSE LET matrix(x, y) = matrix(x, y)+s2 NEXT y NEXT x PRINT " maximum triangle path sum ="; matrix(1, 1) END</syntaxhighlight> {{out}} <pre> maximum triangle path sum = 1320</pre> ==={{header\|Yabasic}}=== <syntaxhighlight lang="freebasic">dim ln$(19) ln$(1) = " 55" ln$(2) = " 94 48" ln$(3) = " 95 30 96" ln$(4) = " 77 71 26 67" ln$(5) = " 97 13 76 38 45" ln$(6) = " 07 36 79 16 37 68" ln$(7) = " 48 07 09 18 70 26 06" ln$(8) = " 18 72 79 46 59 79 29 90" ln$(9) = " 20 76 87 11 32 07 07 49 18" ln$(10) = " 27 83 58 35 71 11 25 57 29 85" ln$(11) = " 14 64 36 96 27 11 58 56 92 18 55" ln$(12) = " 02 90 03 60 48 49 41 46 33 36 47 23" ln$(13) = " 92 50 48 02 36 59 42 79 72 20 82 77 42" ln$(14) = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72" ln$(15) = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" ln$(16) = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" ln$(17) = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" ln$(18) = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" ln$(19) = "end" dim matrix(20,20) x = 1 tam = 0 for n = 1 to arraysize(ln$(),1) - 1 ln2$ = trim$(ln$(n)) for y = 1 to x matrix(x, y) = val(left$(ln2$, 2)) if len(ln2$) > 4 ln2$ = mid$(ln2$, 4, len(ln2$)-4) next y x = x + 1 tam = tam + 1 next n for x = tam - 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) = matrix(x, y) + s1 else matrix(x, y) = matrix(x, y) + s2 end if next y next x print "\n maximum triangle path sum = ", matrix(1, 1)</syntaxhighlight> {{out}} <pre> maximum triangle path sum = 1320</pre> =={{header\|C}}== <syntaxhighlight 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(8len + 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; } </syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|C sharp\|C#}}== <syntaxhighlight lang="csharp"> using System; namespace RosetaCode { class MainClass { public static void Main (string[] args) { int[,] list = new int[18,19]; string input = @"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"; var charArray = input.Split ('\n'); for (int i=0; i < charArray.Length; i++) { var numArr = charArray[i].Trim().Split(' '); for (int j = 0; j<numArr.Length; j++) { int number = Convert.ToInt32 (numArr[j]); list [i, j] = number; } } for (int i = 16; i >= 0; i--) { for (int j = 0; j < 18; j++) { list[i,j] = Math.Max(list[i, j] + list[i+1, j], list[i,j] + list[i+1, j+1]); } } Console.WriteLine (string.Format("Maximum total: {0}", list [0, 0])); } } } </syntaxhighlight> {{out}} <pre>Maximum total: 1320</pre> =={{header\|C++}}== {{trans\|Ada}} <syntaxhighlight lang="cpp"> / Algorithm complexity: nlog(n) / #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+1)) / 2; ++k) // from the start to the end of row triangle[k] += std::max(triangle[k + n], triangle[k + n + 1]); std::cout << "Maximum total: " << triangle[0] << "\n\n"; } </syntaxhighlight> {{out}} <pre>Maximum total: 1320</pre> =={{header\|Clojure\|ClojureScript}}== <syntaxhighlight lang="clojure"> (ns clojure.examples.rosetta (:gen-class) (:require [clojure.string :as string])) (def rosetta "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") ;; The technique is described here in more detail http://mishadoff.com/blog/clojure-euler-problem-018/ ;; Most of the code converts the string data to a nested array of integers. ;; The code to calculate the max sum is then only a single line ;; First convert string data to nested list ;; with each inner list containing one row of the triangle ;; [[55] [94 48] [95 30 96] ... [...10 69 93] (defn parse-int [s] " Convert digits to a number (finds digits when could be surrounded by non-digits" (Integer. (re-find #"\d+" s))) (defn data-int-array [s] " Convert string to integer array" (map parse-int (string/split (string/trim s) #"\s+"))) (defn nested-triangle [s] " Convert triangle to nested vector, with each inner vector containing one triangle row" (loop [lst s n 1 newlist nil] (if (empty? lst) (reverse newlist) (recur (drop n lst) (inc n) (cons (take n lst) newlist))))) ; Create nested list (def nested-list (nested-triangle (data-int-array rosetta))) ;; Function to compute maximum path sum (defn max-sum [s] " Compute maximum path sum using a technique described here: http://mishadoff.com/blog/clojure-euler-problem-018/" (reduce (fn [a b] (map + b (map max a (rest a)))) (reverse s))) ; Print result (println (max-sum nested-list)) </syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|Common Lisp}}== <syntaxhighlight 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)))</syntaxhighlight> {{Out}} <pre>321 1320</pre> =={{header\|D}}== <~~lang~~syntaxhighlight lang="d">void main() { import std.stdio, std.algorithm, std.range, std.file, std.conv; Line 89 ⟶ 1,369: .array)[0] .writeln; }</~~lang~~syntaxhighlight> {{out}} <pre>1320</pre> =={{~~Header~~header\|GoEasyLang}}== <syntaxhighlight> ~~<lang go>package main~~ a[] = [ 0 0 ] repeat s$ = input until s$ = "" i = 1 while substr s$ i 1 = " " i += 1 . s$ = "0 " & substr s$ i 999 & " 0" b[] = number strsplit s$ " " for i = 2 to len b[] - 1 b[i] = higher (b[i] + a[i - 1]) (b[i] + a[i]) . swap a[] b[] . for v in a[] max = higher max v . print max # input_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 </syntaxhighlight> =={{header\|Elena}}== {{trans\|C#}} ELENA 6.x : <syntaxhighlight lang="elena">import system'routines; import extensions; import extensions'math; string input = "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"; public program() { var list := IntMatrix.allocate(18,19); int i := 0; int j := 0; input.splitBy(newLineConstant).forEach::(string line) { j := 0; line.trim().splitBy(" ").forEach::(string num) { list[i][j] := num.toInt(); j += 1 }; i += 1 }; for(int i := 16; i >= 0; i-=1) { for(int j := 0; j < 18; j += 1) { list[i][j] := max(list[i][j] + list[i+1][j], list[i][j] + list[i+1][j+1]) } }; console.printLine("Maximum total: ", list[0][0]) }</syntaxhighlight> {{out}} <pre> Maximum total: 1320 </pre> =={{header\|Elixir}}== <syntaxhighlight lang="elixir">defmodule Maximum do def triangle_path(text) do text \|> String.split("\n", trim: true) \|> Enum.map(fn line -> line \|> String.split() \|> Enum.map(&String.to_integer(&1)) end) \|> Enum.reduce([], fn x,total -> [0]++total++[0] \|> Enum.chunk_every( 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) </syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|Erlang}}== Reads the data from the file "triangle.txt" <syntaxhighlight lang="erlang"> -mode(compile). -import(lists, [foldl/3]). main(_) -> {ok, Tmat} = file:open("triangle.txt", [read, raw, {read_ahead, 16384}]), Max = max_sum(Tmat, []), io:format("The maximum total is ~b~n", [Max]). max_sum(FD, Last) -> case file:read_line(FD) of eof -> foldl(fun erlang:max/2, 0, Last); {ok, Line} -> Current = [binary_to_integer(B) \|\| B <- re:split(Line, "[ \n]"), byte_size(B) > 0], max_sum(FD, fold_row(Last, Current)) end. % The first argument has one more element than the second, so compute % the initial sum so that both lists have identical length for fold_rest(). fold_row([], L) -> L; fold_row([A\|_] = Last, [B\|Bs]) -> [A+B \| fold_rest(Last, Bs)]. % Both lists must have same length fold_rest([A], [B]) -> [A+B]; fold_rest([A1 \| [A2\|_] = As], [B\|Bs]) -> [B + max(A1,A2) \| fold_rest(As, Bs)]. </syntaxhighlight> {{Out}} <pre> The maximum total is 1320 </pre> =={{header\|ERRE}}== <syntaxhighlight 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(8LUNG+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 </syntaxhighlight> =={{header\|F_Sharp\|F#}}== <syntaxhighlight lang="fsharp"> // Maximum triangle path sum. Nigel Galloway: October 23rd., 2023 let g=[[27;02;92;23;08;71;76;84;15;52;92;63;81;10;44;10;69;93];[06;71;28;75;94;48;37;10;23;51;06;48;53;18;74;98;15];[85;32;25;85;57;48;84;35;47;62;17;01;01;99;89;52];[44;25;67;84;71;67;11;61;40;57;58;89;40;56;36];[56;78;38;80;39;75;02;71;66;66;01;03;55;72];[92;50;48;02;36;59;42;79;72;20;82;77;42];[02;90;03;60;48;49;41;46;33;36;47;23];[14;64;36;96;27;11;58;56;92;18;55];[27;83;58;35;71;11;25;57;29;85];[20;76;87;11;32;07;07;49;18];[18;72;79;46;59;79;29;90];[48;07;09;18;70;26;06];[07;36;79;16;37;68];[97;13;76;38;45];[77;71;26;67];[95;30;96];[94;48];[55]] let fG n g=List.map2(fun (n1,n2) g->(max n1 n2)+g) (n\|>List.pairwise) g let rec fN=function n::g::t->fN ((fG n g)::t) \|n::_->List.head n printfn "%d" (fN g) </syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|Factor}}== <syntaxhighlight lang="factor">USING: grouping.extras io.encodings.utf8 io.files kernel math.order math.parser math.vectors prettyprint sequences splitting ; IN: rosetta-code.maximum-triangle-path-sum : parse-triangle ( path -- seq ) utf8 file-lines [ " " split harvest ] map [ [ string>number ] map ] map ; : max-triangle-path-sum ( seq -- n ) <reversed> unclip-slice [ swap [ max ] 2clump-map v+ ] reduce first ; "triangle.txt" parse-triangle max-triangle-path-sum .</syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|Forth}}== <syntaxhighlight lang="forth"> \ 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 .</syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|Fortran}}== This being Fortran, why not a brute-force scan of all possible paths? This is eased by noting that from a given position, only two numbers are accessible, and always two numbers. Just like binary digits. So, for three levels, the choices would be 000, 001, 010, 011, 100, 101, 110, 111 or somesuch. Since however the pinnacle of the pyramid is always chosen, there is no choice there so the digits would be 100, 101, 110, 111. A triangular array can be defined in some languages, and in some circumstances a square array is used with a lower triangle and upper triangle partition, but here, a simple linear array is in order, with some attention to subscript usage. The first layer has one number, the second has two, the third has three, ... easy enough. The more refined method that determines the maximum sum without ascertaining the path through working upwards from the base employs a FOR ALL statement in adding the maximum of the two possible descendants to each brick in the current layer, employing array BEST that starts off with all the values of the bottom layer. As each layer is one value shorter than the one below and the expression computes <code>BEST(i) = ... + MAX(BEST(i),BEST(i + 1))</code> the special feature of the FORALL statement, that ''all'' rhs expressions are evaluated before ''any'' results are placed on the lhs is not needed if a DO-loop were to be used instead. For input, free-format is convenient. Bad input still is a problem, and can lead to puzzles. If say when N values are to be read but an input line is short of numbers, then additional lines will be read and confusion is likely. So, read the file's record into a text variable and then extract the expected N values from that. Should a problem arise, then the troublesome record can be shown. <syntaxhighlight lang="fortran"> MODULE PYRAMIDS !Produces a pyramid of numbers in 1-D array. INTEGER MANY !The usual storage issues. PARAMETER (MANY = 666) !This should suffice. INTEGER BRICK(MANY),IN,LAYERS !Defines a pyramid. CONTAINS SUBROUTINE IMHOTEP(PLAN)!The architect. Counting is from the apex down, the Erich von Daniken construction. CHARACTER() PLAN !The instruction file. INTEGER I,IT !Steppers. CHARACTER666 ALINE !A scratchpad for input. IN = 0 !No bricks. LAYERS = 0 !In no courses. WRITE (6,) "Reading from ",PLAN !Here we go. OPEN(10,FILE=PLAN,FORM="FORMATTED",ACTION="READ",ERR=6) !I hope. GO TO 10 !Why can't OPEN be a function?@&%#^%! 6 STOP "Can't grab the file!" Chew into the plan. 10 READ (10,11,END = 20) ALINE !Get the whole line in one piece. 11 FORMAT (A) !As plain text. IF (ALINE .EQ. "") GO TO 10 !Ignoring any blank lines. IF (ALINE(1:1).EQ."%") GO TO 10 !A comment opportunity. LAYERS = LAYERS + 1 !Righto, this should be the next layer. IF (IN + LAYERS.GT.MANY) STOP "Too many bricks!" !Perhaps not. READ (ALINE,,END = 15,ERR = 15) BRICK(IN + 1:IN + LAYERS) !Free format. IN = IN + LAYERS !Insufficient numbers will provoke trouble. GO TO 10 !Extra numbers/stuff will be ignored. Caught a crab? A bad number, or too few numbers on a line? No read-next-record antics, thanks. 15 WRITE (6,16) LAYERS,ALINE !Just complain. 16 FORMAT ("Bad layer ",I0,": ",A) Completed the plan. 20 WRITE (6,21) IN,LAYERS !Announce some details. 21 FORMAT (I0," bricks in ",I0," layers.") CLOSE(10) !Finished with input. Cast forth the numbers in a nice pyramid. 30 IT = 0 !For traversing the pyramid. DO I = 1,LAYERS !Each course has one more number than the one before. WRITE (6,31) BRICK(IT + 1:IT + I) !Sweep along the layer. 31 FORMAT (<LAYERS2 - 2I>X,666I4) !Leading spaces may be zero in number. IT = IT + I !Thus finger the last of a layer. END DO !On to the start of the next layer. END SUBROUTINE IMHOTEP !The pyramid's plan is ready. SUBROUTINE TRAVERSE !Clamber around the pyramid. Thoroughly. C The idea is that a pyramid of numbers is provided, and then, starting at the peak, c work down to the base summing the numbers at each step to find the maximum value path. c The constraint is that from a particular brick, only the two numbers below left and below right c may be reached in stepping to that lower layer. c Since that is a 0/1 choice, recorded in MOVE, a base-two scan searches the possibilities. INTEGER MOVE(LAYERS) !Choices are made at the various positions. INTEGER STEP(LAYERS),WALK(LAYERS) !Thus determining the path. INTEGER I,L,IT !Steppers. INTEGER PS,WS !Scores. WRITE (6,1) LAYERS !Announce the intention. 1 FORMAT (//,"Find the highest score path across a pyramid of ", 1 I0," layers."/) !I'm not worrying over singular/plural. MOVE = 0 !All 0/1 values to zero. MOVE(1) = 1 !Except the first. STEP(1) = 1 !Every path starts here, without option. WS = -666 !The best score so far. Commence a multi-level loop, using the values of MOVE as the digits, one digit per level. 10 IT = 1 !All paths start with the first step. PS = BRICK(1) !The starting score,. c write (6,8) "Move",MOVE,WS DO L = 2,LAYERS !Deal with the subsequent layers. IT = IT + L - 1 + MOVE(L) !Choose a brick. STEP(L) = IT !Remember this step. PS = PS + BRICK(IT) !Count its score. c WRITE (6,6) L,IT,BRICK(IT),PS 6 FORMAT ("Layer ",I0,",Brick(",I0,")=",I0,",Sum=",I0) END DO !Thus is the path determined. IF (PS .GT. WS) THEN !An improvement? IF (WS.GT.0) WRITE (6,7) WS,PS !Yes! Announce. 7 FORMAT ("Improved path score: ",I0," to ",I0) WRITE (6,8) "Moves",MOVE !Show the choices at each layer.. WRITE (6,8) "Steps",STEP !That resulted in this path. WRITE (6,8) "Score",BRICK(STEP) !Whose steps were scored thus. 8 FORMAT (A8,666I4) !This should suffice. WS = PS !Record the new best value. WALK = STEP !And the path thereby. END IF !So much for an improvement. DO L = LAYERS,1,-1 !Now add one to the number in MOVE. IF (MOVE(L).EQ.0) THEN !By finding the lowest order zero. MOVE(L) = 1 !Making it one, MOVE(L + 1:LAYERS) = 0 !And setting still lower orders back to zero. GO TO 10 !And if we did, there's more to do! END IF !But if that bit wasn't zero, END DO !Perhaps the next one up will be. WRITE (6,) WS," is the highest score." !So much for that. END SUBROUTINE TRAVERSE !All paths considered... SUBROUTINE REFINE !Ascertain the highest score without searching. INTEGER BEST(LAYERS) !A scratchpad. INTEGER I,L !Steppers. L = LAYERS(LAYERS - 1)/2 + 1 !Finger the first brick of the lowest layer. BEST = BRICK(L:L + LAYERS - 1)!Syncopation. Copy the lowest layer. DO L = LAYERS - 1,1,-1 !Work towards the peak. FORALL (I = 1:L) BEST(I) = BRICK(L(L - 1)/2 + I) !Add to each brick's value 1 + MAXVAL(BEST(I:I + 1)) !The better of its two possibles. END DO !On to the next layer. WRITE (6,) BEST(1)," is the highest score. By some path." END SUBROUTINE REFINE !Who knows how we get there. END MODULE PYRAMIDS PROGRAM TRICKLE USE PYRAMIDS c CALL IMHOTEP("Sakkara.txt") CALL IMHOTEP("Cheops.txt") CALL TRAVERSE !Do this the definite way. CALL REFINE !Only the result by more cunning. END </syntaxhighlight> Output: <pre> Reading from Cheops.txt 171 bricks in 18 layers. 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 Find the highest score path across a pyramid of 18 layers. Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 154 Score 55 94 95 77 97 7 48 18 20 27 14 2 92 56 44 85 6 27 Improved path score: 864 to 904 Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 138 155 Score 55 94 95 77 97 7 48 18 20 27 14 2 92 56 44 85 71 2 Improved path score: 904 to 994 Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 138 156 Score 55 94 95 77 97 7 48 18 20 27 14 2 92 56 44 85 71 92 Improved path score: 994 to 1041 Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 93 108 124 141 159 Score 55 94 95 77 97 7 48 18 20 27 14 2 92 78 67 85 94 71 Improved path score: 1041 to 1087 Moves 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 Steps 1 2 4 7 11 16 22 29 37 46 56 68 80 93 108 124 141 159 Score 55 94 95 77 97 7 48 18 20 27 14 90 50 78 67 85 94 71 Improved path score: 1087 to 1104 Moves 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 Steps 1 2 4 7 11 16 22 29 37 46 56 68 81 95 109 124 141 159 Score 55 94 95 77 97 7 48 18 20 27 14 90 48 80 84 85 94 71 Improved path score: 1104 to 1137 Moves 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 Steps 1 2 4 7 11 16 22 29 37 46 57 68 80 93 108 124 141 159 Score 55 94 95 77 97 7 48 18 20 27 64 90 50 78 67 85 94 71 Improved path score: 1137 to 1154 Moves 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 Steps 1 2 4 7 11 16 22 29 37 46 57 68 81 95 109 124 141 159 Score 55 94 95 77 97 7 48 18 20 27 64 90 48 80 84 85 94 71 Improved path score: 1154 to 1193 Moves 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 Steps 1 2 4 7 11 16 22 29 37 47 57 68 80 93 108 124 141 159 Score 55 94 95 77 97 7 48 18 20 83 64 90 50 78 67 85 94 71 Improved path score: 1193 to 1210 Moves 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 Steps 1 2 4 7 11 16 22 29 37 47 57 68 81 95 109 124 141 159 Score 55 94 95 77 97 7 48 18 20 83 64 90 48 80 84 85 94 71 Improved path score: 1210 to 1249 Moves 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 Steps 1 2 4 7 11 16 22 29 38 47 57 68 80 93 108 124 141 159 Score 55 94 95 77 97 7 48 18 76 83 64 90 50 78 67 85 94 71 Improved path score: 1249 to 1266 Moves 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 Steps 1 2 4 7 11 16 22 29 38 47 57 68 81 95 109 124 141 159 Score 55 94 95 77 97 7 48 18 76 83 64 90 48 80 84 85 94 71 Improved path score: 1266 to 1303 Moves 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 Steps 1 2 4 7 11 16 22 30 38 47 57 68 80 93 108 124 141 159 Score 55 94 95 77 97 7 48 72 76 83 64 90 50 78 67 85 94 71 Improved path score: 1303 to 1320 Moves 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 Steps 1 2 4 7 11 16 22 30 38 47 57 68 81 95 109 124 141 159 Score 55 94 95 77 97 7 48 72 76 83 64 90 48 80 84 85 94 71 1320 is the highest score. 1320 is the highest score. By some path. </pre> =={{header\|FreeBASIC}}== <syntaxhighlight 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 <> "" : Wend Print : Print "hit any key to end program" Sleep End</syntaxhighlight> {{out}}<pre> maximum triangle path sum = 1320</pre> =={{header\|Go}}== <syntaxhighlight lang="go">package main import ( Line 148 ⟶ 2,025: } fmt.Println(d[0]) }</~~lang~~syntaxhighlight> {{Out}} <pre> Line 155 ⟶ 2,032: =={{header\|Haskell}}== <~~lang~~syntaxhighlight 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~~syntaxhighlight> {{out}} <pre>1320</pre> Or, inlining the data for quick testing, and using an applicative expression: <syntaxhighlight lang="haskell">---------------- MAXIMUM TRIANGLE PATH SUM --------------- maxPathSum :: [[Int]] -> Int maxPathSum = head . foldr1 ((<> tail) . zipWith3 (\x y z -> x + max y z)) --------------------------- TEST ------------------------- main :: IO () main = print $ maxPathSum [ [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] ]</syntaxhighlight> {{Out}} <pre>1320</pre> ZipList variant: <syntaxhighlight lang="haskell">import Control.Applicative (ZipList (ZipList, getZipList)) ---------------- MAXIMUM TRIANGLE PATH SUM --------------- maxPathSum :: [[Int]] -> Int maxPathSum [] = 0 maxPathSum triangleRows = head ( foldr1 ( \xs -> ( \ys zs -> getZipList ( ( ( (\x y z -> x + max y z) <$> ZipList xs ) <> ZipList ys ) <> ZipList zs ) ) <> tail ) triangleRows ) --------------------------- TEST ------------------------- main :: IO () main = print $ maxPathSum [ [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] ]</syntaxhighlight> {{Out}} <pre>1320</pre> =={{header\|J}}== <~~lang~~syntaxhighlight lang="j">padTri=: 0 ". [: ];._2 ] NB. parse triangle and (implicitly) pad with zeros maxSum=: [: {. (+ (0 ,~ 2 >./\ ]))/ NB. find max triangle path sum</~~lang~~syntaxhighlight> '''Example Usage''' <~~lang~~syntaxhighlight lang="j"> maxSum padTri freads 'triangle.txt' 1320</~~lang~~syntaxhighlight> 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. <syntaxhighlight lang="j">maxsum=: ((] + #@] {. [)2 >./\ ])/</syntaxhighlight> 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.) =={{header\|Java}}== {{works with\|Java\|8}} <syntaxhighlight 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]); } }</syntaxhighlight> <pre>1320</pre> =={{header\|Javascript}}== ===ES5=== ====Imperative==== <syntaxhighlight 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); </syntaxhighlight> {{out}} <syntaxhighlight lang="javascript"> [ [ 1320 ] ] </syntaxhighlight> ====Functional==== {{trans\|Haskell}} <syntaxhighlight 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))) : []; } // Evaluating from bottom up (right fold) // and with recursion left to right (head and first item of tail at each stage) return foldr1( function (xs, ys) { return zipWith3( function (x, y, z) { return x + (y < z ? z : y); }, xs, ys, ys.slice(1) // item above, and larger of two 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] ] )[0]; })();</syntaxhighlight> {{out}} <syntaxhighlight lang="javascript">1320</syntaxhighlight> ===ES6=== ====Imperative==== <syntaxhighlight lang="javascript">function maximumTrianglePathSum(triangle) { function distilLastLine() { let lastLine = triangle.pop(), aboveLine = triangle.pop(); for (let i = 0; i < aboveLine.length; i++) aboveLine[i] = Math.max( aboveLine[i] + lastLine[i], aboveLine[i] + lastLine[i + 1] ); triangle.push(aboveLine); } do { distilLastLine(); } while (triangle.length > 1); return triangle[0][0]; } // testing let theTriangle = [ [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] ]; console.log(maximumTrianglePathSum(theTriangle));</syntaxhighlight> {{out}} <syntaxhighlight lang="javascript">1320</syntaxhighlight> ====Functional==== {{Trans\|Haskell}} <syntaxhighlight lang="javascript">(() => { "use strict"; // ------------------ MAX PATH SUM ------------------- // Working from the bottom of the triangle upwards, // summing each number with the larger of the two below // until the maximum emerges at the top. // maxPathSum ::[[Int]] -> Int const maxPathSum = xss => // A list of lists folded down to a list of just one // remaining integer. foldr1( // The accumulator, zipped with the tail of the // accumulator, yields pairs of adjacent sums. (ys, xs) => zipWith3( // Plus greater of two below (a, b, c) => a + Math.max(b, c) )(xs)(ys)(ys.slice(1)) )(xss)[0]; // ---------------- GENERIC FUNCTIONS ---------------- // foldr1 :: (a -> a -> a) -> [a] -> a const foldr1 = f => xs => 0 < xs.length ? ( xs.slice(0, -1).reduceRight( f, xs.slice(-1)[0] ) ) : []; // zipWith3 :: (a -> b -> c -> d) -> // [a] -> [b] -> [c] -> [d] const zipWith3 = f => xs => ys => zs => Array.from({ length: Math.min( ...[xs, ys, zs].map(x => x.length) ) }, (_, i) => f(xs[i], ys[i], zs[i])); // ---------------------- TEST ----------------------- return maxPathSum([ [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] ]); })();</syntaxhighlight> {{Out}} <pre>1320</pre> =={{header\|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 <tt>reduce</tt>. The input array is identical to that in the Javascript section and is therefore omitted here.<syntaxhighlight 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] ) ) ;</syntaxhighlight> =={{header\|Julia}}== {{works with\|Julia\|0.6}} <syntaxhighlight lang="julia"># dynamic solution function maxpathsum(t::Array{Array{I, 1}, 1}) where I T = deepcopy(t) for r in length(T)-1:-1:1 for c in linearindices(T[r]) T[r][c] += max(T[r+1][c], T[r+1][c+1]) end end return T[1][1] end test = [[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]] @show maxpathsum(test)</syntaxhighlight> {{out}} <pre>maxpathsum(test) = 1320</pre> =={{header\|Kotlin}}== {{trans\|C}} <syntaxhighlight lang="scala">// version 1.1.2 val tri = intArrayOf( 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 ) fun main(args: Array<String>) { val triangles = arrayOf(tri.sliceArray(0..9), tri) for (triangle in triangles) { val size = triangle.size val base = ((Math.sqrt(8.0 size + 1.0) - 1.0)/ 2.0).toInt() var step = base - 1 var stepc = 0 for (i in (size - base - 1) downTo 0) { triangle[i] += maxOf(triangle[i + step], triangle[i + step + 1]) if (++stepc == step) { step-- stepc = 0 } } println("Maximum total = ${triangle[0]}") } }</syntaxhighlight> {{out}} <pre> Maximum total = 321 Maximum total = 1320 </pre> =={{header\|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. <syntaxhighlight 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)) </syntaxhighlight> {{out}} <pre>321 1320</pre> =={{header\|Mathematica}}/{{header\|Wolfram Language}}== <syntaxhighlight 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]]]</syntaxhighlight> {{out}} <pre>MaximumTrianglePathSum[nums] 1320</pre> =={{header\|Nim}}== {{trans\|Python}} <syntaxhighlight lang="nim">import sequtils, strutils, sugar proc solve(tri: seq[seq[int]]): 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.strip.split.map parseInt) </syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|PARI/GP}}== <~~lang~~syntaxhighlight 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~~syntaxhighlight> {{out}} <pre>%1 = 1320</pre> =={{header\|Pascal}}== testet with freepascal, should run under Turbo Pascal, therefore using static array and val, and Delphi too. <syntaxhighlight 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.</syntaxhighlight> {{out}} <pre>height sum 18 1320 17 1249 .... 4 321 3 244 2 149 1 55</pre> =={{header\|Perl}}== <~~lang~~syntaxhighlight lang="perl">use 5.10.0; use List::Util 'max'; Line 189 ⟶ 2,751: } say max(@sum);</~~lang~~syntaxhighlight> {{out}} <pre> Line 195 ⟶ 2,757: 1320 </pre> ~~=={{header\|Perl 6}}==~~ The <tt>Z+</tt> and <tt>Zmax</tt> are examples of the zipwith metaoperator. We ought to be able to use <tt>[Z+]=</tt> as an assignment operator here, but rakudo has a bug. Note also we can use the <tt>Zmax</tt> metaoperator form because <tt>max</tt> is define as an infix in Perl 6. ~~<lang perl6>my @rows = slurp("triangle.txt").lines.map: { [.words] }~~ =={{header\|Phix}}== ~~while @rows > 1 {~~ <!--<syntaxhighlight lang="phix">(phixonline)--> ~~my @last := @rows.pop;~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~@rows[-1] = @rows[-1][] Z+ (@last Zmax @last[1..]);~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">tri</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">55</span><span style="color: #0000FF;">},</span> } <span style="color: #0000FF;">{</span><span style="color: #000000;">94</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">95</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">96</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">77</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">26</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">97</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">76</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">38</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">16</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">37</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">68</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">70</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">26</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">72</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">46</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">59</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">76</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">87</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">49</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">83</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">35</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">57</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">85</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">64</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">96</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">56</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">55</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">60</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">49</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">41</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">46</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">33</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">59</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">72</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">82</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">77</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">56</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">78</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">38</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">80</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">39</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">66</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">66</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">55</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">72</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">44</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">84</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">61</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">57</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">89</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">56</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">85</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">85</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">57</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">84</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">35</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">62</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">99</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">89</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">52</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">28</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">94</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">37</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">51</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">53</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">74</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">98</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">76</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">84</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">52</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">63</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">81</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">44</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">69</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">93</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- update each row from last but one upwards, with the larger -- child, so the first step is to replace 6 with 6+27 or 6+2.</span> <span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> <span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span> <span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">..</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <!--</syntaxhighlight>--> {{out}} <pre> 1320 </pre> =={{header\|Picat}}== ===Mode directed tabling=== <syntaxhighlight lang="picat">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].</syntaxhighlight> ===Loop based approach=== <syntaxhighlight lang="picat">pp2(Row, Column, Sum, Tri, M) => if Sum > M.get(max_val,0) then M.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, M) end end.</syntaxhighlight> ===Recursion=== {{trans\|Prolog}} <syntaxhighlight lang="picat">max_path(N, V) :- data(N, T), path(1, T, V). path(_N, [], 0) . path(N, [H \| T], V) :- nth(N, H, V0), N1 is N+1, path(N, T, V1), path(N1, T, V2), V = V0 + max(V1, V2). 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]].</syntaxhighlight> ===Test=== <syntaxhighlight lang="picat">import util. go => tri(Tri), println("Mode directed tabling:"), pp(1,1,Tri,Sum), writeln(max_val=Sum), nl, println("Loop based:"), M = new_map([max_val=0]), pp2(1,1, Tri[1,1], Tri, M), writeln(max_val=M.get(max_val)), nl, println("Adapted the Prolog solution:"), max_path(2, V2), println(max_val=V2), nl. tri(Tri) => Tri = { {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} }.</syntaxhighlight> ~~say @rows;</lang>~~ {{out}} <pre>Mode directed tabling: ~~<pre>1320</pre>~~ max_val = 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, <tt>[op]</tt>, which turns any infix into a list operator.~~ ~~<lang perl6>sub infix:<op>(@a,@b) { (@a Zmax @a[1..]) Z+ @b }~~ Loop based: ~~say [op] slurp("triangle.txt").lines.reverse.map: { [.words] }</lang>~~ max_val = 1320 ~~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..]) }~~ Adapted the Prolog solution: ~~say [op] slurp("triangle.txt").lines.map: { [.words] }</lang>~~ max_val = 1320</pre> =={{header\|PicoLisp}}== {{trans\|Common Lisp}} <syntaxhighlight 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) ) )</syntaxhighlight> =={{header\|PL/I}}== {{trans\|REXX}} <syntaxhighlight 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;</syntaxhighlight> {{out}} <pre>maximum path sum: 1320</pre> =={{header\|Prolog}}== <syntaxhighlight 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]]. </syntaxhighlight> {{out}} <pre> ?- max_path(1, V). V = 321 . ?- max_path(2, V). V = 1320 . </pre> =={{header\|Python}}== A simple mostly imperative solution: <~~lang~~syntaxhighlight lang="python">def solve(tri): while len(tri) > 1: t0 = tri.pop() Line 225 ⟶ 3,030: return tri[0][0] ~~def main():~~ data = """\ 55 55 94 48 95 30 96 Line 246 ⟶ 3,050: 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()])</syntaxhighlight> ~~main()</lang>~~ {{out}} <pre>1320</pre> A more functional version, similar to the Haskell entry (same output): <~~lang~~syntaxhighlight 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~~syntaxhighlight> And, updating a little for Python 3 (in which ''itertools'' no longer defines '''imap''', and '''reduce''' now has to be imported from ''functools''), while inlining the data for ease of testing: {{Trans\|Haskell}} {{Trans\|JavaScript}} {{Works with\|Python\|3\|7}} <syntaxhighlight lang="python">'''Maximum triangle path sum''' from functools import (reduce) # maxPathSum :: [[Int]] -> Int def maxPathSum(rows): '''The maximum total among all possible paths from the top to the bottom row. ''' return reduce( lambda xs, ys: [ a + max(b, c) for (a, b, c) in zip(ys, xs, xs[1:]) ], reversed(rows[:-1]), rows[-1] )[0] # ------------------------- TEST ------------------------- print( maxPathSum([ [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] ]) )</syntaxhighlight> {{Out}} <pre>1320</pre> =={{header\|Quackery}}== <syntaxhighlight lang="Quackery"> [ [] swap behead swap witheach [ tuck max rot swap join swap ] drop ] is pairwise-max ( [ --> [ ) [ [] unrot witheach [ dip behead + rot swap join swap ] drop ] is add-items ( [ --> [ ) [ behead dip [ reverse behead pairwise-max swap witheach [ add-items pairwise-max ] ] add-items 0 peek ] is mtps ( [ --> n ) ' [ [ 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 ] ] mtps echo</syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|Racket}}== <~~lang~~syntaxhighlight lang="racket">#lang racket (require math/number-theory) Line 319 ⟶ 3,221: #(55 94 48 95 30 96 77 71 26 67)) (check-equal? (maximum-triangle-path-sum test-triangle) 321) )</~~lang~~syntaxhighlight> {{out}} <pre>1320</pre> =={{header\|Raku}}== (formerly Perl 6) {{works with\|Rakudo\|2018.03}} The <tt>Z+</tt> and <tt>Zmax</tt> are examples of the zipwith metaoperator. Note also we can use the <tt>Zmax</tt> metaoperator form because <tt>max</tt> is define as an infix in Perl 6. <syntaxhighlight lang="raku" line>my $triangle = q\| 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\|; my @rows = $triangle.lines.map: { [.words] } while @rows > 1 { my @last := @rows.pop; @rows[-1] = (@rows[-1][] Z+ (@last Zmax @last[1..])).List; } put @rows; # Here's a more FPish version. We define our own operator and the use it in the reduction metaoperator form, [op], which turns any infix into a list operator. sub infix:<op>(@a,@b) { (@a Zmax @a[1..]) Z+ @b } put [op] $triangle.lines.reverse.map: { [.words] } # Or, instead of using reverse, one could also define the op as right-associative. sub infix:<rop>(@a,@b) is assoc('right') { @a Z+ (@b Zmax @b[1..]) } put [rop] $triangle.lines.map: { [.words] }</syntaxhighlight> {{out}} <pre>1320 1320 1320</pre> =={{header\|REXX}}== The method used is very efficient and performs very well for triangles that have thousands of rows (lines). <br>For an expanded discussion of the program method's efficiency, see the discussion page. <~~lang~~syntaxhighlight lang="rexx">/REXX program finds the ~~max~~ maximum sum of a ~~"column"~~ path of numbers in a ~~triangle~~pyramid of numbers. / @.=.; @.1 = 55 ~~@. =~~ @.12 = 94 5548 @.23 = 9495 30 4896 @.34 = 77 9571 3026 9667 @.45 = 7797 13 7176 2638 6745 @.56 = 07 9736 1379 7616 3837 4568 @.67 = 48 07 3609 7918 1670 3726 6806 @.78 = 18 4872 0779 0946 1859 7079 2629 0690 @.89 = 1820 7276 7987 4611 5932 7907 2907 9049 18 @.9 10 = 27 2083 7658 8735 1171 3211 0725 0757 4929 1885 @.1011 = 2714 8364 5836 3596 7127 11 2558 56 5792 2918 8555 @.1112 = 02 1490 6403 3660 9648 2749 1141 5846 5633 9236 1847 5523 @.1213 = 0292 9050 0348 6002 4836 4959 4142 4679 3372 3620 82 4777 2342 @.1314 = 56 9278 5038 4880 0239 3675 5902 4271 7966 7266 2001 8203 7755 4272 @.1415 = 5644 7825 3867 8084 3971 7567 0211 7161 6640 6657 0158 0389 5540 56 7236 @.1516 = 85 4432 25 6785 8457 7148 6784 1135 6147 4062 5717 5801 8901 4099 5689 3652 @.1617 = 8506 3271 2528 8575 5794 48 8437 3510 4723 6251 1706 48 0153 0118 9974 8998 5215 @.1718 = 27 0602 7192 2823 7508 9471 4876 3784 1015 2352 5192 0663 4881 5310 1844 7410 9869 1593 #.=0 ~~@.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 another version of the pyramid./ do k=1 for r; #.r.k=word(@.r, k) /assign a number to an array number. / end /k/ end /r/ do do r=r-1 ~~while~~by -1 ~~@.r\==''~~ to 2; p=r-1 /~~build~~traipse athrough the pyramid rows. ~~version~~ of ~~the~~ ~~triangle~~/ do k=1 for ~~words(@.r)~~p; ~~/build~~ a ~~row,~~ ~~number~~ by ~~number.~~ _=k+1 /re─calculate the previous pyramid row/ #.rp.k=~~word~~max(@#.r,.k, #.r._) + #.p.k /~~assign~~replace athe previous number. to an ~~array~~ ~~num~~/ end /k/ end /r/ ~~rows=r-1~~ /~~compute~~stick ~~the~~a ~~number~~fork ofin ~~rows.~~it, we're all done. / say 'maximum path sum: ' #.1.1 /show the top (row 1) pyramid number. /</syntaxhighlight> ~~do r=rows by -1 to 2; p=r-1 /traipse through triangle rows. /~~ '''output'''   using the data within the REXX program: ~~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:~~ <pre> maximum path sum: 1320 </pre> =={{header\|Ring}}== <syntaxhighlight lang="ring"> # Project : Maximum triangle path sum load "stdlib.ring" ln = list(19) ln[1] = " 55" ln[2] = " 94 48" ln[3] = " 95 30 96" ln[4] = " 77 71 26 67" ln[5] = " 97 13 76 38 45" ln[6] = " 07 36 79 16 37 68" ln[7] = " 48 07 09 18 70 26 06" ln[8] = " 18 72 79 46 59 79 29 90" ln[9] = " 20 76 87 11 32 07 07 49 18" ln[10] = " 27 83 58 35 71 11 25 57 29 85" ln[11] = " 14 64 36 96 27 11 58 56 92 18 55" ln[12] = " 02 90 03 60 48 49 41 46 33 36 47 23" ln[13] = " 92 50 48 02 36 59 42 79 72 20 82 77 42" ln[14] = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72" ln[15] = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36" ln[16] = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52" ln[17] = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15" ln[18] = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93" ln[19] = "end" matrix = newlist(20,20) x = 1 size = 0 for n = 1 to len(ln) - 1 ln2 = ln[n] ln2 = trim(ln2) for y = 1 to x matrix[x][y] = number(left(ln2,2)) if len(ln2) > 4 ln2 = substr(ln2,4,len(ln2)-4) ok next x = x + 1 size = size + 1 next 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 matrix[x][y] = matrix[x][y] + s1 else matrix[x][y] = matrix[x][y] + s2 ok next next see "maximum triangle path sum = " + matrix[1][1] </syntaxhighlight> Output: <pre> maximum triangle path sum = 1320 </pre> =={{header\|RPL}}== {{works with\|HP\|48G}} « DUP TAIL 0 + « MAX » DOLIST 1 OVER SIZE 1 - SUB » '<span style="color:blue">MAX2L</span>' STO « → t « t SIZE LASTARG OVER GET SWAP 1 - 1 '''FOR''' j <span style="color:blue">MAX2L</span> t j GET ADD -1 '''STEP''' HEAD » » '<span style="color:blue">P018</span>' STO {{ 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 }} <span style="color:blue">P018</span> {{out}} <pre> 1: 1320 </pre> =={{header\|Ruby}}== <syntaxhighlight lang="ruby">triangle = ~~<lang ruby>~~ ~~triangle =~~ " 55 94 48 Line 386 ⟶ 3,432: 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)} puts ar.inject([]){\|res,x\| ~~until ar.size == 1 do~~ maxes = ~~ar.pop~~[0, res, 0].each_cons(2).map(&:max) ~~ar[-1]= ar[-1]~~x.zip(maxes).~~flat_map~~map{\|r1a,r2b\| r1 a+ r2b} }.max ~~end~~ ~~puts ar~~ # => 1320</~~lang~~syntaxhighlight> =={{header\|Rust}}== {{works with\|Rust\|1.3}} <syntaxhighlight 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 }</syntaxhighlight> =={{header\|Scala}}== <syntaxhighlight 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"))) }</syntaxhighlight> {{out}} <pre>321 1320</pre> =={{header\|Sidef}}== {{trans\|Perl}} Iterative solution: <syntaxhighlight lang="ruby">var sum = [0] ARGF.each { \|line\| var x = line.words.map{.to_n} sum = [ x.first + sum.first, 1 ..^ x.end -> map{\|i\| x[i] + [sum[i-1, i]].max}..., x.last + sum.last, ] } say sum.max</syntaxhighlight> Recursive solution: <syntaxhighlight lang="ruby">var triangle = ARGF.slurp.lines.map{.words.map{.to_n}} 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()</syntaxhighlight> {{out}} <pre>% sidef maxpath.sf triangle.txt 1320</pre> =={{header\|Stata}}== <syntaxhighlight lang="stata">import delimited triangle.txt, delim(" ") clear mata a = st_data(.,.) n = rows(a) for (i=n-1; i>=1; i--) { for (j=1; j<=i; j++) { a[i,j] = a[i,j]+max((a[i+1,j],a[i+1,j+1])) } } a[1,1] end</syntaxhighlight> '''Output''' <pre>1320</pre> =={{header\|Tcl}}== {{works with\|Tcl\|8.6}} <~~lang~~syntaxhighlight lang="tcl">package require Tcl 8.6 proc maxTrianglePathSum {definition} { Line 439 ⟶ 3,610: 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~~syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|VBScript}}== <syntaxhighlight 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 </syntaxhighlight> {{In}} Input file <pre> 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 </pre> {{Out}} <pre>1320</pre> =={{header\|Wren}}== {{trans\|Go}} <syntaxhighlight lang="wren">var lines = [ " 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" ] var f = lines[-1].split(" ") var d = f.map { \|s\| Num.fromString(s) }.toList for (row in lines.count-2..0) { var l = d[0] var i = 0 for (s in lines[row].trimStart().split(" ")) { var u = Num.fromString(s) var r = d[i+1] d[i] = (l > r) ? u + l : u + r l = r i = i + 1 } } System.print(d[0])</syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|XPL0}}== {{trans\|Ada}} <syntaxhighlight lang "XPL0">function Max(A, B); int A, B; return if A > B then A else B; int Triangle, Last, Tn, N, I; begin Triangle:= [0, 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 := (1818+18)/2; Tn := 1; while (Tn * (Tn + 1) / 2) < Last do Tn := Tn + 1; for N:= Tn downto 2 do begin for I:= 2 to N do begin Triangle (Last - N) := Triangle (Last - N) + Max(Triangle (Last - 1), Triangle (Last)); Last := Last - 1; end; Last := Last - 1; end; IntOut(0, Triangle(1)); CrLf(0); end;</syntaxhighlight> {{out}} <pre> 1320 </pre> =={{header\|Z80 Assembly}}== {{works with\|CP/M 3.1\|YAZE-AG-2.51.2 Z80 emulator}} {{works with\|ZSM4 macro assembler\|YAZE-AG-2.51.2 Z80 emulator}} Use the /S8 switch on the ZSM4 assembler for 8 significant characters for labels and names<br><br> No attempt is made to check for and handle incomplete triangles, and the number of elements must be defined in code.<br> <syntaxhighlight lang="z80"> ; ; Find maximum triangle path sum using Z80 assembly language ; ; Runs under CP/M 3.1 on YAZE-AG-2.51.2 Z80 emulator ; Assembled with zsm4 on same emulator/OS, uses macro capabilities of said assembler ; Created with vim under Windows ; ; Thanks to https://wikiti.brandonw.net for the idea for the conversion routine hl -> decimal ASCII ; ; ; 2023-04-28 Xorph ; ; ; Useful definitions ; bdos equ 05h ; Call to CP/M BDOS function strdel equ 6eh ; Set string delimiter wrtstr equ 09h ; Write string to console nul equ 00h ; ASCII control characters cr equ 0dh lf equ 0ah cnull equ '0' ; ASCII character constants trisize equ 171 ; Number of elements in triangle, must be counted manually - elements are 16 bit words ; ; Macros for BDOS calls ; setdel macro char ; Set string delimiter to char ld c,strdel ld e,char call bdos endm print macro msg ; Output string to console ld c,wrtstr ld de,msg call bdos endm newline macro ; Print newline ld c,wrtstr ld de,crlf call bdos endm pushall macro ; Save all registers to stack push af push bc push de push hl push ix push iy endm popall macro ; Recall all registers from stack pop iy pop ix pop hl pop de pop bc pop af endm ; ; ===================== ; Start of main program ; ===================== ; cseg ; ; The total number of elements in a triangle with N rows is the sum of the numbers 1..N, and we need to ; determine N for the given number of elements (trisize from above). ; Since the Z80 has no multiplication instruction, we can not use the Gauss formula N * (N + 1) / 2. Instead, we ; just sum up all the numbers beginning with 1, until we exceed the number of elements. ; ld a,trisize ; a holds number of elements for comparison ld de,1 ; de is the counter from 1..N ld hl,0 ; hl holds the accumulated sum. Since a must be used for comparison, we need hl as accumulator sum1toN: add hl,de ; Add next number to hl cp l ; Comparison is only 8 bit! The maximum number of elements is limited to 255 jr c,foundN ; If l exceeds trisize, we are finished and need to reduce de again inc de ; Otherwise, increase de and repeat jr sum1toN foundN: dec de ; We overshot the target and need to reduce de again. de now holds N, the number of rows = elements in last row ld b,e ; Our actual counters will be b and c ld ix,triangle ; Set ix to LSB of very last element (16 bit word) of triangle ld de,2trisize-2 add ix,de ; Everything is 0-based! Here we need the bytes instead of the number of elements push ix ; Set iy to last element of penultimate row pop hl ; Need to use hl for subtraction of number of bytes in last row ld c,b ; Get number of bytes in c, b shall keep the number of elements sla c ; bytes = 2 elements ld d,0 ; Use de for 16 bit subtraction of c from hl ld e,c sbc hl,de push hl ; and then move it to iy via stack, no direct load pop iy dec b ; b runs over the penultimate row, which has 1 element less ld c,b ; c is the row counter, b the element counter - each row contains as many elements as is its number loop: ; Loop entry point is the same for inner and outer loop push bc ; Save bc to stack, it will hold the maximum of right and left successor ld l,(ix) ; Right successor of iy ld h,(ix+1) ld e,(ix-2) ; Left successor of iy ld d,(ix-1) push hl ; Save hl, it is modified by the comparison/subtraction or a ; Clear carry flag sbc hl,de ; 16 bit comparison by subtracting left from right pop hl ; Restore hl jr c,delarger ; If carry, then the left successor in de is larger push hl ; hl is larger, move it to bc pop bc jr addmax delarger: push de ; de is larger, move it to bc pop bc addmax: ld l,(iy) ; Get "parent" element into hl and add maximum of its two successors ld h,(iy+1) add hl,bc ; Add maximum, which is in bc ld (iy),l ; Store hl back to triangle ld (iy+1),h pop bc ; Restore bc with loop counters dec ix ; Decrement element pointers (by 2 bytes) dec ix dec iy dec iy dec b ; Decrement element counter jp nz,loop ; Check if penultimate row finished - this is the inner loop ld b,c ; Restore inner loop counter, check if more rows above current dec ix ; Decrement element pointer of row below again (by 2 bytes), skip leftmost element dec ix dec b ; Decrement loop counters, first the element counter dec c ; ...then the row counter jp nz,loop ; Check if triangle finished - this is the outer loop ld hl,(triangle) ; Root element now contains maximum sum ld ix,buffer ; Set ix to output buffer call dispHL ; Create decimal representation setdel nul ; Set string delimiter to 00h print buffer ; Display result newline ret ; Return to CP/M ; ; =================== ; End of main program ; =================== ; ; ; Helper routines - notice that the Z80 does not have a divide instruction ; Notice further that CP/M does not have any support for pretty-printing ; formatted numbers and stuff like that. So we have to do all this by hand... ; ; ; Converts the value (unsigned int) in register hl to its decimal representation ; Register ix has memory address of target for converted value ; String is terminated with nul character (\0) ; dispHL: pushall ld b,1 ; Flag for leading '0' irp x,<-10000,-1000,-100,-10,-1> ld de,x ; Subtract powers of 10 and determine digit call calcdig endm ld a,nul ; Terminate result string with nul ld (ix+0),a popall ret ; End of conversion routine calcdig: ld a,cnull-1 ; Determine the digit character incrdig: inc a ; Start with '0' add hl,de ; As long as subtraction is possible, increment digit character jr c,incrdig sbc hl,de ; If negative, undo last subtraction and continue with remainder cp cnull ; Check for leading '0', these are ignored jr nz,adddig bit 0,b ; Use bit instruction for check if flag set, register a contains digit ret nz ; If '0' found and flag set, it is a leading '0' and we return adddig: ld b,0 ; Reset flag for leading '0', we are now outputting digits ld (ix+0),a ; Store character in memory and set ix to next location inc ix ret ; End of conversion helper routine ; ; ================ ; Data definitions ; ================ ; dseg crlf: defb cr,lf,nul ; Generic newline buffer: defs 10 ; Buffer for conversion of number to text triangle: ; Triangle data, number of elements is "trisize" equ further above defw 55 defw 94 defw 48 defw 95 defw 30 defw 96 defw 77 defw 71 defw 26 defw 67 defw 97 defw 13 defw 76 defw 38 defw 45 defw 07 defw 36 defw 79 defw 16 defw 37 defw 68 defw 48 defw 07 defw 09 defw 18 defw 70 defw 26 defw 06 defw 18 defw 72 defw 79 defw 46 defw 59 defw 79 defw 29 defw 90 defw 20 defw 76 defw 87 defw 11 defw 32 defw 07 defw 07 defw 49 defw 18 defw 27 defw 83 defw 58 defw 35 defw 71 defw 11 defw 25 defw 57 defw 29 defw 85 defw 14 defw 64 defw 36 defw 96 defw 27 defw 11 defw 58 defw 56 defw 92 defw 18 defw 55 defw 02 defw 90 defw 03 defw 60 defw 48 defw 49 defw 41 defw 46 defw 33 defw 36 defw 47 defw 23 defw 92 defw 50 defw 48 defw 02 defw 36 defw 59 defw 42 defw 79 defw 72 defw 20 defw 82 defw 77 defw 42 defw 56 defw 78 defw 38 defw 80 defw 39 defw 75 defw 02 defw 71 defw 66 defw 66 defw 01 defw 03 defw 55 defw 72 defw 44 defw 25 defw 67 defw 84 defw 71 defw 67 defw 11 defw 61 defw 40 defw 57 defw 58 defw 89 defw 40 defw 56 defw 36 defw 85 defw 32 defw 25 defw 85 defw 57 defw 48 defw 84 defw 35 defw 47 defw 62 defw 17 defw 01 defw 01 defw 99 defw 89 defw 52 defw 06 defw 71 defw 28 defw 75 defw 94 defw 48 defw 37 defw 10 defw 23 defw 51 defw 06 defw 48 defw 53 defw 18 defw 74 defw 98 defw 15 defw 27 defw 02 defw 92 defw 23 defw 08 defw 71 defw 76 defw 84 defw 15 defw 52 defw 92 defw 63 defw 81 defw 10 defw 44 defw 10 defw 69 defw 93 </syntaxhighlight> {{out}} <pre> E>maxtri 1320 </pre> =={{header\|zkl}}== {{trans\|Python}} The two Python solutions: <syntaxhighlight 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();</syntaxhighlight> <syntaxhighlight 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();</syntaxhighlight> {{trans\|Go}} <syntaxhighlight 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]);</syntaxhighlight> {{out}} <pre> 1320 1320 1320 </pre>