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 ++++++++++++++++++++++++++++++++++++++++++++ 12 files changed, 4160 insertions(+) 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 (limited to '2025') 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 -- cgit v1.3