path: root/aoc-2025/day11.asm

; Advent of Code 2025 - Day 11

bits 64
default rel

global _start

%define SYS_EXIT   60
%define SYS_READ   0
%define SYS_WRITE  1
%define SYS_OPEN   2
%define SYS_CLOSE  3

%define O_RDONLY   0
%define STDOUT     1

%define RAW_SIZE   262144
%define NCODES     17576        ; 26^3 possible 3-letter names
%define OUT_CODE   10003        ; encode("out")
%define YOU_CODE   16608        ; encode("you")
%define SVR_CODE   12731        ; encode("svr")
%define DAC_CODE   2030         ; encode("dac")
%define FFT_CODE   3529         ; encode("fft")
%define MAXEDGES   8192

section .data
    input_path db "input/day11.txt", 0

    newline    db 10

    label1     db "Part 1: ", 0
    label2     db "Part 2: ", 0

section .bss
    raw           resb RAW_SIZE
    adj_head      resq NCODES    ; first child index in `child`
    adj_cnt       resq NCODES    ; number of children
    child         resq MAXEDGES  ; flat child codes
    memo          resq NCODES    ; path counts, -1 = not computed
    blocked       resb NCODES    ; 1 = treat node as a dead end

    raw_len       resq 1
    t1            resq 1
    t2            resq 1

    number_buffer resb 32

section .text

_start:
    mov     rax, SYS_OPEN
    mov     rdi, input_path
    mov     rsi, O_RDONLY
    xor     rdx, rdx
    syscall
    mov     r12, rax

    xor     r13, r13
read_loop:
    mov     rax, SYS_READ
    mov     rdi, r12
    lea     rsi, [raw + r13]
    mov     rdx, RAW_SIZE
    sub     rdx, r13
    syscall
    cmp     rax, 0
    jle     read_done
    add     r13, rax
    jmp     read_loop
read_done:
    mov     [raw_len], r13
    mov     rax, SYS_CLOSE
    mov     rdi, r12
    syscall

    ; memo = -1 everywhere
    mov     rax, -1
    lea     rdi, [memo]
    mov     rcx, NCODES
    rep     stosq

    ; parse "name: a b c" adjacency lines
    lea     rsi, [raw]
    mov     rax, [raw_len]
    lea     r13, [raw + rax]   ; end pointer
    xor     r12, r12           ; child write index
parse_line:
    cmp     rsi, r13
    jae     parse_done
    mov     al, [rsi]
    cmp     al, 10
    je      parse_skip
    cmp     al, 13
    je      parse_skip
    call    encode3            ; RAX = node code
    mov     r10, rax
    mov     [adj_head + r10*8], r12
skip_sep:
    mov     al, [rsi]
    cmp     al, ':'
    je      .adv
    cmp     al, ' '
    je      .adv
    jmp     children
.adv:
    inc     rsi
    jmp     skip_sep
children:
    xor     r11, r11           ; child count
child_loop:
    cmp     rsi, r13
    jae     child_done
    mov     al, [rsi]
    cmp     al, 10
    je      child_done
    cmp     al, 13
    je      child_done
    cmp     al, ' '
    je      child_space
    call    encode3
    mov     [child + r12*8], rax
    inc     r12
    inc     r11
    jmp     child_loop
child_space:
    inc     rsi
    jmp     child_loop
child_done:
    mov     [adj_cnt + r10*8], r11
skip_eol:
    cmp     rsi, r13
    jae     parse_done
    mov     al, [rsi]
    inc     rsi
    cmp     al, 10
    jne     skip_eol
    jmp     parse_line
parse_skip:
    inc     rsi
    jmp     parse_line
