path: root/2025/day10.asm

; Advent of Code 2025 - Day 10

bits 64
default rel

global _start

%include "utils/io.asm"

%define RAW_SIZE   262144
%define MAXB       16
%define MAXL       12
%define MNCOLS     (MAXB + 1)   ; matrix columns: buttons + rhs
%define CPFSTRIDE  8            ; free-coeff stride (free vars <= 3)

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

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

section .bss
    raw           resb RAW_SIZE

    bmask         resq MAXB              ; part 1: button light masks
    btn_ctrs      resq (MAXB * MAXL)     ; part 2: counters each button hits
    btn_len       resq MAXB
    jolt          resq MAXL              ; part 2: target counter values

    Mnum          resq (MAXL * MNCOLS)   ; augmented matrix numerators
    rowden        resq MAXL              ; per-row common denominators
    pivcol        resq MAXL
    is_piv        resb MAXB
    free_cols     resq MAXB
    ub_free       resq MAXB
    x_free        resq MAXB
    RP            resq MAXL              ; scaled rhs per pivot row
    CPF           resq (MAXL * CPFSTRIDE); scaled free coeffs per pivot row

    raw_len       resq 1
    cur_t         resq 1
    nb            resq 1
    nc            resq 1
    npiv          resq 1
    nfree         resq 1
    Dval          resq 1
    best          resq 1
    total1        resq 1
    total2        resq 1

section .text

_start:
    mov     rdi, input_path
    lea     rsi, [raw]
    mov     rdx, RAW_SIZE
    call    read_file
    mov     [raw_len], rax

    lea     rsi, [raw]
    mov     rax, [raw_len]
    lea     r14, [raw + rax]
    mov     qword [cur_t], 0
    mov     qword [nb], 0
    mov     qword [nc], 0
scan:
    cmp     rsi, r14
    jae     finish_last
    mov     al, [rsi]
    cmp     al, '['
    je      do_bracket
    cmp     al, '('
    je      do_button
    cmp     al, '{'
    je      do_curly
    cmp     al, 10
    je      end_line
    inc     rsi
    jmp     scan

do_bracket:
    inc     rsi
    xor     r10, r10   ; light index
    xor     r11, r11   ; target mask
.loop:
    mov     al, [rsi]
    cmp     al, ']'
    je      .done
    cmp     al, '#'
    jne     .off
    mov     rcx, r10
    mov     rdx, 1
    shl     rdx, cl
    or      r11, rdx
.off:
    inc     r10
    inc     rsi
    jmp     .loop
.done:
    inc     rsi
    mov     [cur_t], r11
    jmp     scan

do_button:
    inc     rsi
    xor     r11, r11   ; light mask
    xor     r10, r10   ; current index
    xor     r9, r9     ; counter list length
.loop:
    mov     al, [rsi]
    cmp     al, ')'
    je      .fin
    cmp     al, ','
    je      .comma
    sub     al, '0'
    movzx   rax, al
    imul    r10, r10, 10
    add     r10, rax
    inc     rsi
    jmp     .loop
.comma:
    mov     rcx, r10
    mov     rdx, 1
    shl     rdx, cl
    or      r11, rdx
    mov     rax, [nb]
    imul    rax, MAXL
    add     rax, r9
    mov     [btn_ctrs + rax*8], r10
    inc     r9
    xor     r10, r10
    inc     rsi
    jmp     .loop
.fin:
    mov     rcx, r10
    mov     rdx, 1
    shl     rdx, cl
    or      r11, rdx
    mov     rax, [nb]
    imul    rax, MAXL
    add     rax, r9
    mov     [btn_ctrs + rax*8], r10
    inc     r9
    inc     rsi
    mov     rax, [nb]
    mov     [bmask + rax*8], r11
    mov     [btn_len + rax*8], r9
    inc     qword [nb]
    jmp     scan

do_curly:
    inc     rsi
    xor     r10, r10   ; current number
.loop:
    mov     al, [rsi]
    cmp     al, '}'
    je      .fin
    cmp     al, ','
    je      .comma
    sub     al, '0'
    movzx   rax, al
    imul    r10, r10, 10
    add     r10, rax
    inc     rsi
    jmp     .loop
.comma:
    mov     rax, [nc]
    mov     [jolt + rax*8], r10
    inc     qword [nc]
    xor     r10, r10
    inc     rsi
    jmp     .loop
.fin:
    mov     rax, [nc]
    mov     [jolt + rax*8], r10
    inc     qword [nc]
    inc     rsi
    jmp     scan

end_line:
    inc     rsi
    push    rsi
    push    r14
    call    solve1
    call    solve2
    pop     r14
    pop     rsi
    mov     qword [cur_t], 0
    mov     qword [nb], 0
    mov     qword [nc], 0
    jmp     scan

