Maximum triangle path sum: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add APL) |
(Added Z80 Assembly version) |
||
Line 3,346: | Line 3,346: | ||
{{out}} |
{{out}} |
||
<pre> |
<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 |
1320 |
||
</pre> |
</pre> |