Advent of Z80 - Day 7, 2022
Day 7 is a challenge primarily about parsing the input, with a little side-trip into a recursive algorithm and a dab of 32-bit arithmetic on an 8-bit processor.
JP DAY07Regrettably, I contracted COVID this week. As a result the following is light on prose and heavy on code I originally wrote on the 8th of December 2022. You will also notice that the code style is rather different: I’ve settled on a particular style for this series, using lowercase mnemonics and code blocks; a large portion of the code below is a bit more shouty.
The general approach I took was to produce a list of directory sizes. Star 1 requires summing all directory sizes below 100,000 while Star 2 requires finding the smallest directory greater than a number to be determined. The size of a directory is the size of all its files plus all its subdirectories, so the code below scans the lines in the input recursively determining directory sizes when $ cd <dir> is encountered, returning when $ cd .. is encountered, and summing up file sizes.
Once the set of sizes is determined, star 1 is simply scanning the list for values under 100,000 and summing them up, while star 2 first requires determining the minimum size acceptable, then scanning for the smallest value larger than that.
DAY07:
LD SP, 8000H
LD IX, INPUT
LD IY, SIZES
CALL READDIR
JP FINISH
; in: IX input lines
; IY dest for size
; out: DE:BC dir size
; IX next input
; IY next size
READDIR:
PUSH AF
PUSH HL
PUSH IY
LD IY, 0
LD HL, 0
; begin by consuming up to a newline
; for the first invocation this consumes '$ cd /'
; for subsequent invocations it consumes the remainder of '$ cd <dir>'
JR NEWLINE
READLINE:
LD A, (IX+0)
OR A
JR Z, LEAVEDIR
CP '$' ; if $ ... parse command
JR Z, CMD
CP 'd' ; if 'dir <name>' ignore
JR Z, NEWLINE
; if '<size> name' add size, ignore name
CALL READ32
ADD IY, BC
ADC HL, DE
; Keep consuming input until end of input reached or a newline is consumed
NEWLINE:
LD A, (IX + 0)
OR A
JR Z, LEAVEDIR
INC IX
CP '\n'
JR Z, READLINE
JR NEWLINE
; Code flow reaches here on end of input or '$ cd ..'
; The directory's size is written into (IY) and READDIR returns
LEAVEDIR:
; Move the size into DE:BC
EX DE, HL
PUSH IY
POP BC
; Store the size
POP IY
LD (IY+0), C
LD (IY+1), B
LD (IY+2), E
LD (IY+3), D
INC IY
INC IY
INC IY
INC IY
; Increment the count of dirs
LD HL, DIRS
INC (HL)
; Return
POP HL
POP AF
RET
; Could be '$ cd /' or '$ cd ..' or '$ cd <name>' or '$ ls'
; By the time this code is reached '$ cd /' is already consumed
CMD:
LD A, (IX+2)
CP 'l' ; if '$ ls' ignore
JR Z, NEWLINE
; must be $ cd <path>
LD A, (IX+5)
CP '.' ; if '$ cd ..' then return to caller
JR Z, LEAVEDIR
; it must be '$ cd <dir>'
EX (SP), IY ; switch high word of count for sizes index
CALL READDIR
EX (SP), IY ; switch them back
ADD IY, BC
ADC HL, DE
JR NEWLINE
SUM: DEFB 0, 0, 0, 0
FINISH:
; sum the directory sizes <= 100000, 0x186a0
LD IX, SIZES
LD A, (DIRS)
LD B, A
SUMSMALL:
; the highest byte must be zero to match
LD A, (IX+3)
OR A
JR NZ, SUMLOOP
; if next byte also zero, it's small enough
LD A, (IX+2)
OR A
JR Z, SMALL
; else it must be exactly 1
CP 1
JR NZ, SUMLOOP
; the low word must be <= 86A0
LD H, (IX+1)
LD L, (IX+0)
LD DE, 086A1H
OR A ; clear carry
SBC HL, DE
JR NC, SUMLOOP
SMALL:
LD HL, (SUM)
LD D, (IX+1)
LD E, (IX+0)
OR A
ADC HL, DE ; low word
LD (SUM), HL
LD HL, (SUM+2)
LD D, (IX+3)
LD E, (IX+2)
ADC HL, DE ; high word
LD (SUM+2), HL
SUMLOOP:
INC IX
INC IX
INC IX
INC IX
DJNZ SUMSMALL
LD IY, (SUM)
LD HL, (SUM+2)
CALL PRINT32
LD A, '\n'
OUT (1), A
; 70,000,000 units of total space
; 30,000,000 units must be free
; used space is the last value in SIZES
; so subtract 40,000,000 from that for the target size
ld a, (DIRS)
ld l, a
ld h, 0
add hl, hl ; * 2
add hl, hl ; * 4
ld de, SIZES - 4
add hl, de
; more useful to have this in IX
push hl
pop ix
; load low word into de
ld e, (ix+0)
ld d, (ix+1)
ld hl, -40000000 & $ffff
add hl, de
ld c, (ix+2)
ld b, (ix+3)
ex de, hl
ld hl, -40000000 shr 16
adc hl, bc
; HL:DE contains the min size
ld b, a
ld ix, SIZES
TARGET:
; compare msb down
ld a, (ix+3)
cp h
jr c, TOOSMALL
jr nz, CHECKMIN
ld a, (ix+2)
cp l
jr c, TOOSMALL
jr nz, CHECKMIN
ld a, (ix+1)
cp d
jr c, TOOSMALL
jr nz, CHECKMIN
ld a, (ix+0)
cp e
jr c, TOOSMALL
CHECKMIN:
ld c, (ix+3)
ld a, (MIN+3)
cp c
jr c, TOOSMALL
jr nz, SMALLEST
ld c, (ix+2)
ld a, (MIN+2)
cp c
jr c, TOOSMALL
jr nz, SMALLEST
ld c, (ix+1)
ld a, (MIN+1)
cp c
jr c, TOOSMALL
jr nz, SMALLEST
ld c, (ix+0)
ld a, (MIN+0)
cp c
jr c, TOOSMALL
SMALLEST:
ld a, (ix+0)
ld (MIN+0), a
ld a, (ix+1)
ld (MIN+1), a
ld a, (ix+2)
ld (MIN+2), a
ld a, (ix+3)
ld (MIN+3), a
TOOSMALL:
inc ix
inc ix
inc ix
inc ix
djnz TARGET
ld iy, (MIN)
ld hl, (MIN+2)
call PRINT32
ld a, '\n'
out (1), a
halt
.include "util32.z80"
INPUT:
.include "day07-input.z80"
; sample input, ignored because above is zero terminated
db "$ cd /\n"
db "$ ls\n"
db "dir a\n"
db "14848514 b.txt\n"
db "8504156 c.dat\n"
db "dir d\n"
db "$ cd a\n"
db "$ ls\n"
db "dir e\n"
db "29116 f\n"
db "2557 g\n"
db "62596 h.lst\n"
db "$ cd e\n"
db "$ ls\n"
db "584 i\n"
db "$ cd ..\n"
db "$ cd ..\n"
db "$ cd d\n"
db "$ ls\n"
db "4060174 j\n"
db "8033020 d.log\n"
db "5626152 d.ext\n"
db "7214296 k\n"
db 0
MIN: db $ff, $ff, $ff, $ff
DIRS: db 0
SIZES:The 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 |