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 --- 2025/day1.asm | 228 ++++++++++++++++ 2025/day10.asm | 695 +++++++++++++++++++++++++++++++++++++++++++++++ 2025/day11.asm | 233 ++++++++++++++++ 2025/day12.asm | 486 +++++++++++++++++++++++++++++++++ 2025/day2.asm | 324 ++++++++++++++++++++++ 2025/day3.asm | 234 ++++++++++++++++ 2025/day4.asm | 236 ++++++++++++++++ 2025/day5.asm | 225 +++++++++++++++ 2025/day6.asm | 331 ++++++++++++++++++++++ 2025/day7.asm | 302 ++++++++++++++++++++ 2025/day8.asm | 326 ++++++++++++++++++++++ 2025/day9.asm | 540 ++++++++++++++++++++++++++++++++++++ Dockerfile | 5 +- Makefile | 6 +- README.md | 15 +- aoc-2025/day1.asm | 228 ---------------- aoc-2025/day10.asm | 695 ----------------------------------------------- aoc-2025/day11.asm | 233 ---------------- aoc-2025/day12.asm | 486 --------------------------------- aoc-2025/day2.asm | 324 ---------------------- aoc-2025/day3.asm | 234 ---------------- aoc-2025/day4.asm | 236 ---------------- aoc-2025/day5.asm | 225 --------------- aoc-2025/day6.asm | 331 ---------------------- aoc-2025/day7.asm | 302 -------------------- aoc-2025/day8.asm | 326 ---------------------- aoc-2025/day9.asm | 540 ------------------------------------ aoc-2025/utils/io.asm | 107 -------- aoc-2025/utils/parse.asm | 22 -- utils/io.asm | 107 ++++++++ utils/parse.asm | 22 ++ 31 files changed, 4304 insertions(+), 4300 deletions(-) create mode 100644 2025/day1.asm create mode 100644 2025/day10.asm create mode 100644 2025/day11.asm create mode 100644 2025/day12.asm create mode 100644 2025/day2.asm create mode 100644 2025/day3.asm create mode 100644 2025/day4.asm create mode 100644 2025/day5.asm create mode 100644 2025/day6.asm create mode 100644 2025/day7.asm create mode 100644 2025/day8.asm create mode 100644 2025/day9.asm delete mode 100644 aoc-2025/day1.asm delete mode 100644 aoc-2025/day10.asm delete mode 100644 aoc-2025/day11.asm delete mode 100644 aoc-2025/day12.asm delete mode 100644 aoc-2025/day2.asm delete mode 100644 aoc-2025/day3.asm delete mode 100644 aoc-2025/day4.asm delete mode 100644 aoc-2025/day5.asm delete mode 100644 aoc-2025/day6.asm delete mode 100644 aoc-2025/day7.asm delete mode 100644 aoc-2025/day8.asm delete mode 100644 aoc-2025/day9.asm delete mode 100644 aoc-2025/utils/io.asm delete mode 100644 aoc-2025/utils/parse.asm create mode 100644 utils/io.asm create mode 100644 utils/parse.asm diff --git a/2025/day1.asm b/2025/day1.asm new file mode 100644 index 0000000..928e7a5 --- /dev/null +++ b/2025/day1.asm @@ -0,0 +1,228 @@ +; Advent of Code 2025 - Day 1 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" + +section .data + input_path db "input/day1.txt", 0 + + label1 db "Password 1: ", 0 + label2 db "Password 2: ", 0 + + angle1 dd 50 + angle2 dd 50 + + password1 dd 0 + password2 dd 0 + +section .bss + buffer resb 4096 + line_buffer resb 256 + line_len resd 1 + +section .text + +_start: + ; open file + mov rax, SYS_OPEN + mov rdi, input_path + mov rsi, O_RDONLY + xor rdx, rdx + syscall + + mov r12, rax ; fd in R12 + mov dword [line_len], 0 ; no chars in current line yet + +read_loop: + ; read up to 4096 bytes + mov rax, SYS_READ + mov rdi, r12 + mov rsi, buffer + mov rdx, 4096 + syscall + + cmp rax, 0 + jle eof ; <=0 -> EOF or error + + mov rdi, buffer ; scan pointer + mov rbp, rax ; bytes remaining in this chunk + +scan_chunk: + cmp rbp, 0 + je read_loop ; chunk done, read next + + mov al, [rdi] + + ; windows can be a fucking bitch + ; handle (CR) -> just skip + cmp al, 13 + je skip_cr + + ; handle LF (10) -> end of line + cmp al, 10 + je end_of_line + + ; normal character -> append to line_buffer if space left + mov edx, [line_len] + cmp edx, 255 ; leave 1 byte for NULL + jae skip_store ; ignore extra characters if too long + mov [line_buffer+rdx], al + inc edx + mov [line_len], edx + +skip_store: + inc rdi + dec rbp + jmp scan_chunk + +skip_cr: + inc rdi + dec rbp + jmp scan_chunk + +end_of_line: + ; terminate current line + mov edx, [line_len] + mov byte [line_buffer+rdx], 0 + + ; if line isn't empty, process it + cmp edx, 0 + je line_done + + push rdi + mov rsi, line_buffer + call handle_line + pop rdi + +line_done: + mov dword [line_len], 0 ; reset line length + inc rdi + dec rbp + jmp scan_chunk + +; process last line if not newline-terminated, then print result +eof: + ; if there is a partial line at EOF, process it + mov edx, [line_len] + cmp edx, 0 + jle print_results + mov byte [line_buffer+rdx], 0 + + mov rsi, line_buffer + call handle_line + +print_results: + mov rcx, label1 + call print_string + mov eax, [password1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov eax, [password2] + call print_int64 + call print_newline + + mov rax, SYS_CLOSE + mov rdi, r12 + syscall + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; Handle one line: RSI -> "L123" or "R45" +handle_line: + mov al, [rsi] + cmp al, 'L' + je .left + mov ebx, 1 ; direction = +1 for 'R' or anything else + jmp .after +.left: + mov ebx, -1 ; direction = -1 for 'L' +.after: + inc rsi ; skip 'L' or 'R' + call parse_int ; EAX = steps + mov ecx, eax + +; Part 1 +p1_start: + mov eax, ecx + imul eax, ebx + add eax, [angle1] + call normalize_angle + mov [angle1], eax + cmp eax, 0 + jne p2_start + mov rdi, password1 + mov edx, [rdi] + inc edx + mov [rdi], edx + +; Part 2 +p2_start: + mov rdi, password2 +.loop: + test ecx, ecx + jle p2_exit + dec ecx + + mov eax, [angle2] + call update_angle_count + mov [angle2], eax + + jmp .loop +p2_exit: + ret + +; normalize eax to 0..99 +normalize_angle: + cmp eax, 0 + jl .add + cmp eax, 100 + jl .done + sub eax, 100 + jmp normalize_angle +.add: + add eax, 100 + jmp normalize_angle +.done: + ret + +; eax = angle, ebx = direction, rdi = password counter addr +update_angle_count: + add eax, ebx + call normalize_angle + + cmp eax, 0 + jne .done + mov edx, [rdi] + inc edx + mov [rdi], edx +.done: + ret + +; parse ASCII integer into EAX +parse_int: + xor eax, eax ; result = 0 +.parse_loop: + mov dl, [rsi] + cmp dl, '0' + jl .done + cmp dl, '9' + jg .done + + sub dl, '0' ; digit value 0..9 + movzx edx, dl + + imul eax, eax, 10 ; result *= 10 + add eax, edx ; result += digit + + inc rsi + jmp .parse_loop +.done: + ret diff --git a/2025/day10.asm b/2025/day10.asm new file mode 100644 index 0000000..456752c --- /dev/null +++ b/2025/day10.asm @@ -0,0 +1,695 @@ +; 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 diff --git a/2025/day11.asm b/2025/day11.asm new file mode 100644 index 0000000..c3cd930 --- /dev/null +++ b/2025/day11.asm @@ -0,0 +1,233 @@ +; Advent of Code 2025 - Day 11 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" + +%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 + + 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 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; 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 diff --git a/2025/day12.asm b/2025/day12.asm new file mode 100644 index 0000000..8931a2b --- /dev/null +++ b/2025/day12.asm @@ -0,0 +1,486 @@ +; Advent of Code 2025 - Day 12 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" +%include "utils/parse.asm" + +%define RAW_SIZE 262144 +%define GRID_SIZE 4096 ; regions are at most 50x50 + +section .data + input_path db "input/day12.txt", 0 + + label1 db "Part 1: ", 0 + +section .bss + raw resb RAW_SIZE + + base_r resd (6 * 9) ; parsed shape cells + base_c resd (6 * 9) + base_n resq 6 ; cells per shape (also its area cost) + + odr resd (6 * 8 * 9) ; orientation cell offsets from anchor + odc resd (6 * 8 * 9) + oncells resq (6 * 8) + + tr resd 9 ; scratch for orientation building + tc resd 9 + + grid resb GRID_SIZE + remaining resq 6 + counts resq 6 + + raw_len resq 1 + cursor resq 1 + pend resq 1 + cur_shape resq 1 + shape_row resq 1 + orients_done resq 1 + rW resq 1 + rL resq 1 + area resq 1 + left resq 1 + count_feasible resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; parse shapes and regions + lea rsi, [raw] + mov rax, [raw_len] + lea rax, [raw + rax] + mov [pend], rax + mov qword [cur_shape], 0 + mov qword [orients_done], 0 +pline: + cmp rsi, [pend] + jae pdone + mov al, [rsi] + cmp al, 10 + je pskip + cmp al, 13 + je pskip + cmp al, ' ' + je pskip + cmp al, '0' + jl maybe_grid + cmp al, '9' + jg maybe_grid + ; a number begins the line + call parse_u64 + mov r10, rax + mov al, [rsi] + cmp al, 'x' + je region_line + ; shape header "N:" + inc rsi + mov [cur_shape], r10 + mov qword [base_n + r10*8], 0 + mov qword [shape_row], 0 + jmp eol + +region_line: + cmp qword [orients_done], 0 + jne .have + mov [cursor], rsi + call gen_orients + mov rsi, [cursor] + mov qword [orients_done], 1 +.have: + inc rsi ; skip 'x' + call parse_u64 + mov r11, rax ; L +.find_colon: + mov al, [rsi] + inc rsi + cmp al, ':' + jne .find_colon + xor rcx, rcx +.rcounts: + cmp rcx, 6 + jge .rcounts_done +.rsp: + mov al, [rsi] + cmp al, ' ' + jne .rsp_done + inc rsi + jmp .rsp +.rsp_done: + call parse_u64 + mov [counts + rcx*8], rax + inc rcx + jmp .rcounts +.rcounts_done: + mov [cursor], rsi + mov rdi, r10 ; W + mov rsi, r11 ; L + call solve_region + mov rsi, [cursor] + jmp eol + +maybe_grid: + cmp al, '#' + je grid_row + cmp al, '.' + je grid_row + inc rsi + jmp pline +grid_row: + mov r10, [cur_shape] + mov r11, [shape_row] + xor rcx, rcx ; column +.cell: + mov al, [rsi] + cmp al, '#' + je .hash + cmp al, '.' + je .dot + jmp .row_done +.hash: + mov rax, r10 + imul rax, 9 + add rax, [base_n + r10*8] + mov edx, r11d + mov [base_r + rax*4], edx + mov edx, ecx + mov [base_c + rax*4], edx + inc qword [base_n + r10*8] +.dot: + inc rcx + inc rsi + jmp .cell +.row_done: + inc qword [shape_row] + jmp eol + +eol: + cmp rsi, [pend] + jae pdone + mov al, [rsi] + inc rsi + cmp al, 10 + jne eol + jmp pline +pskip: + inc rsi + jmp pline +pdone: + + mov rcx, label1 + call print_string + mov rax, [count_feasible] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; gen_orients: build the 8 dihedral orientations of every shape as offset lists +; anchored at their row-major-first cell. +gen_orients: + xor r12, r12 ; shape +.s_loop: + cmp r12, 6 + jge .done + xor r13, r13 ; transform 0..7 +.t_loop: + cmp r13, 8 + jge .s_next + mov r14, [base_n + r12*8] + xor rcx, rcx +.k_loop: + cmp rcx, r14 + jge .k_done + mov rax, r12 + imul rax, 9 + add rax, rcx + movsxd r8, dword [base_r + rax*4] + movsxd r9, dword [base_c + rax*4] + test r13, 4 + jz .noflip + neg r9 +.noflip: + mov rdx, r13 + and rdx, 3 +.rot: + test rdx, rdx + jz .rot_done + mov r15, r8 + mov r8, r9 ; new r = c + mov r9, r15 + neg r9 ; new c = -r + dec rdx + jmp .rot +.rot_done: + mov [tr + rcx*4], r8d + mov [tc + rcx*4], r9d + inc rcx + jmp .k_loop +.k_done: + ; min row + movsxd r8, dword [tr] + xor rcx, rcx +.minr: + cmp rcx, r14 + jge .minr_done + movsxd rax, dword [tr + rcx*4] + cmp rax, r8 + jge .minr_next + mov r8, rax +.minr_next: + inc rcx + jmp .minr +.minr_done: + ; min col among cells on the min row + mov r9, 0x7fffffff + xor rcx, rcx +.minc: + cmp rcx, r14 + jge .minc_done + movsxd rax, dword [tr + rcx*4] + cmp rax, r8 + jne .minc_next + movsxd rax, dword [tc + rcx*4] + cmp rax, r9 + jge .minc_next + mov r9, rax +.minc_next: + inc rcx + jmp .minc +.minc_done: + mov r11, r12 + shl r11, 3 + add r11, r13 ; orientation index + mov [oncells + r11*8], r14 + xor rcx, rcx +.store: + cmp rcx, r14 + jge .store_done + movsxd rax, dword [tr + rcx*4] + sub rax, r8 ; dr + movsxd rdx, dword [tc + rcx*4] + sub rdx, r9 ; dc + mov rbx, r11 + imul rbx, 9 + add rbx, rcx + mov [odr + rbx*4], eax + mov [odc + rbx*4], edx + inc rcx + jmp .store +.store_done: + inc r13 + jmp .t_loop +.s_next: + inc r12 + jmp .s_loop +.done: + ret + +; solve_region(RDI=W, RSI=L): if the region can fit all presents in `counts`, +; increment count_feasible. +solve_region: + xor r8, r8 ; total cells + xor rcx, rcx +.tot: + cmp rcx, 6 + jge .tot_done + mov rax, [counts + rcx*8] + imul rax, [base_n + rcx*8] + add r8, rax + inc rcx + jmp .tot +.tot_done: + mov rax, rdi + imul rax, rsi + mov [area], rax + mov [rW], rdi + mov [rL], rsi + cmp r8, rax + jg .ret ; more cells than space -> impossible + mov r9, rax + sub r9, r8 ; empty budget + + xor r10, r10 ; piece count + xor rcx, rcx +.setrem: + cmp rcx, 6 + jge .setrem_done + mov rax, [counts + rcx*8] + mov [remaining + rcx*8], rax + add r10, rax + inc rcx + jmp .setrem +.setrem_done: + mov [left], r10 + + mov rcx, [area] + lea rdi, [grid] + xor al, al + rep stosb + + xor rdi, rdi ; pos = 0 + mov rsi, r9 ; empty budget + call rec + test rax, rax + jz .ret + inc qword [count_feasible] +.ret: + ret + +; rec(RDI=pos, RSI=empty_budget) -> RAX 1 if the remaining pieces fit. +; State: R12=pos R13=eb R14=row R15=col RBX=shape RBP=orientation. +rec: + push rbx + push rbp + push r12 + push r13 + push r14 + push r15 + mov r12, rdi + mov r13, rsi + cmp qword [left], 0 + je .true +.adv: + cmp r12, [area] + jae .false + cmp byte [grid + r12], 0 + je .found + inc r12 + jmp .adv +.found: + mov rax, r12 + xor rdx, rdx + div qword [rW] + mov r14, rax ; row + mov r15, rdx ; col + + xor rbx, rbx ; shape +.s_loop: + cmp rbx, 6 + jge .try_empty + cmp qword [remaining + rbx*8], 0 + je .s_next + xor rbp, rbp ; orientation +.t_loop: + cmp rbp, 8 + jge .s_next + mov rax, rbx + shl rax, 3 + add rax, rbp + mov r10, rax ; orientation index + mov r11, [oncells + r10*8] + ; validate placement + xor rcx, rcx +.chk: + cmp rcx, r11 + jge .place + mov rax, r10 + imul rax, 9 + add rax, rcx + movsxd r8, dword [odr + rax*4] + movsxd r9, dword [odc + rax*4] + add r8, r14 ; rr + add r9, r15 ; cc + cmp r8, [rL] + jge .t_next + cmp r9, 0 + jl .t_next + cmp r9, [rW] + jge .t_next + mov rax, r8 + imul rax, [rW] + add rax, r9 + cmp byte [grid + rax], 0 + jne .t_next + inc rcx + jmp .chk +.place: + xor rcx, rcx +.place_k: + cmp rcx, r11 + jge .place_done + mov rax, r10 + imul rax, 9 + add rax, rcx + movsxd r8, dword [odr + rax*4] + movsxd r9, dword [odc + rax*4] + add r8, r14 + add r9, r15 + imul r8, [rW] + add r8, r9 + mov byte [grid + r8], 1 + inc rcx + jmp .place_k +.place_done: + dec qword [remaining + rbx*8] + dec qword [left] + mov rdi, r12 + mov rsi, r13 + call rec + test rax, rax + jnz .true + inc qword [remaining + rbx*8] + inc qword [left] + mov rax, rbx ; child clobbered r10/r11 - rebuild them + shl rax, 3 + add rax, rbp + mov r10, rax + mov r11, [oncells + r10*8] + xor rcx, rcx +.unplace_k: + cmp rcx, r11 + jge .unplace_done + mov rax, r10 + imul rax, 9 + add rax, rcx + movsxd r8, dword [odr + rax*4] + movsxd r9, dword [odc + rax*4] + add r8, r14 + add r9, r15 + imul r8, [rW] + add r8, r9 + mov byte [grid + r8], 0 + inc rcx + jmp .unplace_k +.unplace_done: +.t_next: + inc rbp + jmp .t_loop +.s_next: + inc rbx + jmp .s_loop +.try_empty: + test r13, r13 + jz .false + mov byte [grid + r12], 1 + mov rdi, r12 + mov rsi, r13 + dec rsi + call rec + test rax, rax + jnz .true + mov byte [grid + r12], 0 +.false: + xor eax, eax + jmp .ret +.true: + mov eax, 1 +.ret: + pop r15 + pop r14 + pop r13 + pop r12 + pop rbp + pop rbx + ret diff --git a/2025/day2.asm b/2025/day2.asm new file mode 100644 index 0000000..987fbf9 --- /dev/null +++ b/2025/day2.asm @@ -0,0 +1,324 @@ +; Advent of Code 2025 – Day 2 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" +%include "utils/parse.asm" + +section .data + input_path db "input/day2.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + buffer resb 4096 + line_buffer resb 65536 + line_len resd 1 + + sum1 resq 1 + sum2 resq 1 + +section .text + +_start: + mov rax, SYS_OPEN + mov rdi, input_path + mov rsi, O_RDONLY + xor rdx, rdx + syscall + + mov r12, rax ; file descriptor + mov dword [line_len], 0 + +read_loop: + mov rax, SYS_READ + mov rdi, r12 + mov rsi, buffer + mov rdx, 4096 + syscall + + cmp rax, 0 + jle eof + + mov rdi, buffer + mov rbp, rax + +scan_chunk: + cmp rbp, 0 + je read_loop + + mov al, [rdi] + + cmp al, 13 + je skip_cr + + cmp al, 10 + je end_line + + mov edx, [line_len] + cmp edx, 65535 + jae skip_store + mov [line_buffer+rdx], al + inc edx + mov [line_len], edx + +skip_store: + inc rdi + dec rbp + jmp scan_chunk + +skip_cr: + inc rdi + dec rbp + jmp scan_chunk + +end_line: + mov edx, [line_len] + mov byte [line_buffer+rdx], 0 + + cmp edx, 0 + je clear_line + + push rdi + mov rsi, line_buffer + call handle_line + pop rdi + +clear_line: + mov dword [line_len], 0 + inc rdi + dec rbp + jmp scan_chunk + +eof: + ; process final partial line if needed + mov edx, [line_len] + cmp edx, 0 + jle print_results + + mov byte [line_buffer+rdx], 0 + mov rsi, line_buffer + call handle_line + +print_results: + mov rcx, label1 + call print_string + mov rax, [sum1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [sum2] + call print_int64 + call print_newline + + mov rax, SYS_CLOSE + mov rdi, r12 + syscall + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; parse "A-B,C-D,..."l, RSI = pointer to line +; uses r13 = current ID, r14 = end of range +handle_line: +next_range: + ; parse start + call parse_u64 + mov r13, rax + + cmp byte [rsi], '-' + jne done_line + inc rsi + + ; parse end + call parse_u64 + mov r14, rax + +range_loop: + cmp r13, r14 + jg after_range + + ; Save RSI (line pointer) across the checks, + ; because number_to_string / check_invalid* use RSI + push rsi + + ; Part 1: exact AA + mov rax, r13 + call check_invalid1 + test rax, rax + jz .skip_p1 + add qword [sum1], r13 +.skip_p1: + ; Part 2: any repeating block >= 2 + mov rax, r13 + call check_invalid2 + test rax, rax + jz .skip_p2 + add qword [sum2], r13 +.skip_p2: + pop rsi ; restore line pointer + + inc r13 + jmp range_loop + +after_range: + cmp byte [rsi], ',' + jne done_line + inc rsi + jmp next_range + +done_line: + ret + +; number_to_string: convert RAX to decimal ASCII, MSB-first +; Output: +; RSI = pointer to first digit +; ECX = length +number_to_string: + mov rdi, number_buffer+31 + mov byte [rdi], 0 ; terminator (for convenience) + dec rdi + + cmp rax, 0 + jne .conv + + ; handle zero + mov byte [rdi], '0' + mov rsi, rdi + mov ecx, 1 + ret + +.conv: + mov rbx, 10 +.next_digit: + xor rdx, rdx + div rbx ; RAX = quotient, RDX = remainder + add dl, '0' + mov [rdi], dl + dec rdi + test rax, rax + jnz .next_digit + + inc rdi ; now RDI points to first digit + mov rsi, rdi + mov rdx, number_buffer+31 + sub rdx, rsi ; RDX = length + mov ecx, edx + ret + +; check_invalid1: "AA" pattern +; RAX = number +; Returns RAX = 1 if digits == A A, else 0 +check_invalid1: + push rbx + push rdx + + call number_to_string ; RSI=string, ECX=len + mov eax, ecx ; EAX = len + + cmp eax, 2 + jl .no1 + + test eax, 1 + jnz .no1 ; odd length => cannot be AA + + shr eax, 1 ; half = len/2 + mov r8d, eax ; half + xor r9d, r9d ; i = 0 + +.loop1: + cmp r9d, r8d + jge .yes1 + + ; s[i] + mov rdx, r9 + movzx eax, byte [rsi + rdx] + + ; s[i+half] + mov rdx, r9 + add rdx, r8 + movzx ebx, byte [rsi + rdx] + + cmp eax, ebx + jne .no1 + + inc r9d + jmp .loop1 + +.yes1: + mov rax, 1 + jmp .ret1 + +.no1: + xor rax, rax + +.ret1: + pop rdx + pop rbx + ret + +; check_invalid2: any repeating block >= 2 +; RAX = number +; Returns RAX = 1 if string is some A repeated k>=2 times +check_invalid2: + push rbx + push rdx + + call number_to_string ; RSI=string, ECX=len + mov r11d, ecx ; n = length + + cmp r11d, 2 + jb .no2 + + mov r8d, 1 ; m = 1 (candidate period) +.outer: + cmp r8d, r11d + jge .no2 + + ; if n % m != 0 => cannot tile + mov eax, r11d + xor edx, edx + div r8d ; EAX=q, EDX=r + test edx, edx + jnz .next_m + + mov r9d, r11d + sub r9d, r8d ; limit = n - m + xor r10d, r10d ; i = 0 +.inner: + cmp r10d, r9d + jge .yes2 ; all positions checked + + ; s[i] + mov rdx, r10 + movzx eax, byte [rsi + rdx] + + ; s[i+m] + mov rdx, r10 + add rdx, r8 + movzx ebx, byte [rsi + rdx] + + cmp eax, ebx + jne .next_m + + inc r10d + jmp .inner +.yes2: + mov rax, 1 + jmp .ret2 +.next_m: + inc r8d + jmp .outer +.no2: + xor rax, rax +.ret2: + pop rdx + pop rbx + ret diff --git a/2025/day3.asm b/2025/day3.asm new file mode 100644 index 0000000..8330755 --- /dev/null +++ b/2025/day3.asm @@ -0,0 +1,234 @@ +; Advent of Code 2025 - Day 3 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" + +section .data + input_path db "input/day3.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + buffer resb 4096 + line_buffer resb 65536 + line_len resd 1 + + sum1 resq 1 + sum2 resq 1 + + work_digits resb 64 ; stack for greedy subsequence + +section .text + +_start: + mov rax, SYS_OPEN + mov rdi, input_path + mov rsi, O_RDONLY + xor rdx, rdx + syscall + + mov r12, rax ; fd + mov dword [line_len], 0 + +read_loop: + mov rax, SYS_READ + mov rdi, r12 + mov rsi, buffer + mov rdx, 4096 + syscall + + cmp rax, 0 + jle eof + + mov rdi, buffer + mov rbp, rax + +scan_chunk: + cmp rbp, 0 + je read_loop + + mov al, [rdi] + + cmp al, 13 + je skip_cr + + cmp al, 10 + je end_line + + mov edx, [line_len] + cmp edx, 65535 + jae skip_store + mov [line_buffer+rdx], al + inc edx + mov [line_len], edx + +skip_store: + inc rdi + dec rbp + jmp scan_chunk + +skip_cr: + inc rdi + dec rbp + jmp scan_chunk + +end_line: + mov edx, [line_len] + mov byte [line_buffer+edx], 0 + + cmp edx, 0 + je clear_line + + push rdi + mov rsi, line_buffer + call handle_line + pop rdi + +clear_line: + mov dword [line_len], 0 + inc rdi + dec rbp + jmp scan_chunk + +eof: + ; possible last partial line + mov edx, [line_len] + cmp edx, 0 + jle print_results + + mov byte [line_buffer+edx], 0 + mov rsi, line_buffer + call handle_line + +print_results: + mov rcx, label1 + call print_string + mov rax, [sum1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [sum2] + call print_int64 + call print_newline + + mov rax, SYS_CLOSE + mov rdi, r12 + syscall + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +handle_line: + mov rdi, rsi + xor ecx, ecx ; ECX = 0 +.length_loop: + mov al, [rdi+rcx] + cmp al, 0 + je .length_done + inc ecx + jmp .length_loop +.length_done: + mov r15d, ecx ; r15d = n + + ; part 1: k = 2 + mov ecx, r15d ; ECX = n + mov edi, 2 ; K = 2 + call get_max_for_k ; RAX = best 2-digit value + add qword [sum1], rax + + ; part 2: k = 12, only if n >= 12 + cmp r15d, 12 + jl .skip_part2 + + mov ecx, r15d + mov edi, 12 + call get_max_for_k ; RAX = best 12-digit value + add qword [sum2], rax + +.skip_part2: + ret + +; Greedy lexicographically largest subsequence of length K +; +; Input: +; RSI -> digits string +; ECX = n (length) +; EDI = k +; Output: +; RAX = numeric value of chosen k digits +; Clobbers: R8..R11, EAX, EDX +get_max_for_k: + ; drops_remaining = n - k + mov eax, ecx + sub eax, edi + mov r8d, eax ; r8d = drops + + xor r9d, r9d ; r9d = stack_size + xor r10d, r10d ; r10d = i + +.loop: + cmp r10d, ecx + jge .after_input + + ; current digit in AL + mov r11, r10 + mov al, [rsi + r11] + +.pop: + cmp r9d, 0 + jle .push + cmp r8d, 0 + jle .push + + mov edx, r9d + dec edx + mov r11d, edx + mov bl, [work_digits + r11] + + cmp bl, al + jge .push + + dec r9d + dec r8d + jmp .pop +.push: + mov r11d, r9d + mov [work_digits + r11], al + inc r9d + inc r10d + jmp .loop + +.after_input: + ; trim if stack_size > k +.trim: + cmp r9d, edi + jle .convert + dec r9d + jmp .trim +.convert: + xor rax, rax + xor r11d, r11d +.convert_loop: + cmp r11d, edi + jge .done + + mov rdx, r11 + mov dl, [work_digits + rdx] + sub dl, '0' + movzx rdx, dl + + imul rax, rax, 10 + add rax, rdx + + inc r11d + jmp .convert_loop +.done: + ret diff --git a/2025/day4.asm b/2025/day4.asm new file mode 100644 index 0000000..60e53ec --- /dev/null +++ b/2025/day4.asm @@ -0,0 +1,236 @@ +; Advent of Code 2025 - Day 4 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" + +%define RAW_SIZE 4194304 ; 4 MiB scratch for the raw file +%define GRID_SIZE 4194304 ; 4 MiB for the padded grid / mark buffers + +section .data + input_path db "input/day4.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE ; raw file bytes + grid resb GRID_SIZE ; padded grid: 1 = roll, 0 = empty + mark resb GRID_SIZE ; per-round removal marks + + raw_len resq 1 + width resq 1 ; real columns per row + height resq 1 ; real rows + stride resq 1 ; width + 2 (padding on both sides) + + part1 resq 1 + part2 resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + xor rcx, rcx ; column scanner +width_scan: + cmp rcx, [raw_len] + jge width_done + mov al, [raw + rcx] + cmp al, 13 ; CR + je width_done + cmp al, 10 ; LF + je width_done + inc rcx + jmp width_scan +width_done: + mov [width], rcx + add rcx, 2 ; padding on left + right + mov [stride], rcx + + ; real cell (r, c) lives at grid[(r+1)*stride + (c+1)] + mov r10, [raw_len] + xor r8, r8 ; i (raw index) + xor r9, r9 ; r (row, 0-based) + xor r11, r11 ; c (col, 0-based) +fill_loop: + cmp r8, r10 + jge fill_end + mov al, [raw + r8] + inc r8 + + cmp al, 13 ; CR -> ignore + je fill_loop + cmp al, 10 ; LF -> end of line + je fill_newline + + cmp al, '@' + jne fill_next_col ; '.' leaves the zeroed cell alone + + ; grid[(r9+1)*stride + (r11+1)] = 1 + mov rbx, r9 + inc rbx + imul rbx, [stride] + add rbx, r11 + add rbx, 1 + mov byte [grid + rbx], 1 +fill_next_col: + inc r11 + jmp fill_loop +fill_newline: + cmp r11, 0 ; blank line -> skip (e.g. trailing newline) + je fill_loop + inc r9 + xor r11, r11 + jmp fill_loop +fill_end: + cmp r11, 0 ; last line had no trailing newline + je fill_height + inc r9 +fill_height: + mov [height], r9 + + mov r13, 1 ; row = 1..height +p1_row: + cmp r13, [height] + jg p1_done + mov rbx, r13 + imul rbx, [stride] + inc rbx ; idx of (row, col=1) + mov r12, 1 ; col = 1..width +p1_col: + cmp r12, [width] + jg p1_row_next + movzx eax, byte [grid + rbx] + test eax, eax + jz p1_next ; not a roll + mov rdi, rbx + call count_neighbors + cmp rax, 4 + jge p1_next ; 4 or more neighbors -> blocked + inc qword [part1] +p1_next: + inc rbx + inc r12 + jmp p1_col +p1_row_next: + inc r13 + jmp p1_row +p1_done: + +peel_loop: + mov r13, 1 +mark_row: + cmp r13, [height] + jg mark_done + mov rbx, r13 + imul rbx, [stride] + inc rbx + mov r12, 1 +mark_col: + cmp r12, [width] + jg mark_row_next + movzx eax, byte [grid + rbx] + test eax, eax + jz mark_zero ; empty cell + mov rdi, rbx + call count_neighbors + cmp rax, 4 + jl mark_one ; accessible +mark_zero: + mov byte [mark + rbx], 0 + jmp mark_next +mark_one: + mov byte [mark + rbx], 1 +mark_next: + inc rbx + inc r12 + jmp mark_col +mark_row_next: + inc r13 + jmp mark_row +mark_done: + + xor r11, r11 ; removed this round + mov r13, 1 +apply_row: + cmp r13, [height] + jg apply_done + mov rbx, r13 + imul rbx, [stride] + inc rbx + mov r12, 1 +apply_col: + cmp r12, [width] + jg apply_row_next + movzx eax, byte [mark + rbx] + test eax, eax + jz apply_next + mov byte [grid + rbx], 0 + inc r11 +apply_next: + inc rbx + inc r12 + jmp apply_col +apply_row_next: + inc r13 + jmp apply_row +apply_done: + add [part2], r11 + test r11, r11 + jnz peel_loop ; something changed -> another round + +print_results: + mov rcx, label1 + call print_string + mov rax, [part1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [part2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; count_neighbors: sum of the 8 cells around a padded index +; Input: RDI = grid index +; Output: RAX = number of neighboring rolls (0..8) +; Clobbers: RAX, RCX, RDX, R8 +count_neighbors: + mov rcx, [stride] + xor eax, eax + + mov rdx, rdi + sub rdx, rcx ; row above + movzx r8d, byte [grid + rdx - 1] + add eax, r8d + movzx r8d, byte [grid + rdx] + add eax, r8d + movzx r8d, byte [grid + rdx + 1] + add eax, r8d + + movzx r8d, byte [grid + rdi - 1] ; same row, sides + add eax, r8d + movzx r8d, byte [grid + rdi + 1] + add eax, r8d + + mov rdx, rdi + add rdx, rcx ; row below + movzx r8d, byte [grid + rdx - 1] + add eax, r8d + movzx r8d, byte [grid + rdx] + add eax, r8d + movzx r8d, byte [grid + rdx + 1] + add eax, r8d + ret diff --git a/2025/day5.asm b/2025/day5.asm new file mode 100644 index 0000000..4718343 --- /dev/null +++ b/2025/day5.asm @@ -0,0 +1,225 @@ +; Advent of Code 2025 - Day 5 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" +%include "utils/parse.asm" + +%define RAW_SIZE 1048576 ; 1 MiB scratch for the raw file +%define MAX_RANGES 8192 ; plenty for the ~177 input ranges + +section .data + input_path db "input/day5.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + starts resq MAX_RANGES ; range/merged-interval starts + ends resq MAX_RANGES ; range/merged-interval ends + + raw_len resq 1 + n_ranges resq 1 ; ranges parsed in section 1 + n_merged resq 1 ; disjoint intervals after merge + phase resq 1 ; 0 = ranges, 1 = available IDs + + part1 resq 1 + part2 resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; RSI = cursor, R14 = end pointer (both preserved across helper calls) + lea rsi, [raw] + mov rax, [raw_len] + lea r14, [raw + rax] + mov qword [phase], 0 + +scan_line: + cmp rsi, r14 + jae scan_done + mov al, [rsi] + cmp al, 10 ; LF -> blank line + je got_blank + cmp al, 13 ; CR -> blank line + je got_blank + + cmp qword [phase], 0 + jne do_avail + + call parse_u64 ; RAX = start + mov rcx, [n_ranges] + mov [starts + rcx*8], rax + inc rsi ; skip '-' + call parse_u64 ; RAX = end + mov rcx, [n_ranges] + mov [ends + rcx*8], rax + inc qword [n_ranges] + jmp skip_eol + +do_avail: + call parse_u64 + mov rdi, rax + call is_fresh ; RAX = 1 if fresh + test rax, rax + jz skip_eol + inc qword [part1] + jmp skip_eol + +got_blank: + ; the blank line separates the two sections + cmp qword [phase], 0 + jne skip_eol + call finalize_ranges ; sort + merge, compute part2 + mov qword [phase], 1 + ; fall through + +skip_eol: + cmp rsi, r14 + jae scan_done + mov al, [rsi] + inc rsi + cmp al, 10 ; consume through the LF + jne skip_eol + jmp scan_line + +scan_done: + ; safety: if there was no blank line, still finalize the ranges + cmp qword [phase], 0 + jne print_results + call finalize_ranges + +print_results: + mov rcx, label1 + call print_string + mov rax, [part1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [part2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; is_fresh: test membership of an ID in the merged intervals. +; Input: RDI = id +; Output: RAX = 1 if the id lies in any interval, else 0 +; Intervals are sorted ascending and disjoint, so we can stop early. +; Clobbers: RAX, RCX +is_fresh: + xor rcx, rcx +.loop: + cmp rcx, [n_merged] + jge .no + mov rax, [starts + rcx*8] + cmp rdi, rax + jl .no ; id below this start -> below all later ones + mov rax, [ends + rcx*8] + cmp rdi, rax + jle .yes ; start <= id <= end + inc rcx + jmp .loop +.no: + xor eax, eax + ret +.yes: + mov eax, 1 + ret + +; finalize_ranges: insertion-sort the ranges by start, merge overlapping / +; touching ones in place, store the disjoint intervals back into starts/ends, +; set n_merged, and accumulate their total size into part2. +; Clobbers: RAX, RCX, RDX, R8, R9, R10, R11, R12, R13 +finalize_ranges: + mov r8, 1 ; i +.sort_i: + cmp r8, [n_ranges] + jge .sorted + mov r10, [starts + r8*8] ; key_s + mov r11, [ends + r8*8] ; key_e + mov r9, r8 + dec r9 ; j = i - 1 +.sort_j: + cmp r9, 0 + jl .sort_place + mov rax, [starts + r9*8] + cmp rax, r10 + jle .sort_place ; starts[j] <= key -> in place + mov rdx, r9 + inc rdx ; j + 1 + mov [starts + rdx*8], rax ; shift start + mov rcx, [ends + r9*8] + mov [ends + rdx*8], rcx ; shift end + dec r9 + jmp .sort_j +.sort_place: + mov rdx, r9 + inc rdx + mov [starts + rdx*8], r10 + mov [ends + rdx*8], r11 + inc r8 + jmp .sort_i +.sorted: + + cmp qword [n_ranges], 0 + je .empty + + mov r10, [starts] ; cur_lo + mov r11, [ends] ; cur_hi + mov r8, 1 ; i + xor r12, r12 ; part2 accumulator + xor r13, r13 ; write index +.merge_loop: + cmp r8, [n_ranges] + jge .flush + mov rax, [starts + r8*8] ; s + mov rcx, [ends + r8*8] ; e + cmp rax, r11 + jg .gap ; s > cur_hi -> disjoint + cmp rcx, r11 ; overlap: cur_hi = max(cur_hi, e) + jle .no_extend + mov r11, rcx +.no_extend: + inc r8 + jmp .merge_loop +.gap: + call .emit + mov r10, rax ; begin new interval + mov r11, rcx + inc r8 + jmp .merge_loop +.flush: + call .emit + mov [n_merged], r13 + mov [part2], r12 + ret +.empty: + mov qword [n_merged], 0 + mov qword [part2], 0 + ret + +; local helper: emit [r10, r11] as merged interval r13, add its size to r12 +.emit: + mov [starts + r13*8], r10 + mov [ends + r13*8], r11 + inc r13 + mov rdx, r11 + sub rdx, r10 + inc rdx ; end - start + 1 + add r12, rdx + ret diff --git a/2025/day6.asm b/2025/day6.asm new file mode 100644 index 0000000..728b8b0 --- /dev/null +++ b/2025/day6.asm @@ -0,0 +1,331 @@ +; Advent of Code 2025 - Day 6 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" + +%define RAW_SIZE 1048576 +%define MAX_W 8192 +%define MAX_H 64 +%define GRID_SIZE (MAX_W * MAX_H) + +section .data + input_path db "input/day6.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + grid resb GRID_SIZE ; height x width, space-filled + + raw_len resq 1 + width resq 1 + height resq 1 + + blk_c0 resq 1 ; current block: columns [blk_c0, blk_c1) + blk_c1 resq 1 + op resq 1 ; 0 = add, 1 = mul, -1 = none + + part1 resq 1 + part2 resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; width = length of the first line + xor rcx, rcx +width_scan: + cmp rcx, [raw_len] + jge width_done + mov al, [raw + rcx] + cmp al, 10 + je width_done + cmp al, 13 + je width_done + inc rcx + jmp width_scan +width_done: + mov [width], rcx + + ; height = number of lines (newlines, plus one if the last line has no newline) + xor rcx, rcx + xor r8, r8 +height_scan: + cmp rcx, [raw_len] + jge height_tail + mov al, [raw + rcx] + cmp al, 10 + jne height_next + inc r8 +height_next: + inc rcx + jmp height_scan +height_tail: + mov rax, [raw_len] + test rax, rax + jz height_store + mov dl, [raw + rax - 1] + cmp dl, 10 + je height_store + inc r8 +height_store: + mov [height], r8 + + ; space-fill the grid, then copy the raw bytes into it + mov rax, [height] + imul rax, [width] + mov rcx, rax + lea rdi, [grid] + mov al, ' ' + rep stosb + + xor r8, r8 ; raw index + xor r9, r9 ; row + xor r10, r10 ; col +fill_loop: + cmp r8, [raw_len] + jge fill_done + mov al, [raw + r8] + inc r8 + cmp al, 10 + je fill_newline + cmp al, 13 + je fill_loop + cmp r10, [width] + jge fill_loop + mov rdx, r9 + imul rdx, [width] + add rdx, r10 + mov [grid + rdx], al + inc r10 + jmp fill_loop +fill_newline: + inc r9 + xor r10, r10 + jmp fill_loop +fill_done: + + ; walk the columns, carving out blocks between all-space separators + xor r15, r15 ; column cursor +block_scan: + cmp r15, [width] + jge blocks_done + mov rdi, r15 + call col_is_sep + test rax, rax + jnz block_sep + mov [blk_c0], r15 +block_extend: + cmp r15, [width] + jge block_end + mov rdi, r15 + call col_is_sep + test rax, rax + jnz block_end + inc r15 + jmp block_extend +block_end: + mov [blk_c1], r15 + call process_block + jmp block_scan +block_sep: + inc r15 + jmp block_scan +blocks_done: + +print_results: + mov rcx, label1 + call print_string + mov rax, [part1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [part2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; col_is_sep: is every row of column RDI a space? +; Output: RAX = 1 if the column is a separator, else 0 +; Clobbers: RAX, RDX, R8 +col_is_sep: + xor r8, r8 +.loop: + cmp r8, [height] + jge .sep + mov rax, r8 + imul rax, [width] + add rax, rdi + movzx edx, byte [grid + rax] + cmp dl, ' ' + jne .not + inc r8 + jmp .loop +.sep: + mov rax, 1 + ret +.not: + xor rax, rax + ret + +; process_block: fold the block [blk_c0, blk_c1) for both parts. +; Part 1 reads each row as a number; part 2 reads each column as a number. +; The bottom row supplies the operator. Clobbers RAX, RCX, RDX, R8-R14. +process_block: + ; find the operator on the bottom row within the block + mov rax, [height] + dec rax + imul rax, [width] + mov r11, rax ; offset of the operator row + mov qword [op], -1 + mov rcx, [blk_c0] +.find_op: + cmp rcx, [blk_c1] + jge .op_done + mov rdx, r11 + add rdx, rcx + mov al, [grid + rdx] + cmp al, '+' + je .set_add + cmp al, '*' + je .set_mul + inc rcx + jmp .find_op +.set_add: + mov qword [op], 0 + jmp .op_done +.set_mul: + mov qword [op], 1 +.op_done: + cmp qword [op], 0 + jl .ret ; no operator -> not a real problem + + ; part 1: one number per row + mov r12, [op] + xor r13, r13 ; accumulator + test r12, r12 + jz .p1_acc + mov r13, 1 +.p1_acc: + xor r14, r14 ; count of numbers folded + xor r10, r10 ; row +.p1_rows: + mov rax, [height] + dec rax + cmp r10, rax + jge .p1_done + mov rax, r10 + imul rax, [width] + mov r11, rax ; row offset + xor r8, r8 ; number + xor r9, r9 ; saw a digit? + mov rcx, [blk_c0] +.p1_cols: + cmp rcx, [blk_c1] + jge .p1_fold + mov rdx, r11 + add rdx, rcx + movzx eax, byte [grid + rdx] + cmp al, '0' + jl .p1_col_next + cmp al, '9' + jg .p1_col_next + sub al, '0' + movzx rax, al + imul r8, r8, 10 + add r8, rax + mov r9, 1 +.p1_col_next: + inc rcx + jmp .p1_cols +.p1_fold: + test r9, r9 + jz .p1_row_next + test r12, r12 + jnz .p1_mul + add r13, r8 + jmp .p1_counted +.p1_mul: + imul r13, r8 +.p1_counted: + inc r14 +.p1_row_next: + inc r10 + jmp .p1_rows +.p1_done: + test r14, r14 + jz .p2 + add [part1], r13 + + ; part 2: one number per column +.p2: + mov r12, [op] + xor r13, r13 + test r12, r12 + jz .p2_acc + mov r13, 1 +.p2_acc: + xor r14, r14 + mov rcx, [blk_c0] ; column +.p2_cols: + cmp rcx, [blk_c1] + jge .p2_done + xor r8, r8 ; number + xor r9, r9 ; saw a digit? + xor r10, r10 ; row +.p2_rows: + mov rax, [height] + dec rax + cmp r10, rax + jge .p2_fold + mov rax, r10 + imul rax, [width] + add rax, rcx + movzx edx, byte [grid + rax] + cmp dl, '0' + jl .p2_row_next + cmp dl, '9' + jg .p2_row_next + sub dl, '0' + movzx rdx, dl + imul r8, r8, 10 + add r8, rdx + mov r9, 1 +.p2_row_next: + inc r10 + jmp .p2_rows +.p2_fold: + test r9, r9 + jz .p2_col_next + test r12, r12 + jnz .p2_mul + add r13, r8 + jmp .p2_counted +.p2_mul: + imul r13, r8 +.p2_counted: + inc r14 +.p2_col_next: + inc rcx + jmp .p2_cols +.p2_done: + test r14, r14 + jz .ret + add [part2], r13 +.ret: + ret diff --git a/2025/day7.asm b/2025/day7.asm new file mode 100644 index 0000000..1d990a7 --- /dev/null +++ b/2025/day7.asm @@ -0,0 +1,302 @@ +; Advent of Code 2025 - Day 7 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" + +%define RAW_SIZE 1048576 +%define MAX_W 1024 +%define MAX_H 1024 +%define GRID_SIZE (MAX_W * MAX_H) + +section .data + input_path db "input/day7.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + grid resb GRID_SIZE ; height x width, '.'-filled + g resq (MAX_W * MAX_H) ; part 2 timeline counts + cur resb MAX_W ; part 1 active columns (this row) + nxt resb MAX_W ; part 1 active columns (next row) + + raw_len resq 1 + width resq 1 + height resq 1 + srow resq 1 + scol resq 1 + + part1 resq 1 + part2 resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; width = length of the first line + xor rcx, rcx +width_scan: + cmp rcx, [raw_len] + jge width_done + mov al, [raw + rcx] + cmp al, 10 + je width_done + cmp al, 13 + je width_done + inc rcx + jmp width_scan +width_done: + mov [width], rcx + + ; height = number of lines + xor rcx, rcx + xor r8, r8 +height_scan: + cmp rcx, [raw_len] + jge height_tail + mov al, [raw + rcx] + cmp al, 10 + jne height_next + inc r8 +height_next: + inc rcx + jmp height_scan +height_tail: + mov rax, [raw_len] + test rax, rax + jz height_store + mov dl, [raw + rax - 1] + cmp dl, 10 + je height_store + inc r8 +height_store: + mov [height], r8 + + ; '.'-fill the grid, then copy the raw bytes into it + mov rax, [height] + imul rax, [width] + mov rcx, rax + lea rdi, [grid] + mov al, '.' + rep stosb + + xor r8, r8 ; raw index + xor r9, r9 ; row + xor r10, r10 ; col +fill_loop: + cmp r8, [raw_len] + jge fill_done + mov al, [raw + r8] + inc r8 + cmp al, 10 + je fill_newline + cmp al, 13 + je fill_loop + cmp r10, [width] + jge fill_loop + mov rdx, r9 + imul rdx, [width] + add rdx, r10 + mov [grid + rdx], al + inc r10 + jmp fill_loop +fill_newline: + inc r9 + xor r10, r10 + jmp fill_loop +fill_done: + + ; locate S + xor r8, r8 + mov rax, [height] + imul rax, [width] + mov r9, rax +find_s: + cmp r8, r9 + jge s_done + mov al, [grid + r8] + cmp al, 'S' + je s_found + inc r8 + jmp find_s +s_found: + mov rax, r8 + xor rdx, rdx + div qword [width] + mov [srow], rax + mov [scol], rdx +s_done: + + ; part 1: flood a set of active columns, counting splitter hits + lea rdi, [cur] + mov rcx, MAX_W + xor al, al + rep stosb + mov rax, [scol] + mov byte [cur + rax], 1 + + xor r15, r15 ; row +p1_row: + cmp r15, [height] + jge p1_done + lea rdi, [nxt] + mov rcx, MAX_W + xor al, al + rep stosb + + mov rax, r15 + imul rax, [width] + mov r14, rax ; row offset + xor r13, r13 ; col + xor r12, r12 ; any beam alive? +p1_col: + cmp r13, [width] + jge p1_col_done + mov al, [cur + r13] + test al, al + jz p1_next + mov rdx, r14 + add rdx, r13 + mov al, [grid + rdx] + cmp al, '^' + jne p1_pass + inc qword [part1] + mov rbx, r13 ; left neighbor + test rbx, rbx + jz p1_no_left + dec rbx + mov byte [nxt + rbx], 1 + mov r12, 1 +p1_no_left: + mov rbx, r13 ; right neighbor + inc rbx + cmp rbx, [width] + jge p1_no_right + mov byte [nxt + rbx], 1 + mov r12, 1 +p1_no_right: + jmp p1_next +p1_pass: + mov byte [nxt + r13], 1 + mov r12, 1 +p1_next: + inc r13 + jmp p1_col +p1_col_done: + lea rsi, [nxt] + lea rdi, [cur] + mov rcx, MAX_W + rep movsb + test r12, r12 + jz p1_done + inc r15 + jmp p1_row +p1_done: + + ; part 2: bottom-up DP of timeline counts, g[r][c] + mov r15, [height] + dec r15 ; row, counting down +p2_row: + cmp r15, 0 + jl p2_done + mov rax, r15 + imul rax, [width] + mov r14, rax ; row offset + xor r13, r13 ; col +p2_col: + cmp r13, [width] + jge p2_col_done + mov rdx, r14 + add rdx, r13 ; idx = r*W + c + mov al, [grid + rdx] + cmp al, '^' + je p2_split + + ; pass straight down: g = (r+1 in grid ? g[r+1][c] : 1) + mov rbx, r15 + inc rbx + cmp rbx, [height] + jge p2_pass_exit + mov rcx, rdx + add rcx, [width] + mov rax, [g + rcx*8] + jmp p2_store +p2_pass_exit: + mov rax, 1 + jmp p2_store + +p2_split: + ; left child enters (r+1, c-1) + mov rbx, r15 + inc rbx + cmp rbx, [height] + jge p2_left_one + cmp r13, 0 + jle p2_left_one + mov rcx, rdx + add rcx, [width] + dec rcx + mov r8, [g + rcx*8] + jmp p2_left_done +p2_left_one: + mov r8, 1 +p2_left_done: + ; right child enters (r+1, c+1) + mov rbx, r15 + inc rbx + cmp rbx, [height] + jge p2_right_one + mov rbx, r13 + inc rbx + cmp rbx, [width] + jge p2_right_one + mov rcx, rdx + add rcx, [width] + inc rcx + mov r9, [g + rcx*8] + jmp p2_right_done +p2_right_one: + mov r9, 1 +p2_right_done: + mov rax, r8 + add rax, r9 +p2_store: + mov [g + rdx*8], rax + inc r13 + jmp p2_col +p2_col_done: + dec r15 + jmp p2_row +p2_done: + mov rax, [srow] + imul rax, [width] + add rax, [scol] + mov rax, [g + rax*8] + mov [part2], rax + +print_results: + mov rcx, label1 + call print_string + mov rax, [part1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [part2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall diff --git a/2025/day8.asm b/2025/day8.asm new file mode 100644 index 0000000..6a4ecec --- /dev/null +++ b/2025/day8.asm @@ -0,0 +1,326 @@ +; Advent of Code 2025 - Day 8 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" +%include "utils/parse.asm" + +%define RAW_SIZE 262144 +%define MAXN 1024 +%define MAXE (MAXN * (MAXN - 1) / 2) +%define K_LIMIT 1000 ; part 1 connects the K_LIMIT closest pairs + +section .data + input_path db "input/day8.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + x resq MAXN + y resq MAXN + z resq MAXN + + edges resb (MAXE * 16) ; records: [dist2:8][i:4][j:4] + edges2 resb (MAXE * 16) ; radix ping-pong buffer + counts resq 256 + + parent resq MAXN + csize resq MAXN + + raw_len resq 1 + n_boxes resq 1 + m_edges resq 1 + sorted_ptr resq 1 + comp_count resq 1 + + part1 resq 1 + part2 resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; parse "X,Y,Z" lines into x/y/z, counting boxes + lea rsi, [raw] + mov rax, [raw_len] + lea r14, [raw + rax] ; end pointer + xor r12, r12 ; box index +parse_line: + cmp rsi, r14 + jae parse_done + mov al, [rsi] + cmp al, 10 + je parse_skipnl + cmp al, 13 + je parse_skipnl + call parse_u64 + mov [x + r12*8], rax + inc rsi + call parse_u64 + mov [y + r12*8], rax + inc rsi + call parse_u64 + mov [z + r12*8], rax + inc r12 +parse_eol: + cmp rsi, r14 + jae parse_done + mov al, [rsi] + inc rsi + cmp al, 10 + jne parse_eol + jmp parse_line +parse_skipnl: + inc rsi + jmp parse_line +parse_done: + mov [n_boxes], r12 + + ; build every pairwise edge with squared distance as the key + lea r11, [edges] ; write pointer + xor r12, r12 ; edge count + xor r8, r8 ; i +gen_i: + cmp r8, [n_boxes] + jge gen_done + mov r13, [x + r8*8] + mov r14, [y + r8*8] + mov r15, [z + r8*8] + lea r9, [r8 + 1] ; j = i + 1 +gen_j: + cmp r9, [n_boxes] + jge gen_j_done + mov rax, r13 + sub rax, [x + r9*8] + imul rax, rax + mov rcx, rax + mov rax, r14 + sub rax, [y + r9*8] + imul rax, rax + add rcx, rax + mov rax, r15 + sub rax, [z + r9*8] + imul rax, rax + add rcx, rax ; key = dx^2 + dy^2 + dz^2 + mov [r11], rcx + mov [r11 + 8], r8d + mov [r11 + 12], r9d + add r11, 16 + inc r12 + inc r9 + jmp gen_j +gen_j_done: + inc r8 + jmp gen_i +gen_done: + mov [m_edges], r12 + + ; LSD radix sort by the 5 low bytes of the key (max key < 2^40) + lea r11, [edges] ; src + lea r12, [edges2] ; dst + xor r13, r13 ; byte pass 0..4 +rsort_pass: + cmp r13, 5 + jge rsort_done + lea rdi, [counts] + mov rcx, 256 + xor rax, rax + rep stosq + + xor rcx, rcx ; k +rs_hist: + cmp rcx, [m_edges] + jge rs_hist_done + mov rax, rcx + shl rax, 4 + add rax, r11 + movzx edx, byte [rax + r13] + inc qword [counts + rdx*8] + inc rcx + jmp rs_hist +rs_hist_done: + xor rcx, rcx ; t + xor r8, r8 ; running offset +rs_prefix: + cmp rcx, 256 + jge rs_prefix_done + mov rax, [counts + rcx*8] + mov [counts + rcx*8], r8 + add r8, rax + inc rcx + jmp rs_prefix +rs_prefix_done: + xor rcx, rcx ; k +rs_scatter: + cmp rcx, [m_edges] + jge rs_scatter_done + mov rax, rcx + shl rax, 4 + add rax, r11 ; src record + movzx edx, byte [rax + r13] + mov r9, [counts + rdx*8] + inc qword [counts + rdx*8] + mov r10, r9 + shl r10, 4 + add r10, r12 ; dst slot + mov r8, [rax] + mov [r10], r8 + mov r8, [rax + 8] + mov [r10 + 8], r8 + inc rcx + jmp rs_scatter +rs_scatter_done: + xchg r11, r12 + inc r13 + jmp rsort_pass +rsort_done: + mov [sorted_ptr], r11 + + ; union-find init + xor rcx, rcx +dsu_init: + cmp rcx, [n_boxes] + jge dsu_done + mov [parent + rcx*8], rcx + mov qword [csize + rcx*8], 1 + inc rcx + jmp dsu_init +dsu_done: + mov rax, [n_boxes] + mov [comp_count], rax + mov qword [part2], 0 + + ; Kruskal: one sorted pass drives both parts + mov r11, [sorted_ptr] + xor r15, r15 ; edge index +kloop: + cmp r15, [m_edges] + jge kdone + mov r12, r15 + shl r12, 4 + add r12, r11 ; record pointer + mov r13d, [r12 + 8] ; i + mov r14d, [r12 + 12] ; j + + mov edi, r13d + call find + mov rbx, rax ; root of i + mov edi, r14d + call find ; root of j + + cmp rbx, rax + je k_after ; already connected + + mov rcx, [csize + rbx*8] + mov rdx, [csize + rax*8] + cmp rcx, rdx + jge k_no_swap + xchg rbx, rax ; keep rbx as the larger root +k_no_swap: + mov [parent + rax*8], rbx + mov rcx, [csize + rax*8] + add [csize + rbx*8], rcx + dec qword [comp_count] + + cmp qword [comp_count], 1 + jne k_after + cmp qword [part2], 0 + jne k_after + mov rax, [x + r13*8] + imul rax, [x + r14*8] + mov [part2], rax +k_after: + cmp r15, (K_LIMIT - 1) + jne k_check_break + call compute_part1 +k_check_break: + cmp r15, (K_LIMIT - 1) + jl k_next + cmp qword [part2], 0 + je k_next + jmp kdone +k_next: + inc r15 + jmp kloop +kdone: + +print_results: + mov rcx, label1 + call print_string + mov rax, [part1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [part2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; find: union-find root of node RDI, with path halving. +; Output: RAX = root. Clobbers RAX, RDX, RDI. +find: +.loop: + mov rax, [parent + rdi*8] + cmp rax, rdi + je .done + mov rdx, [parent + rax*8] + mov [parent + rdi*8], rdx + mov rdi, rdx + jmp .loop +.done: + ret + +; compute_part1: product of the three largest component sizes into part1. +; Clobbers RAX, RCX, R8, R9, R10. +compute_part1: + xor r8, r8 ; largest + xor r9, r9 ; 2nd + xor r10, r10 ; 3rd + xor rcx, rcx +.loop: + cmp rcx, [n_boxes] + jge .done + mov rax, [parent + rcx*8] + cmp rax, rcx + jne .next ; not a root + mov rax, [csize + rcx*8] + cmp rax, r8 + jle .try2 + mov r10, r9 + mov r9, r8 + mov r8, rax + jmp .next +.try2: + cmp rax, r9 + jle .try3 + mov r10, r9 + mov r9, rax + jmp .next +.try3: + cmp rax, r10 + jle .next + mov r10, rax +.next: + inc rcx + jmp .loop +.done: + mov rax, r8 + imul rax, r9 + imul rax, r10 + mov [part1], rax + ret diff --git a/2025/day9.asm b/2025/day9.asm new file mode 100644 index 0000000..e5a7d0d --- /dev/null +++ b/2025/day9.asm @@ -0,0 +1,540 @@ +; Advent of Code 2025 - Day 9 + +bits 64 +default rel + +global _start + +%include "utils/io.asm" +%include "utils/parse.asm" + +%define RAW_SIZE 262144 +%define MAXN 512 +%define MAXC 1024 +%define MAXR 1024 +%define MAXP ((MAXC + 1) * (MAXR + 1)) + +section .data + input_path db "input/day9.txt", 0 + + label1 db "Part 1: ", 0 + label2 db "Part 2: ", 0 + +section .bss + raw resb RAW_SIZE + vx resq MAXN + vy resq MAXN + xs resq MAXN + ys resq MAXN + xs_to_col resd MAXN + ys_to_row resd MAXN + col_lo resq MAXC + row_lo resq MAXR + thincol resd MAXN + thinrow resd MAXN + + vex resq MAXN ; vertical edges: x, ylo, yhi + veylo resq MAXN + veyhi resq MAXN + hey resq MAXN ; horizontal edges: y, xlo, xhi + hexlo resq MAXN + hexhi resq MAXN + + pref resd MAXP ; 2D prefix sum of unfilled cells + + raw_len resq 1 + n_v resq 1 + xn resq 1 + yn resq 1 + c_cnt resq 1 + r_cnt resq 1 + cp1 resq 1 + ve_cnt resq 1 + he_cnt resq 1 + best1 resq 1 + best2 resq 1 + +section .text + +_start: + mov rdi, input_path + lea rsi, [raw] + mov rdx, RAW_SIZE + call read_file + mov [raw_len], rax + + ; parse "X,Y" vertices in order + lea rsi, [raw] + mov rax, [raw_len] + lea r14, [raw + rax] + xor r12, r12 +parse_line: + cmp rsi, r14 + jae parse_done + mov al, [rsi] + cmp al, 10 + je parse_skipnl + cmp al, 13 + je parse_skipnl + call parse_u64 + mov [vx + r12*8], rax + inc rsi + call parse_u64 + mov [vy + r12*8], rax + inc r12 +parse_eol: + cmp rsi, r14 + jae parse_done + mov al, [rsi] + inc rsi + cmp al, 10 + jne parse_eol + jmp parse_line +parse_skipnl: + inc rsi + jmp parse_line +parse_done: + mov [n_v], r12 + + ; xs = sorted, deduped x coordinates + xor rcx, rcx +copy_xs: + cmp rcx, [n_v] + jge copy_xs_done + mov rax, [vx + rcx*8] + mov [xs + rcx*8], rax + inc rcx + jmp copy_xs +copy_xs_done: + lea rdi, [xs] + mov rsi, [n_v] + call sort_q + lea rdi, [xs] + mov rsi, [n_v] + call dedup_q + mov [xn], rax + + ; ys = sorted, deduped y coordinates + xor rcx, rcx +copy_ys: + cmp rcx, [n_v] + jge copy_ys_done + mov rax, [vy + rcx*8] + mov [ys + rcx*8], rax + inc rcx + jmp copy_ys +copy_ys_done: + lea rdi, [ys] + mov rsi, [n_v] + call sort_q + lea rdi, [ys] + mov rsi, [n_v] + call dedup_q + mov [yn], rax + + ; refined columns: thin at each xs, thick strip between + xor rcx, rcx ; i + xor r12, r12 ; column count +build_cols: + cmp rcx, [xn] + jge build_cols_done + mov [xs_to_col + rcx*4], r12d + mov rax, [xs + rcx*8] + mov [col_lo + r12*8], rax + inc r12 + mov rdx, rcx + inc rdx + cmp rdx, [xn] + jge build_cols_next + mov r8, [xs + rdx*8] + mov rax, [xs + rcx*8] + sub r8, rax + cmp r8, 1 + jle build_cols_next + inc rax + mov [col_lo + r12*8], rax + inc r12 +build_cols_next: + inc rcx + jmp build_cols +build_cols_done: + mov [c_cnt], r12 + inc r12 + mov [cp1], r12 + + ; refined rows: thin at each ys, thick strip between + xor rcx, rcx + xor r12, r12 +build_rows: + cmp rcx, [yn] + jge build_rows_done + mov [ys_to_row + rcx*4], r12d + mov rax, [ys + rcx*8] + mov [row_lo + r12*8], rax + inc r12 + mov rdx, rcx + inc rdx + cmp rdx, [yn] + jge build_rows_next + mov r8, [ys + rdx*8] + mov rax, [ys + rcx*8] + sub r8, rax + cmp r8, 1 + jle build_rows_next + inc rax + mov [row_lo + r12*8], rax + inc r12 +build_rows_next: + inc rcx + jmp build_rows +build_rows_done: + mov [r_cnt], r12 + + ; per-vertex refined thin column / row index + xor r8, r8 +map_v: + cmp r8, [n_v] + jge map_v_done + mov r13, [vx + r8*8] + xor rcx, rcx +map_v_xs: + mov rax, [xs + rcx*8] + cmp rax, r13 + je map_v_xf + inc rcx + jmp map_v_xs +map_v_xf: + mov edx, [xs_to_col + rcx*4] + mov [thincol + r8*4], edx + mov r13, [vy + r8*8] + xor rcx, rcx +map_v_ys: + mov rax, [ys + rcx*8] + cmp rax, r13 + je map_v_yf + inc rcx + jmp map_v_ys +map_v_yf: + mov edx, [ys_to_row + rcx*4] + mov [thinrow + r8*4], edx + inc r8 + jmp map_v +map_v_done: + + ; classify edges into vertical / horizontal + xor r8, r8 + xor r12, r12 ; ve count + xor r13, r13 ; he count +gen_edges: + cmp r8, [n_v] + jge gen_edges_done + mov r9, r8 + inc r9 + cmp r9, [n_v] + jne ge_nowrap + xor r9, r9 +ge_nowrap: + mov r10, [vx + r8*8] + mov r11, [vx + r9*8] + cmp r10, r11 + je ge_vert + mov rax, [vy + r8*8] + mov [hey + r13*8], rax + mov rcx, r10 + mov rdx, r11 + cmp rcx, rdx + jle ge_h_ok + xchg rcx, rdx +ge_h_ok: + mov [hexlo + r13*8], rcx + mov [hexhi + r13*8], rdx + inc r13 + jmp ge_next +ge_vert: + mov [vex + r12*8], r10 + mov rcx, [vy + r8*8] + mov rdx, [vy + r9*8] + cmp rcx, rdx + jle ge_v_ok + xchg rcx, rdx +ge_v_ok: + mov [veylo + r12*8], rcx + mov [veyhi + r12*8], rdx + inc r12 +ge_next: + inc r8 + jmp gen_edges +gen_edges_done: + mov [ve_cnt], r12 + mov [he_cnt], r13 + + ; 2D prefix sum of unfilled cells + xor r15, r15 ; refined row r +pref_r: + cmp r15, [r_cnt] + jge pref_done + mov r13, [row_lo + r15*8] ; py + xor r14, r14 ; refined col c +pref_c: + cmp r14, [c_cnt] + jge pref_c_done + mov rdi, [col_lo + r14*8] + mov rsi, r13 + call filled + mov rbx, 1 + sub rbx, rax ; unfilled indicator + + mov rax, r15 + imul rax, [cp1] ; r*cp1 + mov rcx, rax + add rcx, r14 + add rcx, 1 + mov edx, [pref + rcx*4] ; P[r][c+1] + mov rcx, rax + add rcx, r14 + mov r8d, [pref + rcx*4] ; P[r][c] + mov rcx, rax + add rcx, [cp1] + mov r9, rcx ; (r+1)*cp1 + add rcx, r14 + mov r10d, [pref + rcx*4] ; P[r+1][c] + mov eax, ebx + add eax, edx + add eax, r10d + sub eax, r8d + mov rcx, r9 + add rcx, r14 + add rcx, 1 + mov [pref + rcx*4], eax ; P[r+1][c+1] + inc r14 + jmp pref_c +pref_c_done: + inc r15 + jmp pref_r +pref_done: + + ; all pairs: part 1 = max area, part 2 = max area fully inside + mov qword [best1], 0 + mov qword [best2], 0 + xor r8, r8 +pair_i: + cmp r8, [n_v] + jge pair_done + mov r12d, [thincol + r8*4] + mov r13d, [thinrow + r8*4] + mov r14, [vx + r8*8] + mov r15, [vy + r8*8] + lea r9, [r8 + 1] +pair_j: + cmp r9, [n_v] + jge pair_j_done + + ; area = (|xi-xj| + 1) * (|yi-yj| + 1) + mov rax, r14 + sub rax, [vx + r9*8] + jns .ax + neg rax +.ax: + inc rax + mov rbx, rax + mov rax, r15 + sub rax, [vy + r9*8] + jns .ay + neg rax +.ay: + inc rax + imul rax, rbx + cmp rax, [best1] + jle .no1 + mov [best1], rax +.no1: + push rax ; save area + + ; refined block: c1,c2 then r1,r2 + mov eax, [thincol + r9*4] + mov ecx, r12d + cmp ecx, eax + jle .cc + xchg ecx, eax +.cc: + mov edi, ecx ; c1 + mov esi, eax ; c2 + mov eax, [thinrow + r9*4] + mov ecx, r13d + cmp ecx, eax + jle .rr + xchg ecx, eax +.rr: + mov edx, ecx ; r1 + mov ecx, eax ; r2 + call block_unf + pop rbx ; area + test eax, eax + jnz .no2 ; contains unfilled cells + cmp rbx, [best2] + jle .no2 + mov [best2], rbx +.no2: + inc r9 + jmp pair_j +pair_j_done: + inc r8 + jmp pair_i +pair_done: + +print_results: + mov rcx, label1 + call print_string + mov rax, [best1] + call print_int64 + call print_newline + + mov rcx, label2 + call print_string + mov rax, [best2] + call print_int64 + call print_newline + + mov rax, SYS_EXIT + xor rdi, rdi + syscall + +; filled: is tile (RDI=px, RSI=py) red or green (inside or on the loop)? +; Output: RAX = 1 if filled, else 0. Clobbers RAX, RCX, RDX, R10, R11. +filled: + xor ecx, ecx ; on-edge flag + xor r11, r11 ; crossing count + xor r10, r10 ; edge index +.v_loop: + cmp r10, [ve_cnt] + jge .v_done + mov rax, [vex + r10*8] + cmp rax, rdi + jne .v_cross + mov rdx, [veylo + r10*8] + cmp rsi, rdx + jl .v_cross + mov rdx, [veyhi + r10*8] + cmp rsi, rdx + jg .v_cross + mov ecx, 1 ; on a vertical edge +.v_cross: + mov rax, [vex + r10*8] + cmp rax, rdi + jle .v_next + mov rdx, [veylo + r10*8] + cmp rsi, rdx + jl .v_next + mov rdx, [veyhi + r10*8] + cmp rsi, rdx + jge .v_next + inc r11 +.v_next: + inc r10 + jmp .v_loop +.v_done: + test ecx, ecx + jnz .yes + xor r10, r10 +.h_loop: + cmp r10, [he_cnt] + jge .h_done + mov rax, [hey + r10*8] + cmp rax, rsi + jne .h_next + mov rdx, [hexlo + r10*8] + cmp rdi, rdx + jl .h_next + mov rdx, [hexhi + r10*8] + cmp rdi, rdx + jg .h_next + jmp .yes +.h_next: + inc r10 + jmp .h_loop +.h_done: + mov rax, r11 + and rax, 1 + ret +.yes: + mov rax, 1 + ret + +; block_unf: count of unfilled refined cells in [c1,c2] x [r1,r2]. +; In: RDI=c1, RSI=c2, RDX=r1, RCX=r2. Out: EAX. Clobbers RAX, R10, R11. +block_unf: + mov r10, rcx + inc r10 + imul r10, [cp1] ; (r2+1)*cp1 + mov r11, r10 + add r11, rsi + add r11, 1 + mov eax, [pref + r11*4] ; A + mov r11, r10 + add r11, rdi + sub eax, [pref + r11*4] ; - C + mov r10, rdx + imul r10, [cp1] ; r1*cp1 + mov r11, r10 + add r11, rsi + add r11, 1 + sub eax, [pref + r11*4] ; - B + mov r11, r10 + add r11, rdi + add eax, [pref + r11*4] ; + D + ret + +; sort_q: insertion sort of qword array RDI[0..RSI-1] ascending. +; Clobbers RAX, RDX, R8, R9, R10. +sort_q: + mov r8, 1 +.i: + cmp r8, rsi + jge .done + mov r10, [rdi + r8*8] + mov r9, r8 + dec r9 +.j: + cmp r9, 0 + jl .place + mov rax, [rdi + r9*8] + cmp rax, r10 + jle .place + mov rdx, r9 + inc rdx + mov [rdi + rdx*8], rax + dec r9 + jmp .j +.place: + mov rdx, r9 + inc rdx + mov [rdi + rdx*8], r10 + inc r8 + jmp .i +.done: + ret + +; dedup_q: remove consecutive duplicates in sorted RDI[0..RSI-1]. +; Out: RAX = new length. Clobbers RAX, RCX, RDX, R8. +dedup_q: + xor rax, rax + xor rcx, rcx +.loop: + cmp rcx, rsi + jge .done + test rax, rax + jz .keep + mov rdx, [rdi + rcx*8] + mov r8, rax + dec r8 + cmp rdx, [rdi + r8*8] + je .skip +.keep: + mov rdx, [rdi + rcx*8] + mov [rdi + rax*8], rdx + inc rax +.skip: + inc rcx + jmp .loop +.done: + ret diff --git a/Dockerfile b/Dockerfile index c45aa6c..7433372 100644 --- a/Dockerfile +++ b/Dockerfile @@ -1,4 +1,4 @@ -FROM --platform=linux/amd64 debian:bookworm-slim +FROM debian:bookworm-slim RUN apt-get update \ && apt-get install -y --no-install-recommends \ @@ -10,7 +10,8 @@ RUN apt-get update \ WORKDIR /app COPY Makefile ./ -COPY aoc-2025/ ./aoc-2025/ +COPY 2025/ ./2025/ +COPY utils/ ./utils/ COPY README.md LICENSE ./ COPY scripts/docker-entrypoint.sh /usr/local/bin/docker-entrypoint.sh diff --git a/Makefile b/Makefile index 5da61f2..c98ea0f 100644 --- a/Makefile +++ b/Makefile @@ -4,7 +4,7 @@ LD ?= ld YEAR ?= 2025 DAY ?= -SRC_DIR := aoc-$(YEAR) +SRC_DIR := $(YEAR) BUILD_DIR := build/aoc-$(YEAR) NASMFLAGS ?= -f elf64 @@ -13,7 +13,7 @@ LDFLAGS ?= -m elf_x86_64 DAYS := $(basename $(notdir $(wildcard $(SRC_DIR)/day*.asm))) BINARIES := $(addprefix $(BUILD_DIR)/,$(DAYS)) -UTILS := $(wildcard $(SRC_DIR)/utils/*.asm) +UTILS := $(wildcard utils/*.asm) .PHONY: all clean list run @@ -23,7 +23,7 @@ $(BUILD_DIR): @mkdir -p $@ $(BUILD_DIR)/%.o: $(SRC_DIR)/%.asm $(UTILS) | $(BUILD_DIR) - @$(NASM) $(NASMFLAGS) -I$(SRC_DIR)/ $< -o $@ + @$(NASM) $(NASMFLAGS) -I. $< -o $@ $(BUILD_DIR)/%: $(BUILD_DIR)/%.o @$(LD) $(LDFLAGS) -o $@ $< diff --git a/README.md b/README.md index afa8008..5473379 100644 --- a/README.md +++ b/README.md @@ -6,31 +6,34 @@ I don't particularly care about the AoC leaderboard. December is usually a prett AoC gives each user their own puzzle input. I keep my inputs locally and do not commit them to this repository. If you're running these solutions yourself, you'll need to provide your own inputs in whatever format the corresponding solution expects. ## Docker -The solutions are Linux x64 ELF binaries, so they don't run natively on macOS or Windows. The image bundles `nasm`, `ld`, and `make`. It's pinned to `linux/amd64`; on Apple Silicon it runs under emulation automatically (you'll see a harmless platform-mismatch warning). +The solutions are Linux x64 ELF binaries, so they don't run natively on macOS or Windows. The image bundles `nasm`, `ld`, and `make`. + +Since the solutions target x86-64, the container should be run as `linux/amd64`. On Apple Silicon, Docker will run it under emulation. Build the image from the repository root: ```sh -docker build -t aoc . +docker build --platform=linux/amd64 -t aoc . ``` List the available days: ```sh -docker run --rm aoc list +docker run --platform=linux/amd64 --rm aoc list ``` -### Inputs AoC inputs are per-user and are not committed to this repo. Put your input for a given day at `input/dayN.txt` in the repository root, then mount that directory when running so the solution can read it: ```sh -docker run --rm -v "$PWD/input:/app/input" aoc day5 +docker run --platform=linux/amd64 --rm \ + -v "$PWD/input:/app/input" \ + aoc run DAY=5 ``` Assemble and link every day without running it — a quick build check that needs no input: ```sh -docker run --rm aoc all +docker run --platform=linux/amd64 --rm aoc all ``` When you're done, remove the image with: diff --git a/aoc-2025/day1.asm b/aoc-2025/day1.asm deleted file mode 100644 index 928e7a5..0000000 --- a/aoc-2025/day1.asm +++ /dev/null @@ -1,228 +0,0 @@ -; Advent of Code 2025 - Day 1 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" - -section .data - input_path db "input/day1.txt", 0 - - label1 db "Password 1: ", 0 - label2 db "Password 2: ", 0 - - angle1 dd 50 - angle2 dd 50 - - password1 dd 0 - password2 dd 0 - -section .bss - buffer resb 4096 - line_buffer resb 256 - line_len resd 1 - -section .text - -_start: - ; open file - mov rax, SYS_OPEN - mov rdi, input_path - mov rsi, O_RDONLY - xor rdx, rdx - syscall - - mov r12, rax ; fd in R12 - mov dword [line_len], 0 ; no chars in current line yet - -read_loop: - ; read up to 4096 bytes - mov rax, SYS_READ - mov rdi, r12 - mov rsi, buffer - mov rdx, 4096 - syscall - - cmp rax, 0 - jle eof ; <=0 -> EOF or error - - mov rdi, buffer ; scan pointer - mov rbp, rax ; bytes remaining in this chunk - -scan_chunk: - cmp rbp, 0 - je read_loop ; chunk done, read next - - mov al, [rdi] - - ; windows can be a fucking bitch - ; handle (CR) -> just skip - cmp al, 13 - je skip_cr - - ; handle LF (10) -> end of line - cmp al, 10 - je end_of_line - - ; normal character -> append to line_buffer if space left - mov edx, [line_len] - cmp edx, 255 ; leave 1 byte for NULL - jae skip_store ; ignore extra characters if too long - mov [line_buffer+rdx], al - inc edx - mov [line_len], edx - -skip_store: - inc rdi - dec rbp - jmp scan_chunk - -skip_cr: - inc rdi - dec rbp - jmp scan_chunk - -end_of_line: - ; terminate current line - mov edx, [line_len] - mov byte [line_buffer+rdx], 0 - - ; if line isn't empty, process it - cmp edx, 0 - je line_done - - push rdi - mov rsi, line_buffer - call handle_line - pop rdi - -line_done: - mov dword [line_len], 0 ; reset line length - inc rdi - dec rbp - jmp scan_chunk - -; process last line if not newline-terminated, then print result -eof: - ; if there is a partial line at EOF, process it - mov edx, [line_len] - cmp edx, 0 - jle print_results - mov byte [line_buffer+rdx], 0 - - mov rsi, line_buffer - call handle_line - -print_results: - mov rcx, label1 - call print_string - mov eax, [password1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov eax, [password2] - call print_int64 - call print_newline - - mov rax, SYS_CLOSE - mov rdi, r12 - syscall - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; Handle one line: RSI -> "L123" or "R45" -handle_line: - mov al, [rsi] - cmp al, 'L' - je .left - mov ebx, 1 ; direction = +1 for 'R' or anything else - jmp .after -.left: - mov ebx, -1 ; direction = -1 for 'L' -.after: - inc rsi ; skip 'L' or 'R' - call parse_int ; EAX = steps - mov ecx, eax - -; Part 1 -p1_start: - mov eax, ecx - imul eax, ebx - add eax, [angle1] - call normalize_angle - mov [angle1], eax - cmp eax, 0 - jne p2_start - mov rdi, password1 - mov edx, [rdi] - inc edx - mov [rdi], edx - -; Part 2 -p2_start: - mov rdi, password2 -.loop: - test ecx, ecx - jle p2_exit - dec ecx - - mov eax, [angle2] - call update_angle_count - mov [angle2], eax - - jmp .loop -p2_exit: - ret - -; normalize eax to 0..99 -normalize_angle: - cmp eax, 0 - jl .add - cmp eax, 100 - jl .done - sub eax, 100 - jmp normalize_angle -.add: - add eax, 100 - jmp normalize_angle -.done: - ret - -; eax = angle, ebx = direction, rdi = password counter addr -update_angle_count: - add eax, ebx - call normalize_angle - - cmp eax, 0 - jne .done - mov edx, [rdi] - inc edx - mov [rdi], edx -.done: - ret - -; parse ASCII integer into EAX -parse_int: - xor eax, eax ; result = 0 -.parse_loop: - mov dl, [rsi] - cmp dl, '0' - jl .done - cmp dl, '9' - jg .done - - sub dl, '0' ; digit value 0..9 - movzx edx, dl - - imul eax, eax, 10 ; result *= 10 - add eax, edx ; result += digit - - inc rsi - jmp .parse_loop -.done: - ret 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 diff --git a/aoc-2025/day11.asm b/aoc-2025/day11.asm deleted file mode 100644 index c3cd930..0000000 --- a/aoc-2025/day11.asm +++ /dev/null @@ -1,233 +0,0 @@ -; Advent of Code 2025 - Day 11 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" - -%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 - - 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 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; 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 diff --git a/aoc-2025/day12.asm b/aoc-2025/day12.asm deleted file mode 100644 index 8931a2b..0000000 --- a/aoc-2025/day12.asm +++ /dev/null @@ -1,486 +0,0 @@ -; Advent of Code 2025 - Day 12 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" -%include "utils/parse.asm" - -%define RAW_SIZE 262144 -%define GRID_SIZE 4096 ; regions are at most 50x50 - -section .data - input_path db "input/day12.txt", 0 - - label1 db "Part 1: ", 0 - -section .bss - raw resb RAW_SIZE - - base_r resd (6 * 9) ; parsed shape cells - base_c resd (6 * 9) - base_n resq 6 ; cells per shape (also its area cost) - - odr resd (6 * 8 * 9) ; orientation cell offsets from anchor - odc resd (6 * 8 * 9) - oncells resq (6 * 8) - - tr resd 9 ; scratch for orientation building - tc resd 9 - - grid resb GRID_SIZE - remaining resq 6 - counts resq 6 - - raw_len resq 1 - cursor resq 1 - pend resq 1 - cur_shape resq 1 - shape_row resq 1 - orients_done resq 1 - rW resq 1 - rL resq 1 - area resq 1 - left resq 1 - count_feasible resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; parse shapes and regions - lea rsi, [raw] - mov rax, [raw_len] - lea rax, [raw + rax] - mov [pend], rax - mov qword [cur_shape], 0 - mov qword [orients_done], 0 -pline: - cmp rsi, [pend] - jae pdone - mov al, [rsi] - cmp al, 10 - je pskip - cmp al, 13 - je pskip - cmp al, ' ' - je pskip - cmp al, '0' - jl maybe_grid - cmp al, '9' - jg maybe_grid - ; a number begins the line - call parse_u64 - mov r10, rax - mov al, [rsi] - cmp al, 'x' - je region_line - ; shape header "N:" - inc rsi - mov [cur_shape], r10 - mov qword [base_n + r10*8], 0 - mov qword [shape_row], 0 - jmp eol - -region_line: - cmp qword [orients_done], 0 - jne .have - mov [cursor], rsi - call gen_orients - mov rsi, [cursor] - mov qword [orients_done], 1 -.have: - inc rsi ; skip 'x' - call parse_u64 - mov r11, rax ; L -.find_colon: - mov al, [rsi] - inc rsi - cmp al, ':' - jne .find_colon - xor rcx, rcx -.rcounts: - cmp rcx, 6 - jge .rcounts_done -.rsp: - mov al, [rsi] - cmp al, ' ' - jne .rsp_done - inc rsi - jmp .rsp -.rsp_done: - call parse_u64 - mov [counts + rcx*8], rax - inc rcx - jmp .rcounts -.rcounts_done: - mov [cursor], rsi - mov rdi, r10 ; W - mov rsi, r11 ; L - call solve_region - mov rsi, [cursor] - jmp eol - -maybe_grid: - cmp al, '#' - je grid_row - cmp al, '.' - je grid_row - inc rsi - jmp pline -grid_row: - mov r10, [cur_shape] - mov r11, [shape_row] - xor rcx, rcx ; column -.cell: - mov al, [rsi] - cmp al, '#' - je .hash - cmp al, '.' - je .dot - jmp .row_done -.hash: - mov rax, r10 - imul rax, 9 - add rax, [base_n + r10*8] - mov edx, r11d - mov [base_r + rax*4], edx - mov edx, ecx - mov [base_c + rax*4], edx - inc qword [base_n + r10*8] -.dot: - inc rcx - inc rsi - jmp .cell -.row_done: - inc qword [shape_row] - jmp eol - -eol: - cmp rsi, [pend] - jae pdone - mov al, [rsi] - inc rsi - cmp al, 10 - jne eol - jmp pline -pskip: - inc rsi - jmp pline -pdone: - - mov rcx, label1 - call print_string - mov rax, [count_feasible] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; gen_orients: build the 8 dihedral orientations of every shape as offset lists -; anchored at their row-major-first cell. -gen_orients: - xor r12, r12 ; shape -.s_loop: - cmp r12, 6 - jge .done - xor r13, r13 ; transform 0..7 -.t_loop: - cmp r13, 8 - jge .s_next - mov r14, [base_n + r12*8] - xor rcx, rcx -.k_loop: - cmp rcx, r14 - jge .k_done - mov rax, r12 - imul rax, 9 - add rax, rcx - movsxd r8, dword [base_r + rax*4] - movsxd r9, dword [base_c + rax*4] - test r13, 4 - jz .noflip - neg r9 -.noflip: - mov rdx, r13 - and rdx, 3 -.rot: - test rdx, rdx - jz .rot_done - mov r15, r8 - mov r8, r9 ; new r = c - mov r9, r15 - neg r9 ; new c = -r - dec rdx - jmp .rot -.rot_done: - mov [tr + rcx*4], r8d - mov [tc + rcx*4], r9d - inc rcx - jmp .k_loop -.k_done: - ; min row - movsxd r8, dword [tr] - xor rcx, rcx -.minr: - cmp rcx, r14 - jge .minr_done - movsxd rax, dword [tr + rcx*4] - cmp rax, r8 - jge .minr_next - mov r8, rax -.minr_next: - inc rcx - jmp .minr -.minr_done: - ; min col among cells on the min row - mov r9, 0x7fffffff - xor rcx, rcx -.minc: - cmp rcx, r14 - jge .minc_done - movsxd rax, dword [tr + rcx*4] - cmp rax, r8 - jne .minc_next - movsxd rax, dword [tc + rcx*4] - cmp rax, r9 - jge .minc_next - mov r9, rax -.minc_next: - inc rcx - jmp .minc -.minc_done: - mov r11, r12 - shl r11, 3 - add r11, r13 ; orientation index - mov [oncells + r11*8], r14 - xor rcx, rcx -.store: - cmp rcx, r14 - jge .store_done - movsxd rax, dword [tr + rcx*4] - sub rax, r8 ; dr - movsxd rdx, dword [tc + rcx*4] - sub rdx, r9 ; dc - mov rbx, r11 - imul rbx, 9 - add rbx, rcx - mov [odr + rbx*4], eax - mov [odc + rbx*4], edx - inc rcx - jmp .store -.store_done: - inc r13 - jmp .t_loop -.s_next: - inc r12 - jmp .s_loop -.done: - ret - -; solve_region(RDI=W, RSI=L): if the region can fit all presents in `counts`, -; increment count_feasible. -solve_region: - xor r8, r8 ; total cells - xor rcx, rcx -.tot: - cmp rcx, 6 - jge .tot_done - mov rax, [counts + rcx*8] - imul rax, [base_n + rcx*8] - add r8, rax - inc rcx - jmp .tot -.tot_done: - mov rax, rdi - imul rax, rsi - mov [area], rax - mov [rW], rdi - mov [rL], rsi - cmp r8, rax - jg .ret ; more cells than space -> impossible - mov r9, rax - sub r9, r8 ; empty budget - - xor r10, r10 ; piece count - xor rcx, rcx -.setrem: - cmp rcx, 6 - jge .setrem_done - mov rax, [counts + rcx*8] - mov [remaining + rcx*8], rax - add r10, rax - inc rcx - jmp .setrem -.setrem_done: - mov [left], r10 - - mov rcx, [area] - lea rdi, [grid] - xor al, al - rep stosb - - xor rdi, rdi ; pos = 0 - mov rsi, r9 ; empty budget - call rec - test rax, rax - jz .ret - inc qword [count_feasible] -.ret: - ret - -; rec(RDI=pos, RSI=empty_budget) -> RAX 1 if the remaining pieces fit. -; State: R12=pos R13=eb R14=row R15=col RBX=shape RBP=orientation. -rec: - push rbx - push rbp - push r12 - push r13 - push r14 - push r15 - mov r12, rdi - mov r13, rsi - cmp qword [left], 0 - je .true -.adv: - cmp r12, [area] - jae .false - cmp byte [grid + r12], 0 - je .found - inc r12 - jmp .adv -.found: - mov rax, r12 - xor rdx, rdx - div qword [rW] - mov r14, rax ; row - mov r15, rdx ; col - - xor rbx, rbx ; shape -.s_loop: - cmp rbx, 6 - jge .try_empty - cmp qword [remaining + rbx*8], 0 - je .s_next - xor rbp, rbp ; orientation -.t_loop: - cmp rbp, 8 - jge .s_next - mov rax, rbx - shl rax, 3 - add rax, rbp - mov r10, rax ; orientation index - mov r11, [oncells + r10*8] - ; validate placement - xor rcx, rcx -.chk: - cmp rcx, r11 - jge .place - mov rax, r10 - imul rax, 9 - add rax, rcx - movsxd r8, dword [odr + rax*4] - movsxd r9, dword [odc + rax*4] - add r8, r14 ; rr - add r9, r15 ; cc - cmp r8, [rL] - jge .t_next - cmp r9, 0 - jl .t_next - cmp r9, [rW] - jge .t_next - mov rax, r8 - imul rax, [rW] - add rax, r9 - cmp byte [grid + rax], 0 - jne .t_next - inc rcx - jmp .chk -.place: - xor rcx, rcx -.place_k: - cmp rcx, r11 - jge .place_done - mov rax, r10 - imul rax, 9 - add rax, rcx - movsxd r8, dword [odr + rax*4] - movsxd r9, dword [odc + rax*4] - add r8, r14 - add r9, r15 - imul r8, [rW] - add r8, r9 - mov byte [grid + r8], 1 - inc rcx - jmp .place_k -.place_done: - dec qword [remaining + rbx*8] - dec qword [left] - mov rdi, r12 - mov rsi, r13 - call rec - test rax, rax - jnz .true - inc qword [remaining + rbx*8] - inc qword [left] - mov rax, rbx ; child clobbered r10/r11 - rebuild them - shl rax, 3 - add rax, rbp - mov r10, rax - mov r11, [oncells + r10*8] - xor rcx, rcx -.unplace_k: - cmp rcx, r11 - jge .unplace_done - mov rax, r10 - imul rax, 9 - add rax, rcx - movsxd r8, dword [odr + rax*4] - movsxd r9, dword [odc + rax*4] - add r8, r14 - add r9, r15 - imul r8, [rW] - add r8, r9 - mov byte [grid + r8], 0 - inc rcx - jmp .unplace_k -.unplace_done: -.t_next: - inc rbp - jmp .t_loop -.s_next: - inc rbx - jmp .s_loop -.try_empty: - test r13, r13 - jz .false - mov byte [grid + r12], 1 - mov rdi, r12 - mov rsi, r13 - dec rsi - call rec - test rax, rax - jnz .true - mov byte [grid + r12], 0 -.false: - xor eax, eax - jmp .ret -.true: - mov eax, 1 -.ret: - pop r15 - pop r14 - pop r13 - pop r12 - pop rbp - pop rbx - ret diff --git a/aoc-2025/day2.asm b/aoc-2025/day2.asm deleted file mode 100644 index 987fbf9..0000000 --- a/aoc-2025/day2.asm +++ /dev/null @@ -1,324 +0,0 @@ -; Advent of Code 2025 – Day 2 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" -%include "utils/parse.asm" - -section .data - input_path db "input/day2.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - buffer resb 4096 - line_buffer resb 65536 - line_len resd 1 - - sum1 resq 1 - sum2 resq 1 - -section .text - -_start: - mov rax, SYS_OPEN - mov rdi, input_path - mov rsi, O_RDONLY - xor rdx, rdx - syscall - - mov r12, rax ; file descriptor - mov dword [line_len], 0 - -read_loop: - mov rax, SYS_READ - mov rdi, r12 - mov rsi, buffer - mov rdx, 4096 - syscall - - cmp rax, 0 - jle eof - - mov rdi, buffer - mov rbp, rax - -scan_chunk: - cmp rbp, 0 - je read_loop - - mov al, [rdi] - - cmp al, 13 - je skip_cr - - cmp al, 10 - je end_line - - mov edx, [line_len] - cmp edx, 65535 - jae skip_store - mov [line_buffer+rdx], al - inc edx - mov [line_len], edx - -skip_store: - inc rdi - dec rbp - jmp scan_chunk - -skip_cr: - inc rdi - dec rbp - jmp scan_chunk - -end_line: - mov edx, [line_len] - mov byte [line_buffer+rdx], 0 - - cmp edx, 0 - je clear_line - - push rdi - mov rsi, line_buffer - call handle_line - pop rdi - -clear_line: - mov dword [line_len], 0 - inc rdi - dec rbp - jmp scan_chunk - -eof: - ; process final partial line if needed - mov edx, [line_len] - cmp edx, 0 - jle print_results - - mov byte [line_buffer+rdx], 0 - mov rsi, line_buffer - call handle_line - -print_results: - mov rcx, label1 - call print_string - mov rax, [sum1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [sum2] - call print_int64 - call print_newline - - mov rax, SYS_CLOSE - mov rdi, r12 - syscall - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; parse "A-B,C-D,..."l, RSI = pointer to line -; uses r13 = current ID, r14 = end of range -handle_line: -next_range: - ; parse start - call parse_u64 - mov r13, rax - - cmp byte [rsi], '-' - jne done_line - inc rsi - - ; parse end - call parse_u64 - mov r14, rax - -range_loop: - cmp r13, r14 - jg after_range - - ; Save RSI (line pointer) across the checks, - ; because number_to_string / check_invalid* use RSI - push rsi - - ; Part 1: exact AA - mov rax, r13 - call check_invalid1 - test rax, rax - jz .skip_p1 - add qword [sum1], r13 -.skip_p1: - ; Part 2: any repeating block >= 2 - mov rax, r13 - call check_invalid2 - test rax, rax - jz .skip_p2 - add qword [sum2], r13 -.skip_p2: - pop rsi ; restore line pointer - - inc r13 - jmp range_loop - -after_range: - cmp byte [rsi], ',' - jne done_line - inc rsi - jmp next_range - -done_line: - ret - -; number_to_string: convert RAX to decimal ASCII, MSB-first -; Output: -; RSI = pointer to first digit -; ECX = length -number_to_string: - mov rdi, number_buffer+31 - mov byte [rdi], 0 ; terminator (for convenience) - dec rdi - - cmp rax, 0 - jne .conv - - ; handle zero - mov byte [rdi], '0' - mov rsi, rdi - mov ecx, 1 - ret - -.conv: - mov rbx, 10 -.next_digit: - xor rdx, rdx - div rbx ; RAX = quotient, RDX = remainder - add dl, '0' - mov [rdi], dl - dec rdi - test rax, rax - jnz .next_digit - - inc rdi ; now RDI points to first digit - mov rsi, rdi - mov rdx, number_buffer+31 - sub rdx, rsi ; RDX = length - mov ecx, edx - ret - -; check_invalid1: "AA" pattern -; RAX = number -; Returns RAX = 1 if digits == A A, else 0 -check_invalid1: - push rbx - push rdx - - call number_to_string ; RSI=string, ECX=len - mov eax, ecx ; EAX = len - - cmp eax, 2 - jl .no1 - - test eax, 1 - jnz .no1 ; odd length => cannot be AA - - shr eax, 1 ; half = len/2 - mov r8d, eax ; half - xor r9d, r9d ; i = 0 - -.loop1: - cmp r9d, r8d - jge .yes1 - - ; s[i] - mov rdx, r9 - movzx eax, byte [rsi + rdx] - - ; s[i+half] - mov rdx, r9 - add rdx, r8 - movzx ebx, byte [rsi + rdx] - - cmp eax, ebx - jne .no1 - - inc r9d - jmp .loop1 - -.yes1: - mov rax, 1 - jmp .ret1 - -.no1: - xor rax, rax - -.ret1: - pop rdx - pop rbx - ret - -; check_invalid2: any repeating block >= 2 -; RAX = number -; Returns RAX = 1 if string is some A repeated k>=2 times -check_invalid2: - push rbx - push rdx - - call number_to_string ; RSI=string, ECX=len - mov r11d, ecx ; n = length - - cmp r11d, 2 - jb .no2 - - mov r8d, 1 ; m = 1 (candidate period) -.outer: - cmp r8d, r11d - jge .no2 - - ; if n % m != 0 => cannot tile - mov eax, r11d - xor edx, edx - div r8d ; EAX=q, EDX=r - test edx, edx - jnz .next_m - - mov r9d, r11d - sub r9d, r8d ; limit = n - m - xor r10d, r10d ; i = 0 -.inner: - cmp r10d, r9d - jge .yes2 ; all positions checked - - ; s[i] - mov rdx, r10 - movzx eax, byte [rsi + rdx] - - ; s[i+m] - mov rdx, r10 - add rdx, r8 - movzx ebx, byte [rsi + rdx] - - cmp eax, ebx - jne .next_m - - inc r10d - jmp .inner -.yes2: - mov rax, 1 - jmp .ret2 -.next_m: - inc r8d - jmp .outer -.no2: - xor rax, rax -.ret2: - pop rdx - pop rbx - ret diff --git a/aoc-2025/day3.asm b/aoc-2025/day3.asm deleted file mode 100644 index 8330755..0000000 --- a/aoc-2025/day3.asm +++ /dev/null @@ -1,234 +0,0 @@ -; Advent of Code 2025 - Day 3 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" - -section .data - input_path db "input/day3.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - buffer resb 4096 - line_buffer resb 65536 - line_len resd 1 - - sum1 resq 1 - sum2 resq 1 - - work_digits resb 64 ; stack for greedy subsequence - -section .text - -_start: - mov rax, SYS_OPEN - mov rdi, input_path - mov rsi, O_RDONLY - xor rdx, rdx - syscall - - mov r12, rax ; fd - mov dword [line_len], 0 - -read_loop: - mov rax, SYS_READ - mov rdi, r12 - mov rsi, buffer - mov rdx, 4096 - syscall - - cmp rax, 0 - jle eof - - mov rdi, buffer - mov rbp, rax - -scan_chunk: - cmp rbp, 0 - je read_loop - - mov al, [rdi] - - cmp al, 13 - je skip_cr - - cmp al, 10 - je end_line - - mov edx, [line_len] - cmp edx, 65535 - jae skip_store - mov [line_buffer+rdx], al - inc edx - mov [line_len], edx - -skip_store: - inc rdi - dec rbp - jmp scan_chunk - -skip_cr: - inc rdi - dec rbp - jmp scan_chunk - -end_line: - mov edx, [line_len] - mov byte [line_buffer+edx], 0 - - cmp edx, 0 - je clear_line - - push rdi - mov rsi, line_buffer - call handle_line - pop rdi - -clear_line: - mov dword [line_len], 0 - inc rdi - dec rbp - jmp scan_chunk - -eof: - ; possible last partial line - mov edx, [line_len] - cmp edx, 0 - jle print_results - - mov byte [line_buffer+edx], 0 - mov rsi, line_buffer - call handle_line - -print_results: - mov rcx, label1 - call print_string - mov rax, [sum1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [sum2] - call print_int64 - call print_newline - - mov rax, SYS_CLOSE - mov rdi, r12 - syscall - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -handle_line: - mov rdi, rsi - xor ecx, ecx ; ECX = 0 -.length_loop: - mov al, [rdi+rcx] - cmp al, 0 - je .length_done - inc ecx - jmp .length_loop -.length_done: - mov r15d, ecx ; r15d = n - - ; part 1: k = 2 - mov ecx, r15d ; ECX = n - mov edi, 2 ; K = 2 - call get_max_for_k ; RAX = best 2-digit value - add qword [sum1], rax - - ; part 2: k = 12, only if n >= 12 - cmp r15d, 12 - jl .skip_part2 - - mov ecx, r15d - mov edi, 12 - call get_max_for_k ; RAX = best 12-digit value - add qword [sum2], rax - -.skip_part2: - ret - -; Greedy lexicographically largest subsequence of length K -; -; Input: -; RSI -> digits string -; ECX = n (length) -; EDI = k -; Output: -; RAX = numeric value of chosen k digits -; Clobbers: R8..R11, EAX, EDX -get_max_for_k: - ; drops_remaining = n - k - mov eax, ecx - sub eax, edi - mov r8d, eax ; r8d = drops - - xor r9d, r9d ; r9d = stack_size - xor r10d, r10d ; r10d = i - -.loop: - cmp r10d, ecx - jge .after_input - - ; current digit in AL - mov r11, r10 - mov al, [rsi + r11] - -.pop: - cmp r9d, 0 - jle .push - cmp r8d, 0 - jle .push - - mov edx, r9d - dec edx - mov r11d, edx - mov bl, [work_digits + r11] - - cmp bl, al - jge .push - - dec r9d - dec r8d - jmp .pop -.push: - mov r11d, r9d - mov [work_digits + r11], al - inc r9d - inc r10d - jmp .loop - -.after_input: - ; trim if stack_size > k -.trim: - cmp r9d, edi - jle .convert - dec r9d - jmp .trim -.convert: - xor rax, rax - xor r11d, r11d -.convert_loop: - cmp r11d, edi - jge .done - - mov rdx, r11 - mov dl, [work_digits + rdx] - sub dl, '0' - movzx rdx, dl - - imul rax, rax, 10 - add rax, rdx - - inc r11d - jmp .convert_loop -.done: - ret diff --git a/aoc-2025/day4.asm b/aoc-2025/day4.asm deleted file mode 100644 index 60e53ec..0000000 --- a/aoc-2025/day4.asm +++ /dev/null @@ -1,236 +0,0 @@ -; Advent of Code 2025 - Day 4 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" - -%define RAW_SIZE 4194304 ; 4 MiB scratch for the raw file -%define GRID_SIZE 4194304 ; 4 MiB for the padded grid / mark buffers - -section .data - input_path db "input/day4.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - raw resb RAW_SIZE ; raw file bytes - grid resb GRID_SIZE ; padded grid: 1 = roll, 0 = empty - mark resb GRID_SIZE ; per-round removal marks - - raw_len resq 1 - width resq 1 ; real columns per row - height resq 1 ; real rows - stride resq 1 ; width + 2 (padding on both sides) - - part1 resq 1 - part2 resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - xor rcx, rcx ; column scanner -width_scan: - cmp rcx, [raw_len] - jge width_done - mov al, [raw + rcx] - cmp al, 13 ; CR - je width_done - cmp al, 10 ; LF - je width_done - inc rcx - jmp width_scan -width_done: - mov [width], rcx - add rcx, 2 ; padding on left + right - mov [stride], rcx - - ; real cell (r, c) lives at grid[(r+1)*stride + (c+1)] - mov r10, [raw_len] - xor r8, r8 ; i (raw index) - xor r9, r9 ; r (row, 0-based) - xor r11, r11 ; c (col, 0-based) -fill_loop: - cmp r8, r10 - jge fill_end - mov al, [raw + r8] - inc r8 - - cmp al, 13 ; CR -> ignore - je fill_loop - cmp al, 10 ; LF -> end of line - je fill_newline - - cmp al, '@' - jne fill_next_col ; '.' leaves the zeroed cell alone - - ; grid[(r9+1)*stride + (r11+1)] = 1 - mov rbx, r9 - inc rbx - imul rbx, [stride] - add rbx, r11 - add rbx, 1 - mov byte [grid + rbx], 1 -fill_next_col: - inc r11 - jmp fill_loop -fill_newline: - cmp r11, 0 ; blank line -> skip (e.g. trailing newline) - je fill_loop - inc r9 - xor r11, r11 - jmp fill_loop -fill_end: - cmp r11, 0 ; last line had no trailing newline - je fill_height - inc r9 -fill_height: - mov [height], r9 - - mov r13, 1 ; row = 1..height -p1_row: - cmp r13, [height] - jg p1_done - mov rbx, r13 - imul rbx, [stride] - inc rbx ; idx of (row, col=1) - mov r12, 1 ; col = 1..width -p1_col: - cmp r12, [width] - jg p1_row_next - movzx eax, byte [grid + rbx] - test eax, eax - jz p1_next ; not a roll - mov rdi, rbx - call count_neighbors - cmp rax, 4 - jge p1_next ; 4 or more neighbors -> blocked - inc qword [part1] -p1_next: - inc rbx - inc r12 - jmp p1_col -p1_row_next: - inc r13 - jmp p1_row -p1_done: - -peel_loop: - mov r13, 1 -mark_row: - cmp r13, [height] - jg mark_done - mov rbx, r13 - imul rbx, [stride] - inc rbx - mov r12, 1 -mark_col: - cmp r12, [width] - jg mark_row_next - movzx eax, byte [grid + rbx] - test eax, eax - jz mark_zero ; empty cell - mov rdi, rbx - call count_neighbors - cmp rax, 4 - jl mark_one ; accessible -mark_zero: - mov byte [mark + rbx], 0 - jmp mark_next -mark_one: - mov byte [mark + rbx], 1 -mark_next: - inc rbx - inc r12 - jmp mark_col -mark_row_next: - inc r13 - jmp mark_row -mark_done: - - xor r11, r11 ; removed this round - mov r13, 1 -apply_row: - cmp r13, [height] - jg apply_done - mov rbx, r13 - imul rbx, [stride] - inc rbx - mov r12, 1 -apply_col: - cmp r12, [width] - jg apply_row_next - movzx eax, byte [mark + rbx] - test eax, eax - jz apply_next - mov byte [grid + rbx], 0 - inc r11 -apply_next: - inc rbx - inc r12 - jmp apply_col -apply_row_next: - inc r13 - jmp apply_row -apply_done: - add [part2], r11 - test r11, r11 - jnz peel_loop ; something changed -> another round - -print_results: - mov rcx, label1 - call print_string - mov rax, [part1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [part2] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; count_neighbors: sum of the 8 cells around a padded index -; Input: RDI = grid index -; Output: RAX = number of neighboring rolls (0..8) -; Clobbers: RAX, RCX, RDX, R8 -count_neighbors: - mov rcx, [stride] - xor eax, eax - - mov rdx, rdi - sub rdx, rcx ; row above - movzx r8d, byte [grid + rdx - 1] - add eax, r8d - movzx r8d, byte [grid + rdx] - add eax, r8d - movzx r8d, byte [grid + rdx + 1] - add eax, r8d - - movzx r8d, byte [grid + rdi - 1] ; same row, sides - add eax, r8d - movzx r8d, byte [grid + rdi + 1] - add eax, r8d - - mov rdx, rdi - add rdx, rcx ; row below - movzx r8d, byte [grid + rdx - 1] - add eax, r8d - movzx r8d, byte [grid + rdx] - add eax, r8d - movzx r8d, byte [grid + rdx + 1] - add eax, r8d - ret diff --git a/aoc-2025/day5.asm b/aoc-2025/day5.asm deleted file mode 100644 index 4718343..0000000 --- a/aoc-2025/day5.asm +++ /dev/null @@ -1,225 +0,0 @@ -; Advent of Code 2025 - Day 5 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" -%include "utils/parse.asm" - -%define RAW_SIZE 1048576 ; 1 MiB scratch for the raw file -%define MAX_RANGES 8192 ; plenty for the ~177 input ranges - -section .data - input_path db "input/day5.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - raw resb RAW_SIZE - starts resq MAX_RANGES ; range/merged-interval starts - ends resq MAX_RANGES ; range/merged-interval ends - - raw_len resq 1 - n_ranges resq 1 ; ranges parsed in section 1 - n_merged resq 1 ; disjoint intervals after merge - phase resq 1 ; 0 = ranges, 1 = available IDs - - part1 resq 1 - part2 resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; RSI = cursor, R14 = end pointer (both preserved across helper calls) - lea rsi, [raw] - mov rax, [raw_len] - lea r14, [raw + rax] - mov qword [phase], 0 - -scan_line: - cmp rsi, r14 - jae scan_done - mov al, [rsi] - cmp al, 10 ; LF -> blank line - je got_blank - cmp al, 13 ; CR -> blank line - je got_blank - - cmp qword [phase], 0 - jne do_avail - - call parse_u64 ; RAX = start - mov rcx, [n_ranges] - mov [starts + rcx*8], rax - inc rsi ; skip '-' - call parse_u64 ; RAX = end - mov rcx, [n_ranges] - mov [ends + rcx*8], rax - inc qword [n_ranges] - jmp skip_eol - -do_avail: - call parse_u64 - mov rdi, rax - call is_fresh ; RAX = 1 if fresh - test rax, rax - jz skip_eol - inc qword [part1] - jmp skip_eol - -got_blank: - ; the blank line separates the two sections - cmp qword [phase], 0 - jne skip_eol - call finalize_ranges ; sort + merge, compute part2 - mov qword [phase], 1 - ; fall through - -skip_eol: - cmp rsi, r14 - jae scan_done - mov al, [rsi] - inc rsi - cmp al, 10 ; consume through the LF - jne skip_eol - jmp scan_line - -scan_done: - ; safety: if there was no blank line, still finalize the ranges - cmp qword [phase], 0 - jne print_results - call finalize_ranges - -print_results: - mov rcx, label1 - call print_string - mov rax, [part1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [part2] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; is_fresh: test membership of an ID in the merged intervals. -; Input: RDI = id -; Output: RAX = 1 if the id lies in any interval, else 0 -; Intervals are sorted ascending and disjoint, so we can stop early. -; Clobbers: RAX, RCX -is_fresh: - xor rcx, rcx -.loop: - cmp rcx, [n_merged] - jge .no - mov rax, [starts + rcx*8] - cmp rdi, rax - jl .no ; id below this start -> below all later ones - mov rax, [ends + rcx*8] - cmp rdi, rax - jle .yes ; start <= id <= end - inc rcx - jmp .loop -.no: - xor eax, eax - ret -.yes: - mov eax, 1 - ret - -; finalize_ranges: insertion-sort the ranges by start, merge overlapping / -; touching ones in place, store the disjoint intervals back into starts/ends, -; set n_merged, and accumulate their total size into part2. -; Clobbers: RAX, RCX, RDX, R8, R9, R10, R11, R12, R13 -finalize_ranges: - mov r8, 1 ; i -.sort_i: - cmp r8, [n_ranges] - jge .sorted - mov r10, [starts + r8*8] ; key_s - mov r11, [ends + r8*8] ; key_e - mov r9, r8 - dec r9 ; j = i - 1 -.sort_j: - cmp r9, 0 - jl .sort_place - mov rax, [starts + r9*8] - cmp rax, r10 - jle .sort_place ; starts[j] <= key -> in place - mov rdx, r9 - inc rdx ; j + 1 - mov [starts + rdx*8], rax ; shift start - mov rcx, [ends + r9*8] - mov [ends + rdx*8], rcx ; shift end - dec r9 - jmp .sort_j -.sort_place: - mov rdx, r9 - inc rdx - mov [starts + rdx*8], r10 - mov [ends + rdx*8], r11 - inc r8 - jmp .sort_i -.sorted: - - cmp qword [n_ranges], 0 - je .empty - - mov r10, [starts] ; cur_lo - mov r11, [ends] ; cur_hi - mov r8, 1 ; i - xor r12, r12 ; part2 accumulator - xor r13, r13 ; write index -.merge_loop: - cmp r8, [n_ranges] - jge .flush - mov rax, [starts + r8*8] ; s - mov rcx, [ends + r8*8] ; e - cmp rax, r11 - jg .gap ; s > cur_hi -> disjoint - cmp rcx, r11 ; overlap: cur_hi = max(cur_hi, e) - jle .no_extend - mov r11, rcx -.no_extend: - inc r8 - jmp .merge_loop -.gap: - call .emit - mov r10, rax ; begin new interval - mov r11, rcx - inc r8 - jmp .merge_loop -.flush: - call .emit - mov [n_merged], r13 - mov [part2], r12 - ret -.empty: - mov qword [n_merged], 0 - mov qword [part2], 0 - ret - -; local helper: emit [r10, r11] as merged interval r13, add its size to r12 -.emit: - mov [starts + r13*8], r10 - mov [ends + r13*8], r11 - inc r13 - mov rdx, r11 - sub rdx, r10 - inc rdx ; end - start + 1 - add r12, rdx - ret diff --git a/aoc-2025/day6.asm b/aoc-2025/day6.asm deleted file mode 100644 index 728b8b0..0000000 --- a/aoc-2025/day6.asm +++ /dev/null @@ -1,331 +0,0 @@ -; Advent of Code 2025 - Day 6 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" - -%define RAW_SIZE 1048576 -%define MAX_W 8192 -%define MAX_H 64 -%define GRID_SIZE (MAX_W * MAX_H) - -section .data - input_path db "input/day6.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - raw resb RAW_SIZE - grid resb GRID_SIZE ; height x width, space-filled - - raw_len resq 1 - width resq 1 - height resq 1 - - blk_c0 resq 1 ; current block: columns [blk_c0, blk_c1) - blk_c1 resq 1 - op resq 1 ; 0 = add, 1 = mul, -1 = none - - part1 resq 1 - part2 resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; width = length of the first line - xor rcx, rcx -width_scan: - cmp rcx, [raw_len] - jge width_done - mov al, [raw + rcx] - cmp al, 10 - je width_done - cmp al, 13 - je width_done - inc rcx - jmp width_scan -width_done: - mov [width], rcx - - ; height = number of lines (newlines, plus one if the last line has no newline) - xor rcx, rcx - xor r8, r8 -height_scan: - cmp rcx, [raw_len] - jge height_tail - mov al, [raw + rcx] - cmp al, 10 - jne height_next - inc r8 -height_next: - inc rcx - jmp height_scan -height_tail: - mov rax, [raw_len] - test rax, rax - jz height_store - mov dl, [raw + rax - 1] - cmp dl, 10 - je height_store - inc r8 -height_store: - mov [height], r8 - - ; space-fill the grid, then copy the raw bytes into it - mov rax, [height] - imul rax, [width] - mov rcx, rax - lea rdi, [grid] - mov al, ' ' - rep stosb - - xor r8, r8 ; raw index - xor r9, r9 ; row - xor r10, r10 ; col -fill_loop: - cmp r8, [raw_len] - jge fill_done - mov al, [raw + r8] - inc r8 - cmp al, 10 - je fill_newline - cmp al, 13 - je fill_loop - cmp r10, [width] - jge fill_loop - mov rdx, r9 - imul rdx, [width] - add rdx, r10 - mov [grid + rdx], al - inc r10 - jmp fill_loop -fill_newline: - inc r9 - xor r10, r10 - jmp fill_loop -fill_done: - - ; walk the columns, carving out blocks between all-space separators - xor r15, r15 ; column cursor -block_scan: - cmp r15, [width] - jge blocks_done - mov rdi, r15 - call col_is_sep - test rax, rax - jnz block_sep - mov [blk_c0], r15 -block_extend: - cmp r15, [width] - jge block_end - mov rdi, r15 - call col_is_sep - test rax, rax - jnz block_end - inc r15 - jmp block_extend -block_end: - mov [blk_c1], r15 - call process_block - jmp block_scan -block_sep: - inc r15 - jmp block_scan -blocks_done: - -print_results: - mov rcx, label1 - call print_string - mov rax, [part1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [part2] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; col_is_sep: is every row of column RDI a space? -; Output: RAX = 1 if the column is a separator, else 0 -; Clobbers: RAX, RDX, R8 -col_is_sep: - xor r8, r8 -.loop: - cmp r8, [height] - jge .sep - mov rax, r8 - imul rax, [width] - add rax, rdi - movzx edx, byte [grid + rax] - cmp dl, ' ' - jne .not - inc r8 - jmp .loop -.sep: - mov rax, 1 - ret -.not: - xor rax, rax - ret - -; process_block: fold the block [blk_c0, blk_c1) for both parts. -; Part 1 reads each row as a number; part 2 reads each column as a number. -; The bottom row supplies the operator. Clobbers RAX, RCX, RDX, R8-R14. -process_block: - ; find the operator on the bottom row within the block - mov rax, [height] - dec rax - imul rax, [width] - mov r11, rax ; offset of the operator row - mov qword [op], -1 - mov rcx, [blk_c0] -.find_op: - cmp rcx, [blk_c1] - jge .op_done - mov rdx, r11 - add rdx, rcx - mov al, [grid + rdx] - cmp al, '+' - je .set_add - cmp al, '*' - je .set_mul - inc rcx - jmp .find_op -.set_add: - mov qword [op], 0 - jmp .op_done -.set_mul: - mov qword [op], 1 -.op_done: - cmp qword [op], 0 - jl .ret ; no operator -> not a real problem - - ; part 1: one number per row - mov r12, [op] - xor r13, r13 ; accumulator - test r12, r12 - jz .p1_acc - mov r13, 1 -.p1_acc: - xor r14, r14 ; count of numbers folded - xor r10, r10 ; row -.p1_rows: - mov rax, [height] - dec rax - cmp r10, rax - jge .p1_done - mov rax, r10 - imul rax, [width] - mov r11, rax ; row offset - xor r8, r8 ; number - xor r9, r9 ; saw a digit? - mov rcx, [blk_c0] -.p1_cols: - cmp rcx, [blk_c1] - jge .p1_fold - mov rdx, r11 - add rdx, rcx - movzx eax, byte [grid + rdx] - cmp al, '0' - jl .p1_col_next - cmp al, '9' - jg .p1_col_next - sub al, '0' - movzx rax, al - imul r8, r8, 10 - add r8, rax - mov r9, 1 -.p1_col_next: - inc rcx - jmp .p1_cols -.p1_fold: - test r9, r9 - jz .p1_row_next - test r12, r12 - jnz .p1_mul - add r13, r8 - jmp .p1_counted -.p1_mul: - imul r13, r8 -.p1_counted: - inc r14 -.p1_row_next: - inc r10 - jmp .p1_rows -.p1_done: - test r14, r14 - jz .p2 - add [part1], r13 - - ; part 2: one number per column -.p2: - mov r12, [op] - xor r13, r13 - test r12, r12 - jz .p2_acc - mov r13, 1 -.p2_acc: - xor r14, r14 - mov rcx, [blk_c0] ; column -.p2_cols: - cmp rcx, [blk_c1] - jge .p2_done - xor r8, r8 ; number - xor r9, r9 ; saw a digit? - xor r10, r10 ; row -.p2_rows: - mov rax, [height] - dec rax - cmp r10, rax - jge .p2_fold - mov rax, r10 - imul rax, [width] - add rax, rcx - movzx edx, byte [grid + rax] - cmp dl, '0' - jl .p2_row_next - cmp dl, '9' - jg .p2_row_next - sub dl, '0' - movzx rdx, dl - imul r8, r8, 10 - add r8, rdx - mov r9, 1 -.p2_row_next: - inc r10 - jmp .p2_rows -.p2_fold: - test r9, r9 - jz .p2_col_next - test r12, r12 - jnz .p2_mul - add r13, r8 - jmp .p2_counted -.p2_mul: - imul r13, r8 -.p2_counted: - inc r14 -.p2_col_next: - inc rcx - jmp .p2_cols -.p2_done: - test r14, r14 - jz .ret - add [part2], r13 -.ret: - ret diff --git a/aoc-2025/day7.asm b/aoc-2025/day7.asm deleted file mode 100644 index 1d990a7..0000000 --- a/aoc-2025/day7.asm +++ /dev/null @@ -1,302 +0,0 @@ -; Advent of Code 2025 - Day 7 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" - -%define RAW_SIZE 1048576 -%define MAX_W 1024 -%define MAX_H 1024 -%define GRID_SIZE (MAX_W * MAX_H) - -section .data - input_path db "input/day7.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - raw resb RAW_SIZE - grid resb GRID_SIZE ; height x width, '.'-filled - g resq (MAX_W * MAX_H) ; part 2 timeline counts - cur resb MAX_W ; part 1 active columns (this row) - nxt resb MAX_W ; part 1 active columns (next row) - - raw_len resq 1 - width resq 1 - height resq 1 - srow resq 1 - scol resq 1 - - part1 resq 1 - part2 resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; width = length of the first line - xor rcx, rcx -width_scan: - cmp rcx, [raw_len] - jge width_done - mov al, [raw + rcx] - cmp al, 10 - je width_done - cmp al, 13 - je width_done - inc rcx - jmp width_scan -width_done: - mov [width], rcx - - ; height = number of lines - xor rcx, rcx - xor r8, r8 -height_scan: - cmp rcx, [raw_len] - jge height_tail - mov al, [raw + rcx] - cmp al, 10 - jne height_next - inc r8 -height_next: - inc rcx - jmp height_scan -height_tail: - mov rax, [raw_len] - test rax, rax - jz height_store - mov dl, [raw + rax - 1] - cmp dl, 10 - je height_store - inc r8 -height_store: - mov [height], r8 - - ; '.'-fill the grid, then copy the raw bytes into it - mov rax, [height] - imul rax, [width] - mov rcx, rax - lea rdi, [grid] - mov al, '.' - rep stosb - - xor r8, r8 ; raw index - xor r9, r9 ; row - xor r10, r10 ; col -fill_loop: - cmp r8, [raw_len] - jge fill_done - mov al, [raw + r8] - inc r8 - cmp al, 10 - je fill_newline - cmp al, 13 - je fill_loop - cmp r10, [width] - jge fill_loop - mov rdx, r9 - imul rdx, [width] - add rdx, r10 - mov [grid + rdx], al - inc r10 - jmp fill_loop -fill_newline: - inc r9 - xor r10, r10 - jmp fill_loop -fill_done: - - ; locate S - xor r8, r8 - mov rax, [height] - imul rax, [width] - mov r9, rax -find_s: - cmp r8, r9 - jge s_done - mov al, [grid + r8] - cmp al, 'S' - je s_found - inc r8 - jmp find_s -s_found: - mov rax, r8 - xor rdx, rdx - div qword [width] - mov [srow], rax - mov [scol], rdx -s_done: - - ; part 1: flood a set of active columns, counting splitter hits - lea rdi, [cur] - mov rcx, MAX_W - xor al, al - rep stosb - mov rax, [scol] - mov byte [cur + rax], 1 - - xor r15, r15 ; row -p1_row: - cmp r15, [height] - jge p1_done - lea rdi, [nxt] - mov rcx, MAX_W - xor al, al - rep stosb - - mov rax, r15 - imul rax, [width] - mov r14, rax ; row offset - xor r13, r13 ; col - xor r12, r12 ; any beam alive? -p1_col: - cmp r13, [width] - jge p1_col_done - mov al, [cur + r13] - test al, al - jz p1_next - mov rdx, r14 - add rdx, r13 - mov al, [grid + rdx] - cmp al, '^' - jne p1_pass - inc qword [part1] - mov rbx, r13 ; left neighbor - test rbx, rbx - jz p1_no_left - dec rbx - mov byte [nxt + rbx], 1 - mov r12, 1 -p1_no_left: - mov rbx, r13 ; right neighbor - inc rbx - cmp rbx, [width] - jge p1_no_right - mov byte [nxt + rbx], 1 - mov r12, 1 -p1_no_right: - jmp p1_next -p1_pass: - mov byte [nxt + r13], 1 - mov r12, 1 -p1_next: - inc r13 - jmp p1_col -p1_col_done: - lea rsi, [nxt] - lea rdi, [cur] - mov rcx, MAX_W - rep movsb - test r12, r12 - jz p1_done - inc r15 - jmp p1_row -p1_done: - - ; part 2: bottom-up DP of timeline counts, g[r][c] - mov r15, [height] - dec r15 ; row, counting down -p2_row: - cmp r15, 0 - jl p2_done - mov rax, r15 - imul rax, [width] - mov r14, rax ; row offset - xor r13, r13 ; col -p2_col: - cmp r13, [width] - jge p2_col_done - mov rdx, r14 - add rdx, r13 ; idx = r*W + c - mov al, [grid + rdx] - cmp al, '^' - je p2_split - - ; pass straight down: g = (r+1 in grid ? g[r+1][c] : 1) - mov rbx, r15 - inc rbx - cmp rbx, [height] - jge p2_pass_exit - mov rcx, rdx - add rcx, [width] - mov rax, [g + rcx*8] - jmp p2_store -p2_pass_exit: - mov rax, 1 - jmp p2_store - -p2_split: - ; left child enters (r+1, c-1) - mov rbx, r15 - inc rbx - cmp rbx, [height] - jge p2_left_one - cmp r13, 0 - jle p2_left_one - mov rcx, rdx - add rcx, [width] - dec rcx - mov r8, [g + rcx*8] - jmp p2_left_done -p2_left_one: - mov r8, 1 -p2_left_done: - ; right child enters (r+1, c+1) - mov rbx, r15 - inc rbx - cmp rbx, [height] - jge p2_right_one - mov rbx, r13 - inc rbx - cmp rbx, [width] - jge p2_right_one - mov rcx, rdx - add rcx, [width] - inc rcx - mov r9, [g + rcx*8] - jmp p2_right_done -p2_right_one: - mov r9, 1 -p2_right_done: - mov rax, r8 - add rax, r9 -p2_store: - mov [g + rdx*8], rax - inc r13 - jmp p2_col -p2_col_done: - dec r15 - jmp p2_row -p2_done: - mov rax, [srow] - imul rax, [width] - add rax, [scol] - mov rax, [g + rax*8] - mov [part2], rax - -print_results: - mov rcx, label1 - call print_string - mov rax, [part1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [part2] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall diff --git a/aoc-2025/day8.asm b/aoc-2025/day8.asm deleted file mode 100644 index 6a4ecec..0000000 --- a/aoc-2025/day8.asm +++ /dev/null @@ -1,326 +0,0 @@ -; Advent of Code 2025 - Day 8 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" -%include "utils/parse.asm" - -%define RAW_SIZE 262144 -%define MAXN 1024 -%define MAXE (MAXN * (MAXN - 1) / 2) -%define K_LIMIT 1000 ; part 1 connects the K_LIMIT closest pairs - -section .data - input_path db "input/day8.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - raw resb RAW_SIZE - x resq MAXN - y resq MAXN - z resq MAXN - - edges resb (MAXE * 16) ; records: [dist2:8][i:4][j:4] - edges2 resb (MAXE * 16) ; radix ping-pong buffer - counts resq 256 - - parent resq MAXN - csize resq MAXN - - raw_len resq 1 - n_boxes resq 1 - m_edges resq 1 - sorted_ptr resq 1 - comp_count resq 1 - - part1 resq 1 - part2 resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; parse "X,Y,Z" lines into x/y/z, counting boxes - lea rsi, [raw] - mov rax, [raw_len] - lea r14, [raw + rax] ; end pointer - xor r12, r12 ; box index -parse_line: - cmp rsi, r14 - jae parse_done - mov al, [rsi] - cmp al, 10 - je parse_skipnl - cmp al, 13 - je parse_skipnl - call parse_u64 - mov [x + r12*8], rax - inc rsi - call parse_u64 - mov [y + r12*8], rax - inc rsi - call parse_u64 - mov [z + r12*8], rax - inc r12 -parse_eol: - cmp rsi, r14 - jae parse_done - mov al, [rsi] - inc rsi - cmp al, 10 - jne parse_eol - jmp parse_line -parse_skipnl: - inc rsi - jmp parse_line -parse_done: - mov [n_boxes], r12 - - ; build every pairwise edge with squared distance as the key - lea r11, [edges] ; write pointer - xor r12, r12 ; edge count - xor r8, r8 ; i -gen_i: - cmp r8, [n_boxes] - jge gen_done - mov r13, [x + r8*8] - mov r14, [y + r8*8] - mov r15, [z + r8*8] - lea r9, [r8 + 1] ; j = i + 1 -gen_j: - cmp r9, [n_boxes] - jge gen_j_done - mov rax, r13 - sub rax, [x + r9*8] - imul rax, rax - mov rcx, rax - mov rax, r14 - sub rax, [y + r9*8] - imul rax, rax - add rcx, rax - mov rax, r15 - sub rax, [z + r9*8] - imul rax, rax - add rcx, rax ; key = dx^2 + dy^2 + dz^2 - mov [r11], rcx - mov [r11 + 8], r8d - mov [r11 + 12], r9d - add r11, 16 - inc r12 - inc r9 - jmp gen_j -gen_j_done: - inc r8 - jmp gen_i -gen_done: - mov [m_edges], r12 - - ; LSD radix sort by the 5 low bytes of the key (max key < 2^40) - lea r11, [edges] ; src - lea r12, [edges2] ; dst - xor r13, r13 ; byte pass 0..4 -rsort_pass: - cmp r13, 5 - jge rsort_done - lea rdi, [counts] - mov rcx, 256 - xor rax, rax - rep stosq - - xor rcx, rcx ; k -rs_hist: - cmp rcx, [m_edges] - jge rs_hist_done - mov rax, rcx - shl rax, 4 - add rax, r11 - movzx edx, byte [rax + r13] - inc qword [counts + rdx*8] - inc rcx - jmp rs_hist -rs_hist_done: - xor rcx, rcx ; t - xor r8, r8 ; running offset -rs_prefix: - cmp rcx, 256 - jge rs_prefix_done - mov rax, [counts + rcx*8] - mov [counts + rcx*8], r8 - add r8, rax - inc rcx - jmp rs_prefix -rs_prefix_done: - xor rcx, rcx ; k -rs_scatter: - cmp rcx, [m_edges] - jge rs_scatter_done - mov rax, rcx - shl rax, 4 - add rax, r11 ; src record - movzx edx, byte [rax + r13] - mov r9, [counts + rdx*8] - inc qword [counts + rdx*8] - mov r10, r9 - shl r10, 4 - add r10, r12 ; dst slot - mov r8, [rax] - mov [r10], r8 - mov r8, [rax + 8] - mov [r10 + 8], r8 - inc rcx - jmp rs_scatter -rs_scatter_done: - xchg r11, r12 - inc r13 - jmp rsort_pass -rsort_done: - mov [sorted_ptr], r11 - - ; union-find init - xor rcx, rcx -dsu_init: - cmp rcx, [n_boxes] - jge dsu_done - mov [parent + rcx*8], rcx - mov qword [csize + rcx*8], 1 - inc rcx - jmp dsu_init -dsu_done: - mov rax, [n_boxes] - mov [comp_count], rax - mov qword [part2], 0 - - ; Kruskal: one sorted pass drives both parts - mov r11, [sorted_ptr] - xor r15, r15 ; edge index -kloop: - cmp r15, [m_edges] - jge kdone - mov r12, r15 - shl r12, 4 - add r12, r11 ; record pointer - mov r13d, [r12 + 8] ; i - mov r14d, [r12 + 12] ; j - - mov edi, r13d - call find - mov rbx, rax ; root of i - mov edi, r14d - call find ; root of j - - cmp rbx, rax - je k_after ; already connected - - mov rcx, [csize + rbx*8] - mov rdx, [csize + rax*8] - cmp rcx, rdx - jge k_no_swap - xchg rbx, rax ; keep rbx as the larger root -k_no_swap: - mov [parent + rax*8], rbx - mov rcx, [csize + rax*8] - add [csize + rbx*8], rcx - dec qword [comp_count] - - cmp qword [comp_count], 1 - jne k_after - cmp qword [part2], 0 - jne k_after - mov rax, [x + r13*8] - imul rax, [x + r14*8] - mov [part2], rax -k_after: - cmp r15, (K_LIMIT - 1) - jne k_check_break - call compute_part1 -k_check_break: - cmp r15, (K_LIMIT - 1) - jl k_next - cmp qword [part2], 0 - je k_next - jmp kdone -k_next: - inc r15 - jmp kloop -kdone: - -print_results: - mov rcx, label1 - call print_string - mov rax, [part1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [part2] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; find: union-find root of node RDI, with path halving. -; Output: RAX = root. Clobbers RAX, RDX, RDI. -find: -.loop: - mov rax, [parent + rdi*8] - cmp rax, rdi - je .done - mov rdx, [parent + rax*8] - mov [parent + rdi*8], rdx - mov rdi, rdx - jmp .loop -.done: - ret - -; compute_part1: product of the three largest component sizes into part1. -; Clobbers RAX, RCX, R8, R9, R10. -compute_part1: - xor r8, r8 ; largest - xor r9, r9 ; 2nd - xor r10, r10 ; 3rd - xor rcx, rcx -.loop: - cmp rcx, [n_boxes] - jge .done - mov rax, [parent + rcx*8] - cmp rax, rcx - jne .next ; not a root - mov rax, [csize + rcx*8] - cmp rax, r8 - jle .try2 - mov r10, r9 - mov r9, r8 - mov r8, rax - jmp .next -.try2: - cmp rax, r9 - jle .try3 - mov r10, r9 - mov r9, rax - jmp .next -.try3: - cmp rax, r10 - jle .next - mov r10, rax -.next: - inc rcx - jmp .loop -.done: - mov rax, r8 - imul rax, r9 - imul rax, r10 - mov [part1], rax - ret diff --git a/aoc-2025/day9.asm b/aoc-2025/day9.asm deleted file mode 100644 index e5a7d0d..0000000 --- a/aoc-2025/day9.asm +++ /dev/null @@ -1,540 +0,0 @@ -; Advent of Code 2025 - Day 9 - -bits 64 -default rel - -global _start - -%include "utils/io.asm" -%include "utils/parse.asm" - -%define RAW_SIZE 262144 -%define MAXN 512 -%define MAXC 1024 -%define MAXR 1024 -%define MAXP ((MAXC + 1) * (MAXR + 1)) - -section .data - input_path db "input/day9.txt", 0 - - label1 db "Part 1: ", 0 - label2 db "Part 2: ", 0 - -section .bss - raw resb RAW_SIZE - vx resq MAXN - vy resq MAXN - xs resq MAXN - ys resq MAXN - xs_to_col resd MAXN - ys_to_row resd MAXN - col_lo resq MAXC - row_lo resq MAXR - thincol resd MAXN - thinrow resd MAXN - - vex resq MAXN ; vertical edges: x, ylo, yhi - veylo resq MAXN - veyhi resq MAXN - hey resq MAXN ; horizontal edges: y, xlo, xhi - hexlo resq MAXN - hexhi resq MAXN - - pref resd MAXP ; 2D prefix sum of unfilled cells - - raw_len resq 1 - n_v resq 1 - xn resq 1 - yn resq 1 - c_cnt resq 1 - r_cnt resq 1 - cp1 resq 1 - ve_cnt resq 1 - he_cnt resq 1 - best1 resq 1 - best2 resq 1 - -section .text - -_start: - mov rdi, input_path - lea rsi, [raw] - mov rdx, RAW_SIZE - call read_file - mov [raw_len], rax - - ; parse "X,Y" vertices in order - lea rsi, [raw] - mov rax, [raw_len] - lea r14, [raw + rax] - xor r12, r12 -parse_line: - cmp rsi, r14 - jae parse_done - mov al, [rsi] - cmp al, 10 - je parse_skipnl - cmp al, 13 - je parse_skipnl - call parse_u64 - mov [vx + r12*8], rax - inc rsi - call parse_u64 - mov [vy + r12*8], rax - inc r12 -parse_eol: - cmp rsi, r14 - jae parse_done - mov al, [rsi] - inc rsi - cmp al, 10 - jne parse_eol - jmp parse_line -parse_skipnl: - inc rsi - jmp parse_line -parse_done: - mov [n_v], r12 - - ; xs = sorted, deduped x coordinates - xor rcx, rcx -copy_xs: - cmp rcx, [n_v] - jge copy_xs_done - mov rax, [vx + rcx*8] - mov [xs + rcx*8], rax - inc rcx - jmp copy_xs -copy_xs_done: - lea rdi, [xs] - mov rsi, [n_v] - call sort_q - lea rdi, [xs] - mov rsi, [n_v] - call dedup_q - mov [xn], rax - - ; ys = sorted, deduped y coordinates - xor rcx, rcx -copy_ys: - cmp rcx, [n_v] - jge copy_ys_done - mov rax, [vy + rcx*8] - mov [ys + rcx*8], rax - inc rcx - jmp copy_ys -copy_ys_done: - lea rdi, [ys] - mov rsi, [n_v] - call sort_q - lea rdi, [ys] - mov rsi, [n_v] - call dedup_q - mov [yn], rax - - ; refined columns: thin at each xs, thick strip between - xor rcx, rcx ; i - xor r12, r12 ; column count -build_cols: - cmp rcx, [xn] - jge build_cols_done - mov [xs_to_col + rcx*4], r12d - mov rax, [xs + rcx*8] - mov [col_lo + r12*8], rax - inc r12 - mov rdx, rcx - inc rdx - cmp rdx, [xn] - jge build_cols_next - mov r8, [xs + rdx*8] - mov rax, [xs + rcx*8] - sub r8, rax - cmp r8, 1 - jle build_cols_next - inc rax - mov [col_lo + r12*8], rax - inc r12 -build_cols_next: - inc rcx - jmp build_cols -build_cols_done: - mov [c_cnt], r12 - inc r12 - mov [cp1], r12 - - ; refined rows: thin at each ys, thick strip between - xor rcx, rcx - xor r12, r12 -build_rows: - cmp rcx, [yn] - jge build_rows_done - mov [ys_to_row + rcx*4], r12d - mov rax, [ys + rcx*8] - mov [row_lo + r12*8], rax - inc r12 - mov rdx, rcx - inc rdx - cmp rdx, [yn] - jge build_rows_next - mov r8, [ys + rdx*8] - mov rax, [ys + rcx*8] - sub r8, rax - cmp r8, 1 - jle build_rows_next - inc rax - mov [row_lo + r12*8], rax - inc r12 -build_rows_next: - inc rcx - jmp build_rows -build_rows_done: - mov [r_cnt], r12 - - ; per-vertex refined thin column / row index - xor r8, r8 -map_v: - cmp r8, [n_v] - jge map_v_done - mov r13, [vx + r8*8] - xor rcx, rcx -map_v_xs: - mov rax, [xs + rcx*8] - cmp rax, r13 - je map_v_xf - inc rcx - jmp map_v_xs -map_v_xf: - mov edx, [xs_to_col + rcx*4] - mov [thincol + r8*4], edx - mov r13, [vy + r8*8] - xor rcx, rcx -map_v_ys: - mov rax, [ys + rcx*8] - cmp rax, r13 - je map_v_yf - inc rcx - jmp map_v_ys -map_v_yf: - mov edx, [ys_to_row + rcx*4] - mov [thinrow + r8*4], edx - inc r8 - jmp map_v -map_v_done: - - ; classify edges into vertical / horizontal - xor r8, r8 - xor r12, r12 ; ve count - xor r13, r13 ; he count -gen_edges: - cmp r8, [n_v] - jge gen_edges_done - mov r9, r8 - inc r9 - cmp r9, [n_v] - jne ge_nowrap - xor r9, r9 -ge_nowrap: - mov r10, [vx + r8*8] - mov r11, [vx + r9*8] - cmp r10, r11 - je ge_vert - mov rax, [vy + r8*8] - mov [hey + r13*8], rax - mov rcx, r10 - mov rdx, r11 - cmp rcx, rdx - jle ge_h_ok - xchg rcx, rdx -ge_h_ok: - mov [hexlo + r13*8], rcx - mov [hexhi + r13*8], rdx - inc r13 - jmp ge_next -ge_vert: - mov [vex + r12*8], r10 - mov rcx, [vy + r8*8] - mov rdx, [vy + r9*8] - cmp rcx, rdx - jle ge_v_ok - xchg rcx, rdx -ge_v_ok: - mov [veylo + r12*8], rcx - mov [veyhi + r12*8], rdx - inc r12 -ge_next: - inc r8 - jmp gen_edges -gen_edges_done: - mov [ve_cnt], r12 - mov [he_cnt], r13 - - ; 2D prefix sum of unfilled cells - xor r15, r15 ; refined row r -pref_r: - cmp r15, [r_cnt] - jge pref_done - mov r13, [row_lo + r15*8] ; py - xor r14, r14 ; refined col c -pref_c: - cmp r14, [c_cnt] - jge pref_c_done - mov rdi, [col_lo + r14*8] - mov rsi, r13 - call filled - mov rbx, 1 - sub rbx, rax ; unfilled indicator - - mov rax, r15 - imul rax, [cp1] ; r*cp1 - mov rcx, rax - add rcx, r14 - add rcx, 1 - mov edx, [pref + rcx*4] ; P[r][c+1] - mov rcx, rax - add rcx, r14 - mov r8d, [pref + rcx*4] ; P[r][c] - mov rcx, rax - add rcx, [cp1] - mov r9, rcx ; (r+1)*cp1 - add rcx, r14 - mov r10d, [pref + rcx*4] ; P[r+1][c] - mov eax, ebx - add eax, edx - add eax, r10d - sub eax, r8d - mov rcx, r9 - add rcx, r14 - add rcx, 1 - mov [pref + rcx*4], eax ; P[r+1][c+1] - inc r14 - jmp pref_c -pref_c_done: - inc r15 - jmp pref_r -pref_done: - - ; all pairs: part 1 = max area, part 2 = max area fully inside - mov qword [best1], 0 - mov qword [best2], 0 - xor r8, r8 -pair_i: - cmp r8, [n_v] - jge pair_done - mov r12d, [thincol + r8*4] - mov r13d, [thinrow + r8*4] - mov r14, [vx + r8*8] - mov r15, [vy + r8*8] - lea r9, [r8 + 1] -pair_j: - cmp r9, [n_v] - jge pair_j_done - - ; area = (|xi-xj| + 1) * (|yi-yj| + 1) - mov rax, r14 - sub rax, [vx + r9*8] - jns .ax - neg rax -.ax: - inc rax - mov rbx, rax - mov rax, r15 - sub rax, [vy + r9*8] - jns .ay - neg rax -.ay: - inc rax - imul rax, rbx - cmp rax, [best1] - jle .no1 - mov [best1], rax -.no1: - push rax ; save area - - ; refined block: c1,c2 then r1,r2 - mov eax, [thincol + r9*4] - mov ecx, r12d - cmp ecx, eax - jle .cc - xchg ecx, eax -.cc: - mov edi, ecx ; c1 - mov esi, eax ; c2 - mov eax, [thinrow + r9*4] - mov ecx, r13d - cmp ecx, eax - jle .rr - xchg ecx, eax -.rr: - mov edx, ecx ; r1 - mov ecx, eax ; r2 - call block_unf - pop rbx ; area - test eax, eax - jnz .no2 ; contains unfilled cells - cmp rbx, [best2] - jle .no2 - mov [best2], rbx -.no2: - inc r9 - jmp pair_j -pair_j_done: - inc r8 - jmp pair_i -pair_done: - -print_results: - mov rcx, label1 - call print_string - mov rax, [best1] - call print_int64 - call print_newline - - mov rcx, label2 - call print_string - mov rax, [best2] - call print_int64 - call print_newline - - mov rax, SYS_EXIT - xor rdi, rdi - syscall - -; filled: is tile (RDI=px, RSI=py) red or green (inside or on the loop)? -; Output: RAX = 1 if filled, else 0. Clobbers RAX, RCX, RDX, R10, R11. -filled: - xor ecx, ecx ; on-edge flag - xor r11, r11 ; crossing count - xor r10, r10 ; edge index -.v_loop: - cmp r10, [ve_cnt] - jge .v_done - mov rax, [vex + r10*8] - cmp rax, rdi - jne .v_cross - mov rdx, [veylo + r10*8] - cmp rsi, rdx - jl .v_cross - mov rdx, [veyhi + r10*8] - cmp rsi, rdx - jg .v_cross - mov ecx, 1 ; on a vertical edge -.v_cross: - mov rax, [vex + r10*8] - cmp rax, rdi - jle .v_next - mov rdx, [veylo + r10*8] - cmp rsi, rdx - jl .v_next - mov rdx, [veyhi + r10*8] - cmp rsi, rdx - jge .v_next - inc r11 -.v_next: - inc r10 - jmp .v_loop -.v_done: - test ecx, ecx - jnz .yes - xor r10, r10 -.h_loop: - cmp r10, [he_cnt] - jge .h_done - mov rax, [hey + r10*8] - cmp rax, rsi - jne .h_next - mov rdx, [hexlo + r10*8] - cmp rdi, rdx - jl .h_next - mov rdx, [hexhi + r10*8] - cmp rdi, rdx - jg .h_next - jmp .yes -.h_next: - inc r10 - jmp .h_loop -.h_done: - mov rax, r11 - and rax, 1 - ret -.yes: - mov rax, 1 - ret - -; block_unf: count of unfilled refined cells in [c1,c2] x [r1,r2]. -; In: RDI=c1, RSI=c2, RDX=r1, RCX=r2. Out: EAX. Clobbers RAX, R10, R11. -block_unf: - mov r10, rcx - inc r10 - imul r10, [cp1] ; (r2+1)*cp1 - mov r11, r10 - add r11, rsi - add r11, 1 - mov eax, [pref + r11*4] ; A - mov r11, r10 - add r11, rdi - sub eax, [pref + r11*4] ; - C - mov r10, rdx - imul r10, [cp1] ; r1*cp1 - mov r11, r10 - add r11, rsi - add r11, 1 - sub eax, [pref + r11*4] ; - B - mov r11, r10 - add r11, rdi - add eax, [pref + r11*4] ; + D - ret - -; sort_q: insertion sort of qword array RDI[0..RSI-1] ascending. -; Clobbers RAX, RDX, R8, R9, R10. -sort_q: - mov r8, 1 -.i: - cmp r8, rsi - jge .done - mov r10, [rdi + r8*8] - mov r9, r8 - dec r9 -.j: - cmp r9, 0 - jl .place - mov rax, [rdi + r9*8] - cmp rax, r10 - jle .place - mov rdx, r9 - inc rdx - mov [rdi + rdx*8], rax - dec r9 - jmp .j -.place: - mov rdx, r9 - inc rdx - mov [rdi + rdx*8], r10 - inc r8 - jmp .i -.done: - ret - -; dedup_q: remove consecutive duplicates in sorted RDI[0..RSI-1]. -; Out: RAX = new length. Clobbers RAX, RCX, RDX, R8. -dedup_q: - xor rax, rax - xor rcx, rcx -.loop: - cmp rcx, rsi - jge .done - test rax, rax - jz .keep - mov rdx, [rdi + rcx*8] - mov r8, rax - dec r8 - cmp rdx, [rdi + r8*8] - je .skip -.keep: - mov rdx, [rdi + rcx*8] - mov [rdi + rax*8], rdx - inc rax -.skip: - inc rcx - jmp .loop -.done: - ret diff --git a/aoc-2025/utils/io.asm b/aoc-2025/utils/io.asm deleted file mode 100644 index 2081671..0000000 --- a/aoc-2025/utils/io.asm +++ /dev/null @@ -1,107 +0,0 @@ -; utils/io.asm - shared syscall constants, file reading, and output helpers. -; This file is %included (not linked) by each day's solution. - -%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 - -section .data - newline db 10 - -section .bss - number_buffer resb 32 - -section .text - -; read_file: open the path in RDI read-only, read up to RDX bytes into the -; buffer in RSI, close, and return the number of bytes read in RAX. -read_file: - mov r8, rsi ; buffer base - mov r9, rdx ; capacity - mov rax, SYS_OPEN - mov rsi, O_RDONLY - xor rdx, rdx - syscall - mov r10, rax ; fd - xor r11, r11 ; bytes read so far -.loop: - mov rax, SYS_READ - mov rdi, r10 - lea rsi, [r8 + r11] - mov rdx, r9 - sub rdx, r11 - syscall - cmp rax, 0 - jle .done - add r11, rax - jmp .loop -.done: - mov rax, SYS_CLOSE - mov rdi, r10 - syscall - mov rax, r11 - ret - -print_newline: - mov rax, SYS_WRITE - mov rdi, STDOUT - mov rsi, newline - mov rdx, 1 - syscall - ret - -; print_int64: print the unsigned integer in RAX in decimal. -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: print the NUL-terminated string pointed to by RCX. -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 diff --git a/aoc-2025/utils/parse.asm b/aoc-2025/utils/parse.asm deleted file mode 100644 index 833cb4e..0000000 --- a/aoc-2025/utils/parse.asm +++ /dev/null @@ -1,22 +0,0 @@ -; utils/parse.asm - decimal parsing helper. - -section .text - -; parse_u64: read decimal digits at [RSI] into RAX, advancing RSI past them. -; Stops on the first non-digit. Clobbers RAX, RDX. -parse_u64: - xor rax, rax -.digit: - mov dl, [rsi] - cmp dl, '0' - jl .done - cmp dl, '9' - jg .done - sub dl, '0' - movzx rdx, dl - imul rax, rax, 10 - add rax, rdx - inc rsi - jmp .digit -.done: - ret diff --git a/utils/io.asm b/utils/io.asm new file mode 100644 index 0000000..2081671 --- /dev/null +++ b/utils/io.asm @@ -0,0 +1,107 @@ +; utils/io.asm - shared syscall constants, file reading, and output helpers. +; This file is %included (not linked) by each day's solution. + +%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 + +section .data + newline db 10 + +section .bss + number_buffer resb 32 + +section .text + +; read_file: open the path in RDI read-only, read up to RDX bytes into the +; buffer in RSI, close, and return the number of bytes read in RAX. +read_file: + mov r8, rsi ; buffer base + mov r9, rdx ; capacity + mov rax, SYS_OPEN + mov rsi, O_RDONLY + xor rdx, rdx + syscall + mov r10, rax ; fd + xor r11, r11 ; bytes read so far +.loop: + mov rax, SYS_READ + mov rdi, r10 + lea rsi, [r8 + r11] + mov rdx, r9 + sub rdx, r11 + syscall + cmp rax, 0 + jle .done + add r11, rax + jmp .loop +.done: + mov rax, SYS_CLOSE + mov rdi, r10 + syscall + mov rax, r11 + ret + +print_newline: + mov rax, SYS_WRITE + mov rdi, STDOUT + mov rsi, newline + mov rdx, 1 + syscall + ret + +; print_int64: print the unsigned integer in RAX in decimal. +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: print the NUL-terminated string pointed to by RCX. +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 diff --git a/utils/parse.asm b/utils/parse.asm new file mode 100644 index 0000000..833cb4e --- /dev/null +++ b/utils/parse.asm @@ -0,0 +1,22 @@ +; utils/parse.asm - decimal parsing helper. + +section .text + +; parse_u64: read decimal digits at [RSI] into RAX, advancing RSI past them. +; Stops on the first non-digit. Clobbers RAX, RDX. +parse_u64: + xor rax, rax +.digit: + mov dl, [rsi] + cmp dl, '0' + jl .done + cmp dl, '9' + jg .done + sub dl, '0' + movzx rdx, dl + imul rax, rax, 10 + add rax, rdx + inc rsi + jmp .digit +.done: + ret -- cgit v1.3