1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
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
|
