λbje - Advent of Z80

Image sourced from a Cults 3D design, origin unknown.

On day 6 the Z80 will need to process a string of input characters, seeking patterns.

        JP      DAY06

The challenge for day 6 is to detect $n$ unique characters in a sequence. A simple approach to the problem is to start at the first character in the input sequence and check if the following $n$ characters are unique: scan along comparing to the first character, then scan from the second character for $n-1$ characters, and so on up until the $n^{th}$ character is reached. If any character was not unique, move the starting position up to beyond the non-unique character, and try again. This is a relatively poor algorithm, being quadratic in $n$ .

To keep the code simple, I will implement this naive version without any attempts to improve algorithmic performance. $n$ is always small, and the puzzle input is also only 4095 characters: around a million comparisons isn’t unreasonable for the z80.

        .block
; IN:   (HL)    the first character in the candidate sequence
;       C       the required unique sequence length
; OUT:  (HL)    the first character in a unique subsequence
;       ZF      set if a NUL byte is encountered
;       A       overwritten
@UNIQ:  push    de
        push    bc

        ; set the high byte of BC to zero for counters
        ld      b, 0
        ld      d, b
        ld      e, c
        dec     e

OUTER:  push    de      ; save counter

CHECK:  ld      c, e

        ; load the character to test, and check for NUL
        ld      a, (hl)
        or      a
        jr      z, EXIT

        inc     hl

        ; compare BC characters to A
        cpir

        ; ZF is set on match
        jr      z, MATCH

        ; restore HL - CF clear from OR earlier
        sbc     hl, de

        dec     e
        jr      nz, CHECK

        ; made it here - found a subsequence
        inc     hl      ; point to last char
        or      a       ; clear ZF, CF
        jr      EXIT

; restart scanning from new (HL)
MATCH:  sbc     hl, de
        add     hl, bc
        pop     de
        jr      OUTER

EXIT:   pop     bc      ; discard saved DE
        pop     bc
        pop     de
        ret

        .endblock

I can verify this by running it against a handful of test inputs.

        .block
        ld      sp, $8000

        ld      ix, tests

TEST:   ld      l, (ix+0)
        ld      h, (ix+1)
        ld      a, l
        or      h
        jr      z, FIN

        ld      d, h
        ld      e, l

        ld      c, 4
        call    UNIQ
        or      a
        sbc     hl, de
        ex      de, hl
        call    PRINT16
        ld      a, '\n'
        out     (1), a
        inc     ix
        inc     ix
        jr      TEST

FIN:    halt

tests:  dw      test1
        dw      test2
        dw      test3
        dw      test4
        dw      test5
        dw      0

test1:  db      'mjqjpqmgbljsphdztnvjfqwrcgsmlb', 0
test2:  db      'bvwbjplbgvbhsrlpgdmjqwftvncz', 0
test3:  db      'nppdvjthqldpwncqszvftbrmjlhg', 0
test4:  db      'nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg', 0
test5:  db      'zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw', 0

        .endblock

This is now all that’s required to solve the day’s challenge:

DAY06:  ld      sp, $8000

        ld      hl, INPUT
        ld      c, 4
        call    UNIQ
        or      a
        ld      de, INPUT
        sbc     hl, de
        ex      de, hl
        call    PRINT16
        ld      a, '\n'
        out     (1), a

        ld      hl, INPUT
        ld      c, 14
        call    UNIQ
        or      a
        ld      de, INPUT
        sbc     hl, de
        ex      de, hl
        call    PRINT16
        ld      a, '\n'
        out     (1), a

        halt

        .include "print16.z80"
INPUT:
        .include "day06-input.z80"

Look at that, just shy of a million cycles; two runs across an input of length 4095, the first time looking for a sequence of length 4 and the second for a sequence of length 14, for something approximating $4^2\times4095 + 14^2\times4095 = 868,140$ executions of cpir - and a bunch of supporting instructions around that executing in something more like linear time. One might think that cpir and friends aren’t all that great, since the CPU re-fetches the instruction every time it executes it, but avoiding the additional fetch and execute of looping constructs is not insignificant, not to mention the potential savings for machines with little ROM or RAM space to work with.

Today’s solution isn’t optimised, neither algorithmically nor with any particular effort to make the assembly tight, but it’s remarkably simple. At this point in the Advent’s challenges algorithmically naive solutions still run in negligible timeframes, but for later puzzles it’s likely that the Z80 browser emulator will run out of time or space trying to solve puzzles naively. Until then, though, simple is good.

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 |