From 42b942404eef0c2af3fc1ec88414793cc6b940a3 Mon Sep 17 00:00:00 2001 From: hachem Date: Sun, 6 Sep 2026 00:23:10 +0200 Subject: refactor: add remaining days --- aoc-2025/day11.asm | 320 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 320 insertions(+) create mode 100644 aoc-2025/day11.asm (limited to 'aoc-2025/day11.asm') diff --git a/aoc-2025/day11.asm b/aoc-2025/day11.asm new file mode 100644 index 0000000..bf92fad --- /dev/null +++ b/aoc-2025/day11.asm @@ -0,0 +1,320 @@ +; Advent of Code 2025 - Day 11 + +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 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 + + newline db 10 + + 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 + + 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 + + ; 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 + +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 -- cgit v1.3