Advent of Z80 - Day 8, 2022
Day 8 has a somewhat less obvious puzzle than the previous days, but as is typical with the Z80 solutions there’s still more time spent working against the low level nature of assembly than there is time spent figuring out how to solve the puzzle.
As with the last post, this one is relatively light on prose as I catch up on backlog from COVID. Fortunately, once again this is code I wrote last year during the AoC, so it’s ready to roll but in a bit of a different style.
The first star requires determining how many trees in a grid are visible from outside the grid. A tree is visible if no taller trees block line of sight to it from one of the four cardinal directions. I solved this problem by scanning over the input left to right, top to bottom, tracking the height of trees in each column and in the current row as I went, then reversing direction and scanning right to left, bottom to top. If a tree is taller than the tallest tree seen so far in its row or column, it’s visible from the edge. To avoid double counting trees I re-use bit 7 of the height of each tree to mark visibility.
START:
LD SP, 08000H
; clear out all the column heights ahead of scanning down
XOR A
LD HL, HEIGHTS
LD DE, HEIGHTS+1
LD BC, MAPSIZE-1
LD (HL), A
LDIR ; copy MAPSIZE-1 bytes from (HL) to (DE), incrementing both each time
; scan each row and column from each direction, marking visible trees in bit 7
; then count how many trees are marked
LD C, MAPSIZE ; row counter
LD HL, DATA
; for each row...
DOWN:
LD E, 0 ; max tree height in row
LD B, MAPSIZE ; column counter
LD IX, HEIGHTS
RIGHT: LD D, (HL) ; load next tree height
RES 7, D ; reset the visible flag before comparing
INC D ; use 1-10 instead of 0-9 so edges always match
LD A, E ; using max height...
CP D ; compare max height to next tree height
JR NC, RSKIP ; CF set if this tree > max seen
LD E, D ; store new max height
SET 7, (HL) ; mark tree as visible
RSKIP: LD A, (IX+0) ; load max column height
CP D ; compare to next tree height
JR NC, DSKIP ; alas, not visible from above
LD (IX+0), D ; update max height
SET 7, (HL) ; mark tree as visible
DSKIP: INC IX ; move along
INC HL ; move along
DJNZ RIGHT ; and loop over remaining trees
DEC C ; row counter
JR NZ, DOWN
; then do it all again, going backwards
XOR A
LD HL, HEIGHTS
LD DE, HEIGHTS+1
LD BC, MAPSIZE-1
LD (HL), A
LDIR ; copy MAPSIZE-1 bytes from (HL) to (DE), incrementing both each time
LD C, MAPSIZE ; row counter
LD HL, DATA + MAPSIZE * MAPSIZE - 1
UP: LD E, 0 ; max tree height in row
LD B, MAPSIZE ; column counter
LD IX, HEIGHTS
LEFT: LD D, (HL) ; load next tree height
RES 7, D ; reset the visible flag before comparing
INC D ; use 1-10 instead of 0-9 so edges always match
LD A, E ; using max height...
CP D ; compare max height to next tree height
JR NC, LSKIP ; CF set if this tree > max seen
LD E, D ; store new max height
SET 7, (HL) ; mark tree as visible
LSKIP: LD A, (IX+0) ; load max column height
CP D ; compare to next tree height
JR NC, USKIP ; alas, not visible from above
LD (IX+0), D ; update max height
SET 7, (HL) ; mark tree as visible
USKIP: INC IX ; move along
DEC HL ; move along - backwards
DJNZ LEFT ; and loop over remaining trees
DEC C ; row counter
JR NZ, UP
; now count how many have bit 7 set
LD HL, DATA
LD DE, 0
LD C, MAPSIZE
VISROW: LD B, MAPSIZE
VISCOL: BIT 7, (HL)
JR Z, VSKIP
INC DE
VSKIP: RES 7, (HL) ; clear for later processing ease
INC HL
DJNZ VISCOL
DEC C
JR NZ, VISROW
LD IY, 0
ADD IY, DE
LD HL, 0
CALL PRINT32
LD A, '\n'
OUT (1), AStar 2 involves finding a ‘scenic score’, which is the product of the distance in each direction to the highest tree. The naive approach will traverse trees, and at each tree move steps in each direction. This is $O(n^3), or around a million steps for a grid size of 99 - not exactly a great solution, but using a desktop emulator it’s still only a fraction of a second.
The code below once again sweeps over the input data from the top left. This time, it tracks the maximum distance visible from a tree of each height, stored in two 10-number arrays. The top and left distances are known as soon as each tree is reached, so those two values are multiplied together and stored in an array of 16-bit numbers, one per tree. As with star 1, when the bottom right corner is reached the code then reverses direction and scans back up to the top left, repeating the computation. At each tree, the 16-bit multiplication result is itself multiplied by the stored 16-bit value, and a running maximum is tracked.
; begin by zeroing all distances
XOR A
LD HL, DISTANCES
LD DE, DISTANCES + 1
LD BC, 10 * (MAPSIZE + 1) - 1
LD (HL), A
LDIR
LD C, MAPSIZE ; row counter
LD HL, DATA
LD IY, SCENICS
LD D, 0
DOWN_2:
LD B, MAPSIZE ; column counter
LD IX, DISTANCES + 10
LD E, 0
LD (DISTANCES), DE
LD (DISTANCES+2), DE
LD (DISTANCES+4), DE
LD (DISTANCES+6), DE
LD (DISTANCES+8), DE
RIGHT_2:
PUSH BC
LD E, (HL) ; load next tree height
ADD IX, DE ; IX[DE]
LD C, (IX+0)
PUSH IX
LD IX, DISTANCES
ADD IX, DE ; DISTANCES[DE]
LD B, (IX+0)
POP IX
CALL MUL8
LD (IY+0), C
LD (IY+1), B
INC IY
INC IY
LD A, 10 ; finish adding 10 to IX
SUB E
LD E, A
ADD IX, DE
POP BC
CALL DISTUPD
INC HL ; move along
DJNZ RIGHT_2 ; and loop over remaining trees
DEC C ; row counter
JR NZ, DOWN_2
; todo: up and to the left, finding maximum
XOR A
LD HL, DISTANCES
LD DE, DISTANCES + 1
LD BC, 10 * (MAPSIZE + 1) - 1
LD (HL), A
LDIR
LD C, MAPSIZE ; row counter
LD HL, DATA + MAPSIZE * MAPSIZE - 1
LD D, 0
UP_2:
LD B, MAPSIZE ; column counter
LD IX, DISTANCES + 10
LD E, 0
LD (DISTANCES), DE
LD (DISTANCES+2), DE
LD (DISTANCES+4), DE
LD (DISTANCES+6), DE
LD (DISTANCES+8), DE
LEFT_2:
PUSH BC
PUSH HL
LD E, (HL) ; load next tree height
ADD IX, DE ; IX[DE]
LD C, (IX+0)
PUSH IX
PUSH DE
LD IX, DISTANCES
ADD IX, DE ; DISTANCES[DE]
LD B, (IX+0)
CALL MUL8 ; BC = dist * dist
DEC IY
DEC IY
LD E, (IY+0) ; DE = dist * dist from down/right
LD D, (IY+1)
CALL MUL16 ; DE:BC = dist*dist*dist*dist
PUSH IY
LD IY, (MAX)
LD HL, (MAX+2)
CALL CMP32
POP IY
JR NC, NOTMAX
LD (MAX), BC
LD (MAX+2), DE
NOTMAX:
POP DE
POP IX
LD A, 10 ; finish adding 10 to IX
SUB E
LD E, A
ADD IX, DE
POP HL
POP BC
CALL DISTUPD
DEC HL ; move along
DJNZ LEFT_2 ; and loop over remaining trees
DEC C ; row counter
JR NZ, UP_2
LD IY, (MAX)
LD HL, (MAX+2)
CALL PRINT32
LD A, '\n'
OUT (1), A
FINISH:
HALT
; Update distances in IX-10 to IX-1 and DISTANCES to DISTANCES+9
; in: A 10 - height
; out: A destroyed
; E destroyed
DISTUPD:
PUSH HL
PUSH IY
; zero out distances this tree height or below
; multiply A by 6
RLCA ; bit 7 is definitely clear here
LD E, A ; save height*2
RLCA ; also here
ADD A, E ; A = height * 6, max. 54
LD E, A
LD HL, DZEROS - 6
ADD HL, DE ; skip over (10-height) loads
XOR A
JP (HL)
DZEROS:
LD (DISTANCES+9), A
LD (IX-1), A
LD (DISTANCES+8), A
LD (IX-2), A
LD (DISTANCES+7), A
LD (IX-3), A
LD (DISTANCES+6), A
LD (IX-4), A
LD (DISTANCES+5), A
LD (IX-5), A
LD (DISTANCES+4), A
LD (IX-6), A
LD (DISTANCES+3), A
LD (IX-7), A
LD (DISTANCES+2), A
LD (IX-8), A
LD (DISTANCES+1), A
LD (IX-9), A
LD (DISTANCES+0), A
LD (IX-10), A
; increment all distances
LD IY, DISTANCES
INC (IY+0)
INC (IX-10)
INC (IY+1)
INC (IX-9)
INC (IY+2)
INC (IX-8)
INC (IY+3)
INC (IX-7)
INC (IY+4)
INC (IX-6)
INC (IY+5)
INC (IX-5)
INC (IY+6)
INC (IX-4)
INC (IY+7)
INC (IX-3)
INC (IY+8)
INC (IX-2)
INC (IY+9)
INC (IX-1)
POP IY
POP HL
RET
.include "util32.z80"The static data definitions follow.
MAX: DEFB 0, 0, 0, 0 ; maximum scenic distance
DATA:
.include "day08-input.z80"
HEIGHTS:
DEFS MAPSIZE
DISTANCES:
DEFS (MAPSIZE + 1) * 10
SCENICS:
DEFS MAPSIZE * MAPSIZE * 2Now, you’ll need a bit of patience for this. It’ll take around 56 million CPU cycles to compute both stars. Perhaps it’s time to implement the core emulator in web assembly…
JP STARTThe series
Day 1 | Day 2 | Day 3 | Day 4 | Day 5 | Day 6 | Day 7 | Day 8 | Day 9 | Day 10 | Day 11 | Day 12 | Day 13 | Day 14 | Day 15 | Day 16 | Day 17 | Day 18 | Day 19 | Day 20 | Day 21 | Day 22 | Day 23 | Day 24 | Day 25 |