finish_last:
    cmp     qword [nb], 0
    je      all_done
    push    rsi
    push    r14
    call    solve1
    call    solve2
    pop     r14
    pop     rsi
all_done:

print_results:
    mov     rcx, label1
    call    print_string
    mov     rax, [total1]
    call    print_int64
    call    print_newline

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

    mov     rax, SYS_EXIT
    xor     rdi, rdi
    syscall

; solve1: part 1 - fewest button presses to match the light target (GF(2)).
solve1:
    mov     rcx, [nb]
    mov     r8, 1
    shl     r8, cl
    mov     r9, 0x7fffffff
    xor     r10, r10
.mask:
    cmp     r10, r8
    jge     .done
    xor     r11, r11
    xor     rbx, rbx
    xor     rcx, rcx
.bits:
    cmp     rcx, [nb]
    jge     .check
    mov     rdx, r10
    shr     rdx, cl
    test    rdx, 1
    jz      .bit_next
    xor     r11, [bmask + rcx*8]
    inc     rbx
.bit_next:
    inc     rcx
    jmp     .bits
.check:
    cmp     r11, [cur_t]
    jne     .next
    cmp     rbx, r9
    jge     .next
    mov     r9, rbx
.next:
    inc     r10
    jmp     .mask
.done:
    cmp     r9, 0x7fffffff
    je      .ret
    add     [total1], r9
.ret:
    ret

; solve2: part 2 - fewest button presses to reach the joltage targets.
; Builds the incidence matrix, reduces it to RREF over the rationals (per-row
; denominators), then enumerates the free variables.
solve2:
    ; clear matrix and set row denominators to 1
    mov     rax, [nc]
    imul    rax, MNCOLS
    mov     rcx, rax
    lea     rdi, [Mnum]
    xor     rax, rax
    rep     stosq
    xor     rcx, rcx
.rd_init:
    cmp     rcx, [nc]
    jge     .rd_done
    mov     qword [rowden + rcx*8], 1
    inc     rcx
    jmp     .rd_init
.rd_done:
    ; A[counter][button] = 1
    xor     r8, r8
.fill_b:
    cmp     r8, [nb]
    jge     .fill_done
    mov     r9, [btn_len + r8*8]
    xor     rcx, rcx
.fill_k:
    cmp     rcx, r9
    jge     .fill_k_done
    mov     r10, r8
    imul    r10, MAXL
    add     r10, rcx
    mov     r11, [btn_ctrs + r10*8]
    mov     rax, r11
    imul    rax, MNCOLS
    add     rax, r8
    mov     qword [Mnum + rax*8], 1
    inc     rcx
    jmp     .fill_k
.fill_k_done:
    inc     r8
    jmp     .fill_b
.fill_done:
    ; rhs column = jolt targets
    xor     rcx, rcx
.rhs:
    cmp     rcx, [nc]
    jge     .rhs_done
    mov     rax, rcx
    imul    rax, MNCOLS
    add     rax, [nb]
    mov     rdx, [jolt + rcx*8]
    mov     [Mnum + rax*8], rdx
    inc     rcx
    jmp     .rhs
.rhs_done:

    ; RREF
    lea     rdi, [is_piv]
    mov     rcx, [nb]
    xor     al, al
    rep     stosb
    mov     qword [npiv], 0
    xor     r15, r15   ; column
.rref_c:
    cmp     r15, [nb]
    jge     .rref_done
    ; find a pivot row in [npiv, nc)
    mov     r12, [npiv]
    mov     r13, -1
.find_pr:
    cmp     r12, [nc]
    jge     .find_pr_done
    mov     rax, r12
    imul    rax, MNCOLS
    add     rax, r15
    cmp     qword [Mnum + rax*8], 0
    je      .find_pr_next
    mov     r13, r12
    jmp     .find_pr_done
.find_pr_next:
    inc     r12
    jmp     .find_pr
.find_pr_done:
    cmp     r13, -1
    je      .rref_c_next
    mov     r12, [npiv]
    cmp     r12, r13
    je      .noswap
    ; swap rows r12 and r13
    xor     rcx, rcx
.swap_j:
    cmp     rcx, [nb]
    jg      .swap_done
    mov     rax, r12
    imul    rax, MNCOLS
    add     rax, rcx
    mov     rbx, r13
    imul    rbx, MNCOLS
    add     rbx, rcx
    mov     r8, [Mnum + rax*8]
    mov     r9, [Mnum + rbx*8]
    mov     [Mnum + rax*8], r9
    mov     [Mnum + rbx*8], r8
    inc     rcx
    jmp     .swap_j
