path: root/aoc-2025/day9.asm

; Advent of Code 2025 - Day 9

bits 64
default rel

global _start

%include "utils/io.asm"
%include "utils/parse.asm"

%define RAW_SIZE   262144
%define MAXN       512
%define MAXC       1024
%define MAXR       1024
%define MAXP       ((MAXC + 1) * (MAXR + 1))

section .data
    input_path db "input/day9.txt", 0

    label1     db "Part 1: ", 0
    label2     db "Part 2: ", 0

section .bss
    raw           resb RAW_SIZE
    vx            resq MAXN
    vy            resq MAXN
    xs            resq MAXN
    ys            resq MAXN
    xs_to_col     resd MAXN
    ys_to_row     resd MAXN
    col_lo        resq MAXC
    row_lo        resq MAXR
    thincol       resd MAXN
    thinrow       resd MAXN

    vex           resq MAXN       ; vertical edges: x, ylo, yhi
    veylo         resq MAXN
    veyhi         resq MAXN
    hey           resq MAXN       ; horizontal edges: y, xlo, xhi
    hexlo         resq MAXN
    hexhi         resq MAXN

    pref          resd MAXP       ; 2D prefix sum of unfilled cells

    raw_len       resq 1
    n_v           resq 1
    xn            resq 1
    yn            resq 1
    c_cnt         resq 1
    r_cnt         resq 1
    cp1           resq 1
    ve_cnt        resq 1
    he_cnt        resq 1
    best1         resq 1
    best2         resq 1

section .text

_start:
    mov     rdi, input_path
    lea     rsi, [raw]
    mov     rdx, RAW_SIZE
    call    read_file
    mov     [raw_len], rax

    ; parse "X,Y" vertices in order
    lea     rsi, [raw]
    mov     rax, [raw_len]
    lea     r14, [raw + rax]
    xor     r12, r12
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     [vx + r12*8], rax
    inc     rsi
    call    parse_u64
    mov     [vy + 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_v], r12

    ; xs = sorted, deduped x coordinates
    xor     rcx, rcx
copy_xs:
    cmp     rcx, [n_v]
    jge     copy_xs_done
    mov     rax, [vx + rcx*8]
    mov     [xs + rcx*8], rax
    inc     rcx
    jmp     copy_xs
copy_xs_done:
    lea     rdi, [xs]
    mov     rsi, [n_v]
    call    sort_q
    lea     rdi, [xs]
    mov     rsi, [n_v]
    call    dedup_q
    mov     [xn], rax

    ; ys = sorted, deduped y coordinates
    xor     rcx, rcx
copy_ys:
    cmp     rcx, [n_v]
    jge     copy_ys_done
    mov     rax, [vy + rcx*8]
    mov     [ys + rcx*8], rax
    inc     rcx
    jmp     copy_ys
copy_ys_done:
    lea     rdi, [ys]
    mov     rsi, [n_v]
    call    sort_q
    lea     rdi, [ys]
    mov     rsi, [n_v]
    call    dedup_q
    mov     [yn], rax

    ; refined columns: thin at each xs, thick strip between
    xor     rcx, rcx      ; i
    xor     r12, r12      ; column count
build_cols:
    cmp     rcx, [xn]
    jge     build_cols_done
    mov     [xs_to_col + rcx*4], r12d
    mov     rax, [xs + rcx*8]
    mov     [col_lo + r12*8], rax
    inc     r12
    mov     rdx, rcx
    inc     rdx
    cmp     rdx, [xn]
    jge     build_cols_next
    mov     r8, [xs + rdx*8]
    mov     rax, [xs + rcx*8]
    sub     r8, rax
    cmp     r8, 1
    jle     build_cols_next
    inc     rax
    mov     [col_lo + r12*8], rax
    inc     r12
build_cols_next:
    inc     rcx
    jmp     build_cols
build_cols_done:
    mov     [c_cnt], r12
    inc     r12
    mov     [cp1], r12

    ; refined rows: thin at each ys, thick strip between
    xor     rcx, rcx
    xor     r12, r12
build_rows:
    cmp     rcx, [yn]
    jge     build_rows_done
    mov     [ys_to_row + rcx*4], r12d
    mov     rax, [ys + rcx*8]
    mov     [row_lo + r12*8], rax
    inc     r12
    mov     rdx, rcx
    inc     rdx
    cmp     rdx, [yn]
    jge     build_rows_next
    mov     r8, [ys + rdx*8]
    mov     rax, [ys + rcx*8]
    sub     r8, rax
    cmp     r8, 1
    jle     build_rows_next
    inc     rax
    mov     [row_lo + r12*8], rax
    inc     r12
build_rows_next:
    inc     rcx
    jmp     build_rows
build_rows_done:
    mov     [r_cnt], r12

    ; per-vertex refined thin column / row index
    xor     r8, r8
map_v:
    cmp     r8, [n_v]
    jge     map_v_done
    mov     r13, [vx + r8*8]
    xor     rcx, rcx
