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
|
; Advent of Code 2025 - Day 5
bits 64
default rel
global _start
%include "utils/io.asm"
%include "utils/parse.asm"
%define RAW_SIZE 1048576 ; 1 MiB scratch for the raw file
%define MAX_RANGES 8192 ; plenty for the ~177 input ranges
section .data
input_path db "input/day5.txt", 0
label1 db "Part 1: ", 0
label2 db "Part 2: ", 0
section .bss
raw resb RAW_SIZE
starts resq MAX_RANGES ; range/merged-interval starts
ends resq MAX_RANGES ; range/merged-interval ends
raw_len resq 1
n_ranges resq 1 ; ranges parsed in section 1
n_merged resq 1 ; disjoint intervals after merge
phase resq 1 ; 0 = ranges, 1 = available IDs
part1 resq 1
part2 resq 1
section .text
_start:
mov rdi, input_path
lea rsi, [raw]
mov rdx, RAW_SIZE
call read_file
mov [raw_len], rax
; RSI = cursor, R14 = end pointer (both preserved across helper calls)
lea rsi, [raw]
mov rax, [raw_len]
lea r14, [raw + rax]
mov qword [phase], 0
scan_line:
cmp rsi, r14
jae scan_done
mov al, [rsi]
cmp al, 10 ; LF -> blank line
je got_blank
cmp al, 13 ; CR -> blank line
je got_blank
cmp qword [phase], 0
jne do_avail
call parse_u64 ; RAX = start
mov rcx, [n_ranges]
mov [starts + rcx*8], rax
inc rsi ; skip '-'
call parse_u64 ; RAX = end
mov rcx, [n_ranges]
mov [ends + rcx*8], rax
inc qword [n_ranges]
jmp skip_eol
do_avail:
call parse_u64
mov rdi, rax
call is_fresh ; RAX = 1 if fresh
test rax, rax
jz skip_eol
inc qword [part1]
jmp skip_eol
got_blank:
; the blank line separates the two sections
cmp qword [phase], 0
jne skip_eol
call finalize_ranges ; sort + merge, compute part2
mov qword [phase], 1
; fall through
skip_eol:
cmp rsi, r14
jae scan_done
mov al, [rsi]
inc rsi
cmp al, 10 ; consume through the LF
jne skip_eol
jmp scan_line
scan_done:
; safety: if there was no blank line, still finalize the ranges
cmp qword [phase], 0
jne print_results
call finalize_ranges
print_results:
mov rcx, label1
call print_string
mov rax, [part1]
call print_int64
call print_newline
mov rcx, label2
call print_string
mov rax, [part2]
call print_int64
call print_newline
mov rax, SYS_EXIT
xor rdi, rdi
syscall
; is_fresh: test membership of an ID in the merged intervals.
; Input: RDI = id
; Output: RAX = 1 if the id lies in any interval, else 0
; Intervals are sorted ascending and disjoint, so we can stop early.
; Clobbers: RAX, RCX
is_fresh:
xor rcx, rcx
.loop:
cmp rcx, [n_merged]
jge .no
mov rax, [starts + rcx*8]
cmp rdi, rax
jl .no ; id below this start -> below all later ones
mov rax, [ends + rcx*8]
cmp rdi, rax
jle .yes ; start <= id <= end
inc rcx
jmp .loop
.no:
xor eax, eax
ret
.yes:
mov eax, 1
ret
; finalize_ranges: insertion-sort the ranges by start, merge overlapping /
; touching ones in place, store the disjoint intervals back into starts/ends,
; set n_merged, and accumulate their total size into part2.
; Clobbers: RAX, RCX, RDX, R8, R9, R10, R11, R12, R13
finalize_ranges:
mov r8, 1 ; i
.sort_i:
cmp r8, [n_ranges]
jge .sorted
mov r10, [starts + r8*8] ; key_s
mov r11, [ends + r8*8] ; key_e
mov r9, r8
dec r9 ; j = i - 1
.sort_j:
cmp r9, 0
jl .sort_place
mov rax, [starts + r9*8]
cmp rax, r10
jle .sort_place ; starts[j] <= key -> in place
mov rdx, r9
inc rdx ; j + 1
mov [starts + rdx*8], rax ; shift start
mov rcx, [ends + r9*8]
mov [ends + rdx*8], rcx ; shift end
dec r9
jmp .sort_j
.sort_place:
mov rdx, r9
inc rdx
mov [starts + rdx*8], r10
mov [ends + rdx*8], r11
inc r8
jmp .sort_i
.sorted:
cmp qword [n_ranges], 0
je .empty
mov r10, [starts] ; cur_lo
mov r11, [ends] ; cur_hi
mov r8, 1 ; i
xor r12, r12 ; part2 accumulator
xor r13, r13 ; write index
.merge_loop:
cmp r8, [n_ranges]
jge .flush
mov rax, [starts + r8*8] ; s
mov rcx, [ends + r8*8] ; e
cmp rax, r11
jg .gap ; s > cur_hi -> disjoint
cmp rcx, r11 ; overlap: cur_hi = max(cur_hi, e)
jle .no_extend
mov r11, rcx
.no_extend:
inc r8
jmp .merge_loop
.gap:
call .emit
mov r10, rax ; begin new interval
mov r11, rcx
inc r8
jmp .merge_loop
.flush:
call .emit
mov [n_merged], r13
mov [part2], r12
ret
.empty:
mov qword [n_merged], 0
mov qword [part2], 0
ret
; local helper: emit [r10, r11] as merged interval r13, add its size to r12
.emit:
mov [starts + r13*8], r10
mov [ends + r13*8], r11
inc r13
mov rdx, r11
sub rdx, r10
inc rdx ; end - start + 1
add r12, rdx
ret
|
