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