From 054d372a716bca4f628674e524e3d027f6824019 Mon Sep 17 00:00:00 2001 From: hachem Date: Sun, 6 Sep 2026 04:12:25 +0200 Subject: refactor: clean up repository layout --- aoc-2025/day10.asm | 695 ----------------------------------------------------- 1 file changed, 695 deletions(-) delete mode 100644 aoc-2025/day10.asm (limited to 'aoc-2025/day10.asm') 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 -- cgit v1.3