hachem.wtf
aboutsummaryrefslogtreecommitdiff
path: root/aoc-2025/day10.asm
diff options
context:
space:
mode:
Diffstat (limited to 'aoc-2025/day10.asm')
-rw-r--r--aoc-2025/day10.asm695
1 files changed, 0 insertions, 695 deletions
diff --git a/aoc-2025/day10.asm b/aoc-2025/day10.asm
deleted file mode 100644
index 456752c..0000000
--- a/aoc-2025/day10.asm
+++ /dev/null
@@ -1,695 +0,0 @@
-; 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
<im@hachem.wtf>