refactor: add remaining days

1 files changed, 784 insertions, 0 deletions

diff --git a/aoc-2025/day10.asm b/aoc-2025/day10.asm
new file mode 100644
index 0000000..02582b2
--- /dev/null
+++ b/aoc-2025/day10.asm
@@ -0,0 +1,784 @@
+; Advent of Code 2025 - Day 10
+
+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 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
+
+    newline    db 10
+
+    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
+
+    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
+
+    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
+
+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
+
+