map_v_xs:
    mov     rax, [xs + rcx*8]
    cmp     rax, r13
    je      map_v_xf
    inc     rcx
    jmp     map_v_xs
map_v_xf:
    mov     edx, [xs_to_col + rcx*4]
    mov     [thincol + r8*4], edx
    mov     r13, [vy + r8*8]
    xor     rcx, rcx
map_v_ys:
    mov     rax, [ys + rcx*8]
    cmp     rax, r13
    je      map_v_yf
    inc     rcx
    jmp     map_v_ys
map_v_yf:
    mov     edx, [ys_to_row + rcx*4]
    mov     [thinrow + r8*4], edx
    inc     r8
    jmp     map_v
map_v_done:

    ; classify edges into vertical / horizontal
    xor     r8, r8
    xor     r12, r12    ; ve count
    xor     r13, r13    ; he count
gen_edges:
    cmp     r8, [n_v]
    jge     gen_edges_done
    mov     r9, r8
    inc     r9
    cmp     r9, [n_v]
    jne     ge_nowrap
    xor     r9, r9
ge_nowrap:
    mov     r10, [vx + r8*8]
    mov     r11, [vx + r9*8]
    cmp     r10, r11
    je      ge_vert
    mov     rax, [vy + r8*8]
    mov     [hey + r13*8], rax
    mov     rcx, r10
    mov     rdx, r11
    cmp     rcx, rdx
    jle     ge_h_ok
    xchg    rcx, rdx
ge_h_ok:
    mov     [hexlo + r13*8], rcx
    mov     [hexhi + r13*8], rdx
    inc     r13
    jmp     ge_next
ge_vert:
    mov     [vex + r12*8], r10
    mov     rcx, [vy + r8*8]
    mov     rdx, [vy + r9*8]
    cmp     rcx, rdx
    jle     ge_v_ok
    xchg    rcx, rdx
ge_v_ok:
    mov     [veylo + r12*8], rcx
    mov     [veyhi + r12*8], rdx
    inc     r12
ge_next:
    inc     r8
    jmp     gen_edges
gen_edges_done:
    mov     [ve_cnt], r12
    mov     [he_cnt], r13

    ; 2D prefix sum of unfilled cells
    xor     r15, r15    ; refined row r
pref_r:
    cmp     r15, [r_cnt]
    jge     pref_done
    mov     r13, [row_lo + r15*8]   ; py
    xor     r14, r14                ; refined col c
pref_c:
    cmp     r14, [c_cnt]
    jge     pref_c_done
    mov     rdi, [col_lo + r14*8]
    mov     rsi, r13
    call    filled
    mov     rbx, 1
    sub     rbx, rax                ; unfilled indicator

    mov     rax, r15
    imul    rax, [cp1]              ; r*cp1
    mov     rcx, rax
    add     rcx, r14
    add     rcx, 1
    mov     edx, [pref + rcx*4]     ; P[r][c+1]
    mov     rcx, rax
    add     rcx, r14
    mov     r8d, [pref + rcx*4]     ; P[r][c]
    mov     rcx, rax
    add     rcx, [cp1]
    mov     r9, rcx                 ; (r+1)*cp1
    add     rcx, r14
    mov     r10d, [pref + rcx*4]    ; P[r+1][c]
    mov     eax, ebx
    add     eax, edx
    add     eax, r10d
    sub     eax, r8d
    mov     rcx, r9
    add     rcx, r14
    add     rcx, 1
    mov     [pref + rcx*4], eax     ; P[r+1][c+1]
    inc     r14
    jmp     pref_c
pref_c_done:
    inc     r15
    jmp     pref_r
pref_done:

    ; all pairs: part 1 = max area, part 2 = max area fully inside
    mov     qword [best1], 0
    mov     qword [best2], 0
    xor     r8, r8
pair_i:
    cmp     r8, [n_v]
    jge     pair_done
    mov     r12d, [thincol + r8*4]
    mov     r13d, [thinrow + r8*4]
    mov     r14, [vx + r8*8]
    mov     r15, [vy + r8*8]
    lea     r9, [r8 + 1]
pair_j:
    cmp     r9, [n_v]
    jge     pair_j_done

    ; area = (|xi-xj| + 1) * (|yi-yj| + 1)
    mov     rax, r14
    sub     rax, [vx + r9*8]
    jns     .ax
    neg     rax
.ax:
    inc     rax
    mov     rbx, rax
    mov     rax, r15
    sub     rax, [vy + r9*8]
    jns     .ay
    neg     rax
.ay:
    inc     rax
    imul    rax, rbx
    cmp     rax, [best1]
    jle     .no1
    mov     [best1], rax
.no1:
    push    rax                     ; save area

    ; refined block: c1,c2 then r1,r2
    mov     eax, [thincol + r9*4]
    mov     ecx, r12d
    cmp     ecx, eax
    jle     .cc
    xchg    ecx, eax
.cc:
    mov     edi, ecx                ; c1
    mov     esi, eax                ; c2
    mov     eax, [thinrow + r9*4]
    mov     ecx, r13d
    cmp     ecx, eax
    jle     .rr
    xchg    ecx, eax