parse_done:

    ; part 1: paths you -> out
    call    clear_memo
    mov     rdi, YOU_CODE
    call    count
    mov     [t1], rax

    ; part 2: paths svr -> out visiting both dac and fft, via inclusion-exclusion
    call    clear_memo
    mov     rdi, SVR_CODE
    call    count
    mov     r12, rax                   ; N(all)

    mov     byte [blocked + DAC_CODE], 1
    call    clear_memo
    mov     rdi, SVR_CODE
    call    count
    mov     r13, rax                   ; N(avoid dac)
    mov     byte [blocked + DAC_CODE], 0

    mov     byte [blocked + FFT_CODE], 1
    call    clear_memo
    mov     rdi, SVR_CODE
    call    count
    mov     r14, rax                   ; N(avoid fft)
    mov     byte [blocked + FFT_CODE], 0

    mov     byte [blocked + DAC_CODE], 1
    mov     byte [blocked + FFT_CODE], 1
    call    clear_memo
    mov     rdi, SVR_CODE
    call    count                      ; N(avoid both) in rax
    mov     byte [blocked + DAC_CODE], 0
    mov     byte [blocked + FFT_CODE], 0

    sub     r12, r13
    sub     r12, r14
    add     r12, rax
    mov     [t2], r12

    mov     rcx, label1
    call    print_string
    mov     rax, [t1]
    call    print_int64
    call    print_newline

    mov     rcx, label2
    call    print_string
    mov     rax, [t2]
    call    print_int64
    call    print_newline

    mov     rax, SYS_EXIT
    xor     rdi, rdi
    syscall

; clear_memo: reset all memo entries to -1. Clobbers RAX, RCX, RDI.
clear_memo:
    mov     rax, -1
    lea     rdi, [memo]
    mov     rcx, NCODES
    rep     stosq
    ret

; encode3: read 3 lowercase letters at [RSI] into a base-26 code, advance RSI.
;   Output: RAX = code. Clobbers RAX, RDX.
encode3:
    movzx   eax, byte [rsi]
    sub     eax, 'a'
    imul    eax, eax, 676
    movzx   edx, byte [rsi + 1]
    sub     edx, 'a'
    imul    edx, edx, 26
    add     eax, edx
    movzx   edx, byte [rsi + 2]
    sub     edx, 'a'
    add     eax, edx
    add     rsi, 3
    ret

; count: number of paths from node RDI to out. Memoised DFS over the DAG.
;   Output: RAX. Clobbers RAX; preserves everything else via the stack.
count:
    cmp     rdi, OUT_CODE
    je      .one
    cmp     byte [blocked + rdi], 0
    jne     .zero
    mov     rax, [memo + rdi*8]
    cmp     rax, -1
    jne     .ret
    push    r12
    push    r13
    push    r14
    push    r15
    mov     r12, rdi
    mov     r13, [adj_head + r12*8]
    mov     r14, r13
    add     r14, [adj_cnt + r12*8]
    xor     r15, r15
.loop:
    cmp     r13, r14
    jge     .done
    mov     rdi, [child + r13*8]
    call    count
    add     r15, rax
    inc     r13
    jmp     .loop
.done:
    mov     [memo + r12*8], r15
    mov     rax, r15
    pop     r15
    pop     r14
    pop     r13
    pop     r12
    ret
.one:
    mov     rax, 1
    ret
.zero:
    xor     eax, eax
.ret:
    ret

print_newline:
    mov     rax, SYS_WRITE
    mov     rdi, STDOUT
    mov     rsi, newline
    mov     rdx, 1
    syscall
    ret

print_int64:
    mov     rdi, number_buffer+31
    mov     byte [rdi], 0
    dec     rdi

    cmp     rax, 0
    jne     .conv

    mov     byte [rdi], '0'
    jmp     .done
.conv:
    mov     rbx, 10
.next:
    xor     rdx, rdx
    div     rbx
    add     dl, '0'
    mov     [rdi], dl
    dec     rdi
    test    rax, rax
    jnz     .next

    inc     rdi
.done:
    mov     rax, SYS_WRITE
    mov     rsi, rdi
    mov     rdi, STDOUT
    mov     rdx, number_buffer+31
    sub     rdx, rsi
    syscall
    ret

print_string:
    push    rcx
    push    rdx
    mov     rdx, 0
.length:
    cmp     byte [rcx+rdx], 0
    je      .submit
    inc     rdx
    jmp     .length
.submit:
    mov     rax, SYS_WRITE
    mov     rdi, STDOUT
    mov     rsi, rcx
    syscall
    pop     rdx
    pop     rcx
    ret