diff options
Diffstat (limited to 'aoc-2025/day9.asm')
| -rw-r--r-- | aoc-2025/day9.asm | 644 |
1 files changed, 644 insertions, 0 deletions
diff --git a/aoc-2025/day9.asm b/aoc-2025/day9.asm new file mode 100644 index 0000000..8b0edcf --- /dev/null +++ b/aoc-2025/day9.asm @@ -0,0 +1,644 @@ +; Advent of Code 2025 - Day 9 + +bits 64 +default rel + +global _start + +%define SYS_EXIT 60 +%define SYS_READ 0 +%define SYS_WRITE 1 +%define SYS_OPEN 2 +%define SYS_CLOSE 3 + +%define O_RDONLY 0 +%define STDOUT 1 + +%define RAW_SIZE 262144 +%define MAXN 512 +%define MAXC 1024 +%define MAXR 1024 +%define MAXP ((MAXC + 1) * (MAXR + 1)) + +section .data + input_path db "input/day9.txt", 0 + + newline db 10 + + 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 + + number_buffer resb 32 + +section .text + +_start: + mov rax, SYS_OPEN + mov rdi, input_path + mov rsi, O_RDONLY + xor rdx, rdx + syscall + mov r12, rax + + xor r13, r13 +read_loop: + mov rax, SYS_READ + mov rdi, r12 + lea rsi, [raw + r13] + mov rdx, RAW_SIZE + sub rdx, r13 + syscall + cmp rax, 0 + jle read_done + add r13, rax + jmp read_loop +read_done: + mov [raw_len], r13 + mov rax, SYS_CLOSE + mov rdi, r12 + syscall + + ; 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 + +; parse_u64: read decimal digits at [RSI], advancing RSI. 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 + +print_newline: + mov rax, SYS_WRITE + mov rdi, STDOUT + mov rsi, newline + mov rdx, 1 + syscall + ret + +print_int64: + mov rdi, number_buffer+31 + mov byte [rdi], 0 + dec rdi + + cmp rax, 0 + jne .conv + + mov byte [rdi], '0' + jmp .done +.conv: + mov rbx, 10 +.next: + xor rdx, rdx + div rbx + add dl, '0' + mov [rdi], dl + dec rdi + test rax, rax + jnz .next + + inc rdi +.done: + mov rax, SYS_WRITE + mov rsi, rdi + mov rdi, STDOUT + mov rdx, number_buffer+31 + sub rdx, rsi + syscall + ret + +print_string: + push rcx + push rdx + mov rdx, 0 +.length: + cmp byte [rcx+rdx], 0 + je .submit + inc rdx + jmp .length +.submit: + mov rax, SYS_WRITE + mov rdi, STDOUT + mov rsi, rcx + syscall + pop rdx + pop rcx + ret |