Maximum triangle path sum: Difference between revisions
m
→{{header|EasyLang}}
m (→{{header|Quackery}}: tidy up) |
|||
| (16 intermediate revisions by 12 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 237 ⟶ 376:
+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}}==
Line 419 ⟶ 566:
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>
Line 597 ⟶ 786:
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
The [[#Chipmunk Basic|Chipmunk Basic]] solution works without any changes.
==={{header|BASIC256}}===
<syntaxhighlight lang="freebasic">arraybase 1
Line 649 ⟶ 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,060 ⟶ 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,093 ⟶ 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,106 ⟶ 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,264 ⟶ 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,681 ⟶ 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,946 ⟶ 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,210 ⟶ 3,673:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
" 55",
" 94 48",
Line 3,247 ⟶ 3,710:
{{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>
| |||