; Advent of Code 2025 - Day 8 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 MAXN 1024 %define MAXE (MAXN * (MAXN - 1) / 2) %define K_LIMIT 1000 ; part 1 connects the K_LIMIT closest pairs section .data input_path db "input/day8.txt", 0 newline db 10 label1 db "Part 1: ", 0 label2 db "Part 2: ", 0 section .bss raw resb RAW_SIZE x resq MAXN y resq MAXN z resq MAXN edges resb (MAXE * 16) ; records: [dist2:8][i:4][j:4] edges2 resb (MAXE * 16) ; radix ping-pong buffer counts resq 256 parent resq MAXN csize resq MAXN raw_len resq 1 n_boxes resq 1 m_edges resq 1 sorted_ptr resq 1 comp_count resq 1 part1 resq 1 part2 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 ; parse "X,Y,Z" lines into x/y/z, counting boxes lea rsi, [raw] mov rax, [raw_len] lea r14, [raw + rax] ; end pointer xor r12, r12 ; box index parse_line: cmp rsi, r14 jae parse_done mov al, [rsi] cmp al, 10 je parse_skipnl cmp al, 13 je parse_skipnl call parse_u64 mov [x + r12*8], rax inc rsi call parse_u64 mov [y + r12*8], rax inc rsi call parse_u64 mov [z + r12*8], rax inc r12 parse_eol: cmp rsi, r14 jae parse_done mov al, [rsi] inc rsi cmp al, 10 jne parse_eol jmp parse_line parse_skipnl: inc rsi jmp parse_line parse_done: mov [n_boxes], r12 ; build every pairwise edge with squared distance as the key lea r11, [edges] ; write pointer xor r12, r12 ; edge count xor r8, r8 ; i gen_i: cmp r8, [n_boxes] jge gen_done mov r13, [x + r8*8] mov r14, [y + r8*8] mov r15, [z + r8*8] lea r9, [r8 + 1] ; j = i + 1 gen_j: cmp r9, [n_boxes] jge gen_j_done mov rax, r13 sub rax, [x + r9*8] imul rax, rax mov rcx, rax mov rax, r14 sub rax, [y + r9*8] imul rax, rax add rcx, rax mov rax, r15 sub rax, [z + r9*8] imul rax, rax add rcx, rax ; key = dx^2 + dy^2 + dz^2 mov [r11], rcx mov [r11 + 8], r8d mov [r11 + 12], r9d add r11, 16 inc r12 inc r9 jmp gen_j gen_j_done: inc r8 jmp gen_i gen_done: mov [m_edges], r12 ; LSD radix sort by the 5 low bytes of the key (max key < 2^40) lea r11, [edges] ; src lea r12, [edges2] ; dst xor r13, r13 ; byte pass 0..4 rsort_pass: cmp r13, 5 jge rsort_done lea rdi, [counts] mov rcx, 256 xor rax, rax rep stosq xor rcx, rcx ; k rs_hist: cmp rcx, [m_edges] jge rs_hist_done mov rax, rcx shl rax, 4 add rax, r11 movzx edx, byte [rax + r13] inc qword [counts + rdx*8] inc rcx jmp rs_hist rs_hist_done: xor rcx, rcx ; t xor r8, r8 ; running offset rs_prefix: cmp rcx, 256 jge rs_prefix_done mov rax, [counts + rcx*8] mov [counts + rcx*8], r8 add r8, rax inc rcx jmp rs_prefix rs_prefix_done: xor rcx, rcx ; k rs_scatter: cmp rcx, [m_edges] jge rs_scatter_done mov rax, rcx shl rax, 4 add rax, r11 ; src record movzx edx, byte [rax + r13] mov r9, [counts + rdx*8] inc qword [counts + rdx*8] mov r10, r9 shl r10, 4 add r10, r12 ; dst slot mov r8, [rax] mov [r10], r8 mov r8, [rax + 8] mov [r10 + 8], r8 inc rcx jmp rs_scatter rs_scatter_done: xchg r11, r12 inc r13 jmp rsort_pass rsort_done: mov [sorted_ptr], r11 ; union-find init xor rcx, rcx dsu_init: cmp rcx, [n_boxes] jge dsu_done mov [parent + rcx*8], rcx mov qword [csize + rcx*8], 1 inc rcx jmp dsu_init dsu_done: mov rax, [n_boxes] mov [comp_count], rax mov qword [part2], 0 ; Kruskal: one sorted pass drives both parts mov r11, [sorted_ptr] xor r15, r15 ; edge index kloop: cmp r15, [m_edges] jge kdone mov r12, r15 shl r12, 4 add r12, r11 ; record pointer mov r13d, [r12 + 8] ; i mov r14d, [r12 + 12] ; j mov edi, r13d call find mov rbx, rax ; root of i mov edi, r14d call find ; root of j cmp rbx, rax je k_after ; already connected mov rcx, [csize + rbx*8] mov rdx, [csize + rax*8] cmp rcx, rdx jge k_no_swap xchg rbx, rax ; keep rbx as the larger root k_no_swap: mov [parent + rax*8], rbx mov rcx, [csize + rax*8] add [csize + rbx*8], rcx dec qword [comp_count] cmp qword [comp_count], 1 jne k_after cmp qword [part2], 0 jne k_after mov rax, [x + r13*8] imul rax, [x + r14*8] mov [part2], rax k_after: cmp r15, (K_LIMIT - 1) jne k_check_break call compute_part1 k_check_break: cmp r15, (K_LIMIT - 1) jl k_next cmp qword [part2], 0 je k_next jmp kdone k_next: inc r15 jmp kloop kdone: 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 ; find: union-find root of node RDI, with path halving. ; Output: RAX = root. Clobbers RAX, RDX, RDI. find: .loop: mov rax, [parent + rdi*8] cmp rax, rdi je .done mov rdx, [parent + rax*8] mov [parent + rdi*8], rdx mov rdi, rdx jmp .loop .done: ret ; compute_part1: product of the three largest component sizes into part1. ; Clobbers RAX, RCX, R8, R9, R10. compute_part1: xor r8, r8 ; largest xor r9, r9 ; 2nd xor r10, r10 ; 3rd xor rcx, rcx .loop: cmp rcx, [n_boxes] jge .done mov rax, [parent + rcx*8] cmp rax, rcx jne .next ; not a root mov rax, [csize + rcx*8] cmp rax, r8 jle .try2 mov r10, r9 mov r9, r8 mov r8, rax jmp .next .try2: cmp rax, r9 jle .try3 mov r10, r9 mov r9, rax jmp .next .try3: cmp rax, r10 jle .next mov r10, rax .next: inc rcx jmp .loop .done: mov rax, r8 imul rax, r9 imul rax, r10 mov [part1], rax ret ; parse_u64: read decimal digits at [RSI], advancing RSI. Clobbers RAX, RDX. parse_u64: xor rax, rax .digit: mov dl, [rsi] cmp dl, '0' jl .done cmp dl, '9' jg .done sub dl, '0' movzx rdx, dl imul rax, rax, 10 add rax, rdx inc rsi jmp .digit .done: 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