diff options
Diffstat (limited to '2025/day5.asm')
| -rw-r--r-- | 2025/day5.asm | 225 |
1 files changed, 225 insertions, 0 deletions
diff --git a/2025/day5.asm b/2025/day5.asm new file mode 100644 index 0000000..4718343 --- /dev/null +++ b/2025/day5.asm @@ -0,0 +1,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 |