Maximum triangle path sum: Difference between revisions
m
→{{header|EasyLang}}
(Added Z80 Assembly version) |
|||
| (12 intermediate revisions by 8 users not shown) | |||
Line 78:
<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>
Line 647 ⟶ 786:
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
The [[#Chipmunk Basic|Chipmunk Basic]] solution works without any changes.
==={{header|BASIC256}}===
<syntaxhighlight lang="freebasic">arraybase 1
Line 699 ⟶ 841:
{{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}}===
Line 1,110 ⟶ 1,372:
{{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
<syntaxhighlight lang="elena">import system'routines;
import extensions;
Line 1,143 ⟶ 1,448:
int i := 0;
int j := 0;
input.splitBy(
{
j := 0;
line.trim().splitBy(" ").forEach::(string num)
{
list[i][j] := num.toInt();
Line 1,156 ⟶ 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 1,314 ⟶ 1,619:
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}}==
Line 1,731 ⟶ 2,049:
. 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 -------------------------
Line 2,996 ⟶ 3,371:
<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>
Line 3,260 ⟶ 3,673:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
" 55",
" 94 48",
| |||