.swap_done:
    mov     r8, [rowden + r12*8]
    mov     r9, [rowden + r13*8]
    mov     [rowden + r12*8], r9
    mov     [rowden + r13*8], r8
.noswap:
    ; normalise pivot row: denominator = pivot numerator
    mov     r12, [npiv]
    mov     rax, r12
    imul    rax, MNCOLS
    add     rax, r15
    mov     rdx, [Mnum + rax*8]
    mov     [rowden + r12*8], rdx
    mov     rdi, r12
    call    reduce_row
    ; eliminate column from every other row
    xor     r13, r13
.elim_rr:
    cmp     r13, [nc]
    jge     .elim_done
    cmp     r13, r12
    je      .elim_next
    mov     rax, r13
    imul    rax, MNCOLS
    add     rax, r15
    mov     r8, [Mnum + rax*8]   ; fc
    test    r8, r8
    jz      .elim_next
    mov     r9, [rowden + r12*8] ; rd
    xor     rcx, rcx
.elim_j:
    cmp     rcx, [nb]
    jg      .elim_j_done
    mov     rax, r13
    imul    rax, MNCOLS
    add     rax, rcx
    mov     r10, [Mnum + rax*8]
    imul    r10, r9
    mov     rbx, r12
    imul    rbx, MNCOLS
    add     rbx, rcx
    mov     r11, [Mnum + rbx*8]
    imul    r11, r8
    sub     r10, r11
    mov     [Mnum + rax*8], r10
    inc     rcx
    jmp     .elim_j
.elim_j_done:
    mov     rax, [rowden + r13*8]
    imul    rax, r9
    mov     [rowden + r13*8], rax
    mov     rdi, r13
    call    reduce_row
.elim_next:
    inc     r13
    jmp     .elim_rr
.elim_done:
    mov     r12, [npiv]
    mov     [pivcol + r12*8], r15
    mov     byte [is_piv + r15], 1
    inc     qword [npiv]
.rref_c_next:
    inc     r15
    jmp     .rref_c
.rref_done:

    ; free columns
    xor     r12, r12
    xor     r15, r15
.free_scan:
    cmp     r15, [nb]
    jge     .free_done
    cmp     byte [is_piv + r15], 0
    jne     .free_next
    mov     [free_cols + r12*8], r15
    inc     r12
.free_next:
    inc     r15
    jmp     .free_scan
.free_done:
    mov     [nfree], r12

    ; D = lcm of the pivot-row denominators
    mov     qword [Dval], 1
    xor     r13, r13
.lcm:
    cmp     r13, [npiv]
    jge     .lcm_done
    mov     rdi, [Dval]
    mov     rsi, [rowden + r13*8]
    call    gcd
    mov     rcx, rax
    mov     rax, [Dval]
    xor     rdx, rdx
    div     rcx
    imul    rax, [rowden + r13*8]
    mov     [Dval], rax
    inc     r13
    jmp     .lcm
.lcm_done:

    ; scaled rhs and free coefficients per pivot row
    xor     r13, r13
.setup_pr:
    cmp     r13, [npiv]
    jge     .setup_done
    mov     rax, [Dval]
    xor     rdx, rdx
    div     qword [rowden + r13*8]
    mov     r8, rax                    ; q = D / rowden
    mov     rax, r13
    imul    rax, MNCOLS
    add     rax, [nb]
    mov     rcx, [Mnum + rax*8]
    imul    rcx, r8
    mov     [RP + r13*8], rcx
    xor     r9, r9
.setup_f:
    cmp     r9, [nfree]
    jge     .setup_f_done
    mov     r10, [free_cols + r9*8]
    mov     rax, r13
    imul    rax, MNCOLS
    add     rax, r10
    mov     rcx, [Mnum + rax*8]
    imul    rcx, r8
    mov     rax, r13
    imul    rax, CPFSTRIDE
    add     rax, r9
    mov     [CPF + rax*8], rcx
    inc     r9
    jmp     .setup_f
.setup_f_done:
    inc     r13
    jmp     .setup_pr
.setup_done:

    ; free-variable upper bounds = min covered target
    xor     r9, r9
.ub_loop:
    cmp     r9, [nfree]
    jge     .ub_done
    mov     r10, [free_cols + r9*8]
    mov     r11, [btn_len + r10*8]
    mov     r12, 0x7fffffff
    xor     rcx, rcx
.ub_k:
    cmp     rcx, r11
    jge     .ub_k_done
    mov     rax, r10
    imul    rax, MAXL
    add     rax, rcx
    mov     rbx, [btn_ctrs + rax*8]
    mov     rdx, [jolt + rbx*8]
    cmp     rdx, r12
    jge     .ub_k_next
    mov     r12, rdx
