-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsolve.asm
377 lines (299 loc) · 5.64 KB
/
solve.asm
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
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
section .bss
area:
.width equ (96 + 2) ; width + border
.height equ (90 + 2)
.length equ area.width * area.height
; using two area copies to simplify the update
.phase resb 1 ; which copy is in use
.one resb area.length
.two resb area.length
buf: resb 32
border equ ' '
occupied equ '#'
vacant equ 'L'
floor equ '.'
section .data
scanner:
.n dd 0 ; current north-side cell of the scanner (byte ptr)
dd -area.width ; increment to move one step further (const)
.s dd 0
dd area.width
.w dd 0
dd -1
.e dd 0
dd 1
.nw dd 0
dd -area.width - 1
.ne dd 0
dd -area.width + 1
.sw dd 0
dd area.width - 1
.se dd 0
dd area.width + 1
section .rodata
eol: db 10
section .text
global _start
%macro push 1-*
%rep %0
push %1
%rotate 1
%endrep
%endmacro
%macro pop 1-*
%rep %0
%rotate -1
pop %1
%endrep
%endmacro
;; fill areas with the border code
prefill:
push ecx, edx
mov edx, area.one
mov ecx, area.length
add ecx, ecx
.prefill_loop:
mov [edx], byte border
inc edx
loop .prefill_loop
pop ecx, edx
ret
read_input:
call prefill
mov edx, area.height - 2
mov ecx, area.one
mov ecx, area.one + area.width + 1
.read_loop:
push edx
mov eax, 3 ; sys.read
xor ebx, ebx
mov edx, area.width-1 ; length ( real width + \n )
int 80h
add ecx, area.width-2
mov [ecx], byte border
add ecx, 2
pop edx
dec edx
jnz .read_loop
ret
;; init scanner for the cell
;; eax = cell ptr
init_scanner:
pusha
mov esi, scanner
mov ebx, 0
mov ecx, 8
.init_loop:
mov edx, eax
add edx, [esi + ebx + 4]
mov [esi + ebx], edx
add ebx, 8
loop .init_loop
popa
ret
;; expand scanner borders until each cell
;; is not a floor (i.e. a L, # or a border)
scan:
push eax, ebx, ecx, edx
.scan_search_loop:
mov edx, scanner
mov ecx, 8
xor al, al
.scan_cell_loop:
mov ebx, [edx]
mov ah, [ebx]
cmp ah, floor
jne .scan_next
inc al
add ebx, [edx+4]
mov [edx], ebx
.scan_next:
add edx, 8
loop .scan_cell_loop
test al, al
jnz .scan_search_loop
pop eax, ebx, ecx, edx
ret
count_occupied_in_scanner:
push ebx, ecx, edx
mov ebx, scanner
mov ecx, 8
xor eax, eax
.count_scanner_loop:
mov edx, [ebx]
mov ah, byte [edx]
cmp ah, occupied
jne .count_scanner_next
inc al
.count_scanner_next:
add ebx, 8
loop .count_scanner_loop
xor ah, ah
pop ebx, ecx, edx
ret
count_occupied:
push ebx, ecx, edx
mov edx, area.one
mov al, [area.phase]
test al, al
jz .count_start
mov edx, area.two
.count_start:
xor eax, eax
mov ecx, area.length
.count_loop:
mov bl, [edx]
cmp bl, occupied
jne .count_next
inc eax
.count_next:
inc edx
loop .count_loop
pop ebx, ecx, edx
ret
switch_phase:
push eax
xor eax, eax
mov al, [area.phase]
xor al, 1
mov [area.phase], al
pop eax
ret
;; print decimal int from eax
print_decimal:
pusha
mov ecx, buf
mov ebx, 10000
call .print_add_digit
mov ebx, 1000
call .print_add_digit
mov ebx, 100
call .print_add_digit
mov ebx, 10
call .print_add_digit
add al, '0'
mov [ecx], al
inc ecx
jmp .print_out
.print_add_digit:
xor edx, edx
div ebx
add al, '0'
mov [ecx], al
mov eax, edx
inc ecx
ret
.print_out:
mov [ecx], byte 10
mov edx, 6
mov ecx, buf
.print_remove_trailing_loop:
xor eax, eax
mov al, [ecx]
cmp al, '0'
jne .print_call
inc ecx
dec edx
jmp .print_remove_trailing_loop
.print_call:
mov eax, 4 ; sys_write
mov ebx, 1
int 80h
popa
ret
print_map:
pusha
mov ebx, area.height
mov ecx, area.one
mov al, [area.phase]
test al, al
jz .print_start
mov ecx, area.two
.print_start:
push ebx, ecx
mov edx, area.width
mov eax, 4
mov ebx, 1
int 80h
mov ecx, eol
mov eax, 4
mov edx, 1
int 80h
pop ebx, ecx
add ecx, area.width
dec ebx
jnz .print_start
popa
ret
;; apply the rules to each cell in the current area
;; changes are made to the shadow one, then switch the phase
one_step:
pusha
xor ecx, ecx
mov bh, area.height-2 ; row
mov bl, area.width-2 ; col
mov edx, (area.height-2) * area.width + area.width - 2
mov esi, area.one
mov edi, area.two
mov al, [area.phase]
test al, al
jz .step_start
xchg esi, edi
.step_start:
mov cl, [esi + edx]
cmp cl, border
je .step_loop_next
cmp cl, floor
je .step_update
lea eax, [esi + edx]
call init_scanner
%ifenv PART2
call scan
%endif
call count_occupied_in_scanner
cmp cl, occupied
jne .step_not_occcupied
%ifenv PART2
cmp al, 5
%else
cmp al, 4
%endif
jl .step_update
mov ch, 1
mov cl, vacant
jmp .step_loop_next
.step_not_occcupied:
cmp cl, vacant
jne .step_update
test al, al
jnz .step_update
mov ch, 1
mov cl, occupied
.step_update:
mov [edi + edx], cl
.step_loop_next:
dec edx
dec bl
jnz .step_start
mov bl, area.width-2
sub edx, 2
dec bh
jnz .step_start
call switch_phase
test ch, ch
popa
ret
_start:
mov [area.phase], byte 0
call read_input
converge_loop:
call one_step
jnz converge_loop
call count_occupied
test eax, eax
jz exit
call print_decimal
exit:
mov eax, 1
xor ebx, ebx
int 80h