Maximum triangle path sum: Difference between revisions
m
→{{header|EasyLang}}
| (25 intermediate revisions by 15 users not shown) | |||
Line 47:
{{trans|Python}}
<
L tri.len > 1
V t0 = tri.pop()
Line 73:
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))))</
{{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 i*n+(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 i*n+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 (N*N)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!}}==
<
IF a>b THEN RETURN (a) FI
RETURN (b)
Line 130 ⟶ 269:
PrintI(data(0))
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Maximum_triangle_path_sum.png Screenshot from Atari 8-bit computer]
Line 138 ⟶ 277:
=={{header|Ada}}==
<
procedure Max_Sum is
Line 178 ⟶ 317:
end loop;
Put_Line(Integer'Image(Triangle(1)));
end Max_Sum;</
{{out}}
<pre> 1320
Line 186 ⟶ 325:
{{works with|ALGOL 68G|Any - tested with release 2.6.win32}}
Basically the same algorithm as Ada and C++ but using a triangular matrix.
<
[ 1]INT row 1 := ( 55 );
Line 232 ⟶ 371:
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}}
<
-- Working from the bottom of the triangle upwards,
Line 417 ⟶ 564:
return lst
end tell
end zipWith3</
{{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}}==
<
let a = val t
for i in a.length-1..-1..1, c in linearindices a[r]:
Line 450 ⟶ 639:
@print maxpathsum test
</syntaxhighlight>
=={{header|AutoHotkey}}==
Examples:<syntaxhighlight lang="autohotkey">data :=[
(join ltrim
55,
Line 492 ⟶ 680:
}
MsgBox % data[1] "`n" path[1]</
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)
Line 519 ⟶ 707:
}
function max(x,y) { return((x > y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
Line 550 ⟶ 738:
=={{header|Bracmat}}==
<
55
94 48
Line 593 ⟶ 781:
| out$!Max
)
)</
{{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>
Line 644 ⟶ 1,162:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 652 ⟶ 1,170:
=={{header|C sharp|C#}}==
<
using System;
Line 702 ⟶ 1,220:
}
</syntaxhighlight>
{{out}}
<pre>Maximum total: 1320</pre>
Line 708 ⟶ 1,226:
=={{header|C++}}==
{{trans|Ada}}
<
/* Algorithm complexity: n*log(n) */
#include <iostream>
Line 747 ⟶ 1,265:
std::cout << "Maximum total: " << triangle[0] << "\n\n";
}
</syntaxhighlight>
{{out}}
<pre>Maximum total: 1320</pre>
Line 753 ⟶ 1,271:
=={{header|Clojure|ClojureScript}}==
<
(ns clojure.examples.rosetta
(:gen-class)
Line 808 ⟶ 1,326:
(println (max-sum nested-list))
</syntaxhighlight>
{{out}}
<pre>1320</pre>
=={{header|Common Lisp}}==
<
(let ((triangle (loop for line = (read-line s NIL NIL)
while line
Line 836 ⟶ 1,354:
(find-max-path-sum s)))
(format T "~a~%" (with-open-file (f "triangle.txt")
(find-max-path-sum f)))</
{{Out}}
Line 843 ⟶ 1,361:
=={{header|D}}==
<
import std.stdio, std.algorithm, std.range, std.file, std.conv;
Line 851 ⟶ 1,369:
.array)[0]
.writeln;
}</
{{out}}
<pre>1320</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
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
<
import extensions;
import extensions'math;
Line 887 ⟶ 1,448:
int i := 0;
int j := 0;
input.splitBy(
{
j := 0;
line.trim().splitBy(" ").forEach::(string num)
{
list[i][j] := num.toInt();
Line 900 ⟶ 1,461:
};
for(int i := 16
{
for(int j := 0
{
list[i][j] := max(list[i][j] + list[i+1][j], list[i][j] + list[i+1][j+1])
Line 909 ⟶ 1,470:
console.printLine("Maximum total: ", list[0][0])
}</
{{out}}
<pre>
Line 916 ⟶ 1,477:
=={{header|Elixir}}==
<
def triangle_path(text) do
text
Line 958 ⟶ 1,519:
IO.puts Maximum.triangle_path(text)
</syntaxhighlight>
{{out}}
Line 967 ⟶ 1,528:
=={{header|Erlang}}==
Reads the data from the file "triangle.txt"
<syntaxhighlight lang="erlang">
-mode(compile).
-import(lists, [foldl/3]).
Line 993 ⟶ 1,554:
fold_rest([A], [B]) -> [A+B];
fold_rest([A1 | [A2|_] = As], [B|Bs]) -> [B + max(A1,A2) | fold_rest(As, Bs)].
</syntaxhighlight>
{{Out}}
<pre>
Line 1,000 ⟶ 1,561:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM TRIANGLE_PATH
Line 1,057 ⟶ 1,618:
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}}==
<
math.order math.parser math.vectors prettyprint sequences
splitting ;
Line 1,073 ⟶ 1,647:
reduce first ;
"triangle.txt" parse-triangle max-triangle-path-sum .</
{{out}}
<pre>
Line 1,080 ⟶ 1,654:
=={{header|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.
Line 1,121 ⟶ 1,695:
;
MAX-SUM .</
{{out}}
<pre>
Line 1,134 ⟶ 1,708:
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.
Line 1,245 ⟶ 1,819:
CALL REFINE !Only the result by more cunning.
END
</syntaxhighlight>
Output:
Line 1,333 ⟶ 1,907:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 1,393 ⟶ 1,967:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}<pre> maximum triangle path sum = 1320</pre>
=={{header|Go}}==
<
import (
Line 1,451 ⟶ 2,025:
}
fmt.Println(d[0])
}</
{{Out}}
<pre>
Line 1,458 ⟶ 2,032:
=={{header|Haskell}}==
<
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</
{{out}}
<pre>1320</pre>
Line 1,468 ⟶ 2,042:
Or, inlining the data for quick testing, and using an applicative expression:
<
maxPathSum :: [[Int]] -> Int
Line 1,499 ⟶ 2,073:
[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]
]</
{{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}}==
<
maxSum=: [: {. (+ (0 ,~ 2 >./\ ]))/ NB. find max triangle path sum</
'''Example Usage'''
<
1320</
Explanation:
Line 1,519 ⟶ 2,150:
Instead of padding, we could instead trim the other argument to match the current reduced row length.
<
However, this turns out to be a slightly slower approach, because we are doing a little more work for each row.
Line 1,527 ⟶ 2,158:
=={{header|Java}}==
{{works with|Java|8}}
<
import static java.util.Arrays.stream;
Line 1,545 ⟶ 2,176:
System.out.println(data[0][0]);
}
}</
<pre>1320</pre>
Line 1,552 ⟶ 2,183:
===ES5===
====Imperative====
<
var arr = [
[55],
Line 1,592 ⟶ 2,223:
console.log(arr);
</syntaxhighlight>
{{out}}
<
[ [ 1320 ] ]
</syntaxhighlight>
====Functional====
{{trans|Haskell}}
<
// Right fold using final element as initial accumulator
Line 1,650 ⟶ 2,281:
)[0];
})();</
{{out}}
<syntaxhighlight lang
===ES6===
====Imperative====
<
function distilLastLine() {
Line 1,697 ⟶ 2,328:
];
console.log(maximumTrianglePathSum(theTriangle));</
{{out}}
<syntaxhighlight lang
====Functional====
{{Trans|Haskell}}
<
"use strict";
Line 1,768 ⟶ 2,399:
[27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
]);
})();</
{{Out}}
<pre>1320</pre>
Line 1,776 ⟶ 2,407:
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.<
def solve:
Line 1,787 ⟶ 2,418:
. as $in
| reduce range(length -2; -1; -1) as $i
($in[-1]; update( $in[$i] ) ) ;</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
function maxpathsum(t::Array{Array{I, 1}, 1}) where I
T = deepcopy(t)
Line 1,822 ⟶ 2,453:
[27, 02, 92, 23, 08, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]]
@show maxpathsum(test)</
{{out}}
Line 1,829 ⟶ 2,460:
=={{header|Kotlin}}==
{{trans|C}}
<
val tri = intArrayOf(
Line 1,868 ⟶ 2,499:
println("Maximum total = ${triangle[0]}")
}
}</
{{out}}
Line 1,880 ⟶ 2,511:
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.
<
{ 55 },
{ 94, 48 },
Line 1,932 ⟶ 2,563:
print(solve(triangleSmall))
print(solve(triangleLarge))
</syntaxhighlight>
{{out}}
Line 1,939 ⟶ 2,570:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
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]]]</
{{out}}
<pre>MaximumTrianglePathSum[nums]
Line 1,949 ⟶ 2,580:
=={{header|Nim}}==
{{trans|Python}}
<
proc solve(tri: seq[seq[int]]): int =
Line 1,979 ⟶ 2,610:
echo solve data.splitLines.map((x: string) => x.strip.split.map parseInt)
</syntaxhighlight>
{{out}}
Line 1,985 ⟶ 2,616:
=={{header|PARI/GP}}==
<
forstep(i=#V,2,-1,V[i-1]+=vector(i-1,j,max(V[i][j],V[i][j+1]))); V[1][1]</
{{out}}
<pre>%1 = 1320</pre>
Line 1,992 ⟶ 2,623:
=={{header|Pascal}}==
testet with freepascal, should run under Turbo Pascal, therefore using static array and val, and Delphi too.
<
{'triangle.txt'
* one element per line
Line 2,097 ⟶ 2,728:
dec(h);
end;
end.</
{{out}}
<pre>height sum
Line 2,109 ⟶ 2,740:
=={{header|Perl}}==
<
use List::Util 'max';
Line 2,120 ⟶ 2,751:
}
say max(@sum);</
{{out}}
<pre>
Line 2,128 ⟶ 2,759:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
Line 2,157 ⟶ 2,788:
<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>
<!--</
{{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>
{{out}}
<pre>Mode directed tabling:
max_val = 1320
Loop based:
max_val = 1320
Adapted the Prolog solution:
max_val = 1320</pre>
=={{header|PicoLisp}}==
{{trans|Common Lisp}}
<
(let (Lst (reverse Lst) R (car Lst))
(for I (cdr Lst)
Line 2,176 ⟶ 2,920:
R )
I ) ) )
(car R) ) )</
=={{header|PL/I}}==
{{trans|REXX}}
<
triang: Proc Options(Main);
Dcl nn(18,18) Bin Fixed(31);
Line 2,221 ⟶ 2,965:
get string(vla) Edit((nn(r,j) Do j=1 To r))(f(3));
End;
End;</
{{out}}
<pre>maximum path sum: 1320</pre>
=={{header|Prolog}}==
<
data(N, T),
path(0, T, V).
Line 2,267 ⟶ 3,011:
[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).
Line 2,279 ⟶ 3,023:
=={{header|Python}}==
A simple mostly imperative solution:
<
while len(tri) > 1:
t0 = tri.pop()
Line 2,306 ⟶ 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()])</
{{out}}
<pre>1320</pre>
A more functional version, similar to the Haskell entry (same output):
<
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]</
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:
Line 2,322 ⟶ 3,066:
{{Trans|JavaScript}}
{{Works with|Python|3|7}}
<
from functools import (reduce)
Line 2,334 ⟶ 3,078:
return reduce(
lambda xs, ys: [
a + max(b, c) for (a, b, c
in zip(ys, xs, xs[1:])
],
reversed(rows[:-1]), rows[-1]
Line 2,340 ⟶ 3,085:
#
print(
maxPathSum([
Line 2,362 ⟶ 3,107:
[27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
])
)</
{{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}}==
<
(require math/number-theory)
Line 2,425 ⟶ 3,221:
#(55 94 48 95 30 96 77 71 26 67))
(check-equal? (maximum-triangle-path-sum test-triangle) 321)
)</
{{out}}
<pre>1320</pre>
Line 2,433 ⟶ 3,229:
{{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"
94 48
95 30 96
Line 2,468 ⟶ 3,264:
# 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] }</
{{out}}
Line 2,478 ⟶ 3,274:
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.
<
@.=.; @.1 = 55
@.2 = 94 48
Line 2,509 ⟶ 3,305:
end /*r*/
/*stick a fork in it, we're all done. */
say 'maximum path sum: ' #.1.1 /*show the top (row 1) pyramid number. */</
'''output''' using the data within the REXX program:
<pre>
Line 2,516 ⟶ 3,312:
=={{header|Ring}}==
<
# Project : Maximum triangle path sum
Line 2,571 ⟶ 3,367:
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}}==
<
" 55
94 48
Line 2,603 ⟶ 3,437:
x.zip(maxes).map{|a,b| a+b}
}.max
# => 1320</
=={{header|Rust}}==
{{works with|Rust|1.3}}
<
fn max_path(vector: &mut Vec<Vec<u32>>) -> u32 {
Line 2,655 ⟶ 3,489:
println!("{}", max_value);
//=> 7273
}</
=={{header|Scala}}==
<
// Solution:
def sum(triangle: Array[Array[Int]]) =
Line 2,678 ⟶ 3,512:
println(sum(parseLines(triangle)))
println(sum(parseFile("triangle.txt")))
}</
{{out}}
<pre>321
Line 2,687 ⟶ 3,521:
Iterative solution:
<
ARGF.each { |line|
Line 2,698 ⟶ 3,532:
}
say sum.max</
Recursive solution:
<
func max_value(i=0, j=0) is cached {
Line 2,708 ⟶ 3,542:
}
say max_value()</
{{out}}
<pre>% sidef maxpath.sf triangle.txt
Line 2,714 ⟶ 3,548:
=={{header|Stata}}==
<
mata
a = st_data(.,.)
Line 2,724 ⟶ 3,558:
}
a[1,1]
end</
'''Output'''
Line 2,732 ⟶ 3,566:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
proc maxTrianglePathSum {definition} {
Line 2,776 ⟶ 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…</
{{out}}
<pre>
Line 2,783 ⟶ 3,617:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
'Solution derived from http://stackoverflow.com/questions/8002252/euler-project-18-approach.
Line 2,809 ⟶ 3,643:
objinfile.Close
Set objfso = Nothing
</syntaxhighlight>
{{In}}
Line 2,839 ⟶ 3,673:
=={{header|Wren}}==
{{trans|Go}}
<
" 55",
" 94 48",
Line 2,872 ⟶ 3,706:
}
}
System.print(d[0])</
{{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 := (18*18+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,2*trisize-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>
Line 2,882 ⟶ 4,182:
{{trans|Python}}
The two Python solutions:
<
while(tri.len()>1){
t0:=tri.pop();
Line 2,889 ⟶ 4,189:
'wrap([(i,t)]){ t + t0[i].max(t0[i+1]) }]])
}
tri[0][0].println();</
<
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();</
{{trans|Go}}
<
d:=lines[-1].copy();
foreach row in ([lines.len()-2..0,-1]){
Line 2,905 ⟶ 4,205:
}
}
println(d[0]);</
{{out}}
<pre>
| |||