Maximum triangle path sum: Difference between revisions

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