diff options
Diffstat (limited to 'aoc-2025/day9.asm')
| -rw-r--r-- | aoc-2025/day9.asm | 540 |
1 files changed, 0 insertions, 540 deletions
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 |