.rr:
    mov     edx, ecx                ; r1
    mov     ecx, eax                ; r2
    call    block_unf
    pop     rbx                     ; area
    test    eax, eax
    jnz     .no2                    ; contains unfilled cells
    cmp     rbx, [best2]
    jle     .no2
    mov     [best2], rbx
.no2:
    inc     r9
    jmp     pair_j
pair_j_done:
    inc     r8
    jmp     pair_i
pair_done:

print_results:
    mov     rcx, label1
    call    print_string
    mov     rax, [best1]
    call    print_int64
    call    print_newline

    mov     rcx, label2
    call    print_string
    mov     rax, [best2]
    call    print_int64
    call    print_newline

    mov     rax, SYS_EXIT
    xor     rdi, rdi
    syscall

; filled: is tile (RDI=px, RSI=py) red or green (inside or on the loop)?
;   Output: RAX = 1 if filled, else 0. Clobbers RAX, RCX, RDX, R10, R11.
filled:
    xor     ecx, ecx    ; on-edge flag
    xor     r11, r11    ; crossing count
    xor     r10, r10    ; edge index
.v_loop:
    cmp     r10, [ve_cnt]
    jge     .v_done
    mov     rax, [vex + r10*8]
    cmp     rax, rdi
    jne     .v_cross
    mov     rdx, [veylo + r10*8]
    cmp     rsi, rdx
    jl      .v_cross
    mov     rdx, [veyhi + r10*8]
    cmp     rsi, rdx
    jg      .v_cross
    mov     ecx, 1      ; on a vertical edge
.v_cross:
    mov     rax, [vex + r10*8]
    cmp     rax, rdi
    jle     .v_next
    mov     rdx, [veylo + r10*8]
    cmp     rsi, rdx
    jl      .v_next
    mov     rdx, [veyhi + r10*8]
    cmp     rsi, rdx
    jge     .v_next
    inc     r11
.v_next:
    inc     r10
    jmp     .v_loop
.v_done:
    test    ecx, ecx
    jnz     .yes
    xor     r10, r10
.h_loop:
    cmp     r10, [he_cnt]
    jge     .h_done
    mov     rax, [hey + r10*8]
    cmp     rax, rsi
    jne     .h_next
    mov     rdx, [hexlo + r10*8]
    cmp     rdi, rdx
    jl      .h_next
    mov     rdx, [hexhi + r10*8]
    cmp     rdi, rdx
    jg      .h_next
    jmp     .yes
.h_next:
    inc     r10
    jmp     .h_loop
.h_done:
    mov     rax, r11
    and     rax, 1
    ret
.yes:
    mov     rax, 1
    ret

; block_unf: count of unfilled refined cells in [c1,c2] x [r1,r2].
;   In: RDI=c1, RSI=c2, RDX=r1, RCX=r2. Out: EAX. Clobbers RAX, R10, R11.
block_unf:
    mov     r10, rcx
    inc     r10
    imul    r10, [cp1]          ; (r2+1)*cp1
    mov     r11, r10
    add     r11, rsi
    add     r11, 1
    mov     eax, [pref + r11*4] ; A
    mov     r11, r10
    add     r11, rdi
    sub     eax, [pref + r11*4] ; - C
    mov     r10, rdx
    imul    r10, [cp1]          ; r1*cp1
    mov     r11, r10
    add     r11, rsi
    add     r11, 1
    sub     eax, [pref + r11*4] ; - B
    mov     r11, r10
    add     r11, rdi
    add     eax, [pref + r11*4] ; + D
    ret

; sort_q: insertion sort of qword array RDI[0..RSI-1] ascending.
;   Clobbers RAX, RDX, R8, R9, R10.
sort_q:
    mov     r8, 1
.i:
    cmp     r8, rsi
    jge     .done
    mov     r10, [rdi + r8*8]
    mov     r9, r8
    dec     r9
.j:
    cmp     r9, 0
    jl      .place
    mov     rax, [rdi + r9*8]
    cmp     rax, r10
    jle     .place
    mov     rdx, r9
    inc     rdx
    mov     [rdi + rdx*8], rax
    dec     r9
    jmp     .j
.place:
    mov     rdx, r9
    inc     rdx
    mov     [rdi + rdx*8], r10
    inc     r8
    jmp     .i
.done:
    ret

; dedup_q: remove consecutive duplicates in sorted RDI[0..RSI-1].
;   Out: RAX = new length. Clobbers RAX, RCX, RDX, R8.
dedup_q:
    xor     rax, rax
    xor     rcx, rcx
.loop:
    cmp     rcx, rsi
    jge     .done
    test    rax, rax
    jz      .keep
    mov     rdx, [rdi + rcx*8]
    mov     r8, rax
    dec     r8
    cmp     rdx, [rdi + r8*8]
    je      .skip
.keep:
    mov     rdx, [rdi + rcx*8]
    mov     [rdi + rax*8], rdx
    inc     rax
.skip:
    inc     rcx
    jmp     .loop
.done:
    ret