.ub_k_next:
    inc     rcx
    jmp     .ub_k
.ub_k_done:
    mov     [ub_free + r9*8], r12
    inc     r9
    jmp     .ub_loop
.ub_done:

    mov     qword [best], 0x3fffffff
    xor     rdi, rdi
    xor     rsi, rsi
    call    enum_free
    mov     rax, [best]
    add     [total2], rax
    ret

; enum_free: recurse over free variables (RDI=depth, RSI=partial presses),
; pruning branches that already reach the best. Preserves R12-R15.
enum_free:
    cmp     rsi, [best]
    jae     .ret
    cmp     rdi, [nfree]
    je      .leaf
    push    r12
    push    r13
    push    r14
    push    r15
    mov     r12, rdi
    mov     r13, rsi
    mov     r14, [ub_free + r12*8]
    xor     r15, r15
.vloop:
    mov     rsi, r13
    add     rsi, r15
    cmp     rsi, [best]
    jae     .vdone
    mov     [x_free + r12*8], r15
    lea     rdi, [r12 + 1]
    call    enum_free
    inc     r15
    cmp     r15, r14
    jbe     .vloop
.vdone:
    pop     r15
    pop     r14
    pop     r13
    pop     r12
    ret
.leaf:
    call    eval_leaf
.ret:
    ret

; eval_leaf: with all free variables fixed, recover the basic variables and
; update best. RSI = presses used by free variables. Preserves R12-R15.
eval_leaf:
    mov     r11, rsi   ; running total
    xor     r8, r8     ; pivot row
.pr:
    cmp     r8, [npiv]
    jge     .accept
    mov     rax, [RP + r8*8]
    xor     r9, r9
.f:
    cmp     r9, [nfree]
    jge     .fd
    mov     rcx, r8
    imul    rcx, CPFSTRIDE
    add     rcx, r9
    mov     rdx, [CPF + rcx*8]
    imul    rdx, [x_free + r9*8]
    sub     rax, rdx
    inc     r9
    jmp     .f
.fd:
    test    rax, rax
    js      .ret
    cqo
    idiv    qword [Dval]
    test    rdx, rdx
    jnz     .ret
    add     r11, rax
    cmp     r11, [best]
    jae     .ret
    inc     r8
    jmp     .pr
.accept:
    mov     [best], r11
.ret:
    ret

; gcd(RDI, RSI) -> RAX, inputs non-negative. Clobbers RAX, RDX, RDI, RSI.
gcd:
.loop:
    test    rsi, rsi
    jz      .done
    xor     rdx, rdx
    mov     rax, rdi
    div     rsi
    mov     rdi, rsi
    mov     rsi, rdx
    jmp     .loop
.done:
    mov     rax, rdi
    ret

; reduce_row(RDI=row): make denominator positive and divide the row by the gcd
; of all its entries. Clobbers RAX, RCX, RDX, RSI, RDI, R8, R9, R10, R11.
reduce_row:
    mov     r11, rdi
    mov     r8, r11
    imul    r8, MNCOLS
    mov     rax, [rowden + r11*8]
    test    rax, rax
    jns     .signok
    neg     qword [rowden + r11*8]
    xor     r10, r10
.sneg:
    cmp     r10, [nb]
    jg      .signok
    mov     rax, r8
    add     rax, r10
    neg     qword [Mnum + rax*8]
    inc     r10
    jmp     .sneg
.signok:
    mov     r9, [rowden + r11*8]   ; g accumulator
    xor     r10, r10
.gloop:
    cmp     r10, [nb]
    jg      .gdone
    cmp     r9, 1
    je      .gdone
    mov     rax, r8
    add     rax, r10
    mov     rsi, [Mnum + rax*8]
    mov     rdx, rsi
    sar     rdx, 63
    xor     rsi, rdx
    sub     rsi, rdx
    test    rsi, rsi
    jz      .gnext
    mov     rdi, r9
    call    gcd
    mov     r9, rax
.gnext:
    inc     r10
    jmp     .gloop
.gdone:
    cmp     r9, 1
    jle     .done
    mov     rax, [rowden + r11*8]
    xor     rdx, rdx
    div     r9
    mov     [rowden + r11*8], rax
    xor     r10, r10
.divl:
    cmp     r10, [nb]
    jg      .done
    mov     rax, r8
    add     rax, r10
    mov     rcx, rax
    mov     rax, [Mnum + rcx*8]
    cqo
    idiv    r9
    mov     [Mnum + rcx*8], rax
    inc     r10
    jmp     .divl
.done:
    ret