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