path: root/aoc-2025/day12.asm

; Advent of Code 2025 - Day 12

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 GRID_SIZE  4096          ; regions are at most 50x50

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

    newline    db 10

    label1     db "Part 1: ", 0

section .bss
    raw           resb RAW_SIZE

    base_r        resd (6 * 9)         ; parsed shape cells
    base_c        resd (6 * 9)
    base_n        resq 6               ; cells per shape (also its area cost)

    odr           resd (6 * 8 * 9)     ; orientation cell offsets from anchor
    odc           resd (6 * 8 * 9)
    oncells       resq (6 * 8)

    tr            resd 9               ; scratch for orientation building
    tc            resd 9

    grid          resb GRID_SIZE
    remaining     resq 6
    counts        resq 6

    raw_len       resq 1
    cursor        resq 1
    pend          resq 1
    cur_shape     resq 1
    shape_row     resq 1
    orients_done  resq 1
    rW            resq 1
    rL            resq 1
    area          resq 1
    left          resq 1
    count_feasible 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 shapes and regions
    lea     rsi, [raw]
    mov     rax, [raw_len]
    lea     rax, [raw + rax]
    mov     [pend], rax
    mov     qword [cur_shape], 0
    mov     qword [orients_done], 0
pline:
    cmp     rsi, [pend]
    jae     pdone
    mov     al, [rsi]
    cmp     al, 10
    je      pskip
    cmp     al, 13
    je      pskip
    cmp     al, ' '
    je      pskip
    cmp     al, '0'
    jl      maybe_grid
    cmp     al, '9'
    jg      maybe_grid
    ; a number begins the line
    call    parse_num
    mov     r10, rax
    mov     al, [rsi]
    cmp     al, 'x'
    je      region_line
    ; shape header "N:"
    inc     rsi
    mov     [cur_shape], r10
    mov     qword [base_n + r10*8], 0
    mov     qword [shape_row], 0
    jmp     eol

region_line:
    cmp     qword [orients_done], 0
    jne     .have
    mov     [cursor], rsi
    call    gen_orients
    mov     rsi, [cursor]
    mov     qword [orients_done], 1
.have:
    inc     rsi                 ; skip 'x'
    call    parse_num
    mov     r11, rax            ; L
.find_colon:
    mov     al, [rsi]
    inc     rsi
    cmp     al, ':'
    jne     .find_colon
    xor     rcx, rcx
.rcounts:
    cmp     rcx, 6
    jge     .rcounts_done
.rsp:
    mov     al, [rsi]
    cmp     al, ' '
    jne     .rsp_done
    inc     rsi
    jmp     .rsp
.rsp_done:
    call    parse_num
    mov     [counts + rcx*8], rax
    inc     rcx
    jmp     .rcounts
.rcounts_done:
    mov     [cursor], rsi
    mov     rdi, r10            ; W
    mov     rsi, r11            ; L
    call    solve_region
    mov     rsi, [cursor]
    jmp     eol

maybe_grid:
    cmp     al, '#'
    je      grid_row
    cmp     al, '.'
    je      grid_row
    inc     rsi
    jmp     pline
grid_row:
    mov     r10, [cur_shape]
    mov     r11, [shape_row]
    xor     rcx, rcx            ; column
.cell:
    mov     al, [rsi]
    cmp     al, '#'
    je      .hash
    cmp     al, '.'
    je      .dot
    jmp     .row_done
.hash:
    mov     rax, r10
    imul    rax, 9
    add     rax, [base_n + r10*8]
    mov     edx, r11d
    mov     [base_r + rax*4], edx
    mov     edx, ecx
    mov     [base_c + rax*4], edx
    inc     qword [base_n + r10*8]
.dot:
    inc     rcx
    inc     rsi
    jmp     .cell
.row_done:
    inc     qword [shape_row]
    jmp     eol

eol:
    cmp     rsi, [pend]
    jae     pdone
    mov     al, [rsi]
    inc     rsi
    cmp     al, 10
    jne     eol
    jmp     pline
pskip:
    inc     rsi
    jmp     pline
pdone:

    mov     rcx, label1
    call    print_string
    mov     rax, [count_feasible]
    call    print_int64
    call    print_newline

    mov     rax, SYS_EXIT
    xor     rdi, rdi
    syscall

; parse_num: read decimal at [RSI], advancing RSI. Clobbers RAX, RDX.
parse_num:
    xor     rax, rax
.d:
    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     .d
.done:
    ret

; gen_orients: build the 8 dihedral orientations of every shape as offset lists
; anchored at their row-major-first cell.
gen_orients:
    xor     r12, r12            ; shape
.s_loop:
    cmp     r12, 6
    jge     .done
    xor     r13, r13            ; transform 0..7
.t_loop:
    cmp     r13, 8
    jge     .s_next
    mov     r14, [base_n + r12*8]
    xor     rcx, rcx
.k_loop:
    cmp     rcx, r14
    jge     .k_done
    mov     rax, r12
    imul    rax, 9
    add     rax, rcx
    movsxd  r8, dword [base_r + rax*4]
    movsxd  r9, dword [base_c + rax*4]
    test    r13, 4
    jz      .noflip
    neg     r9
.noflip:
    mov     rdx, r13
    and     rdx, 3
.rot:
    test    rdx, rdx
    jz      .rot_done
    mov     r15, r8
    mov     r8, r9              ; new r = c
    mov     r9, r15
    neg     r9                  ; new c = -r
    dec     rdx
    jmp     .rot
.rot_done:
    mov     [tr + rcx*4], r8d
    mov     [tc + rcx*4], r9d
    inc     rcx
    jmp     .k_loop
.k_done:
    ; min row
    movsxd  r8, dword [tr]
    xor     rcx, rcx
.minr:
    cmp     rcx, r14
    jge     .minr_done
    movsxd  rax, dword [tr + rcx*4]
    cmp     rax, r8
    jge     .minr_next
    mov     r8, rax
.minr_next:
    inc     rcx
    jmp     .minr
.minr_done:
    ; min col among cells on the min row
    mov     r9, 0x7fffffff
    xor     rcx, rcx
.minc:
    cmp     rcx, r14
    jge     .minc_done
    movsxd  rax, dword [tr + rcx*4]
    cmp     rax, r8
    jne     .minc_next
    movsxd  rax, dword [tc + rcx*4]
    cmp     rax, r9
    jge     .minc_next
    mov     r9, rax
.minc_next:
    inc     rcx
    jmp     .minc
.minc_done:
    mov     r11, r12
    shl     r11, 3
    add     r11, r13            ; orientation index
    mov     [oncells + r11*8], r14
    xor     rcx, rcx
.store:
    cmp     rcx, r14
    jge     .store_done
    movsxd  rax, dword [tr + rcx*4]
    sub     rax, r8             ; dr
    movsxd  rdx, dword [tc + rcx*4]
    sub     rdx, r9             ; dc
    mov     rbx, r11
    imul    rbx, 9
    add     rbx, rcx
    mov     [odr + rbx*4], eax
    mov     [odc + rbx*4], edx
    inc     rcx
    jmp     .store
.store_done:
    inc     r13
    jmp     .t_loop
.s_next:
    inc     r12
    jmp     .s_loop
.done:
    ret

; solve_region(RDI=W, RSI=L): if the region can fit all presents in `counts`,
; increment count_feasible.
solve_region:
    xor     r8, r8              ; total cells
    xor     rcx, rcx
.tot:
    cmp     rcx, 6
    jge     .tot_done
    mov     rax, [counts + rcx*8]
    imul    rax, [base_n + rcx*8]
    add     r8, rax
    inc     rcx
    jmp     .tot
.tot_done:
    mov     rax, rdi
    imul    rax, rsi
    mov     [area], rax
    mov     [rW], rdi
    mov     [rL], rsi
    cmp     r8, rax
    jg      .ret                ; more cells than space -> impossible
    mov     r9, rax
    sub     r9, r8              ; empty budget

    xor     r10, r10            ; piece count
    xor     rcx, rcx
.setrem:
    cmp     rcx, 6
    jge     .setrem_done
    mov     rax, [counts + rcx*8]
    mov     [remaining + rcx*8], rax
    add     r10, rax
    inc     rcx
    jmp     .setrem
.setrem_done:
    mov     [left], r10

    mov     rcx, [area]
    lea     rdi, [grid]
    xor     al, al
    rep     stosb

    xor     rdi, rdi            ; pos = 0
    mov     rsi, r9             ; empty budget
    call    rec
    test    rax, rax
    jz      .ret
    inc     qword [count_feasible]
.ret:
    ret

; rec(RDI=pos, RSI=empty_budget) -> RAX 1 if the remaining pieces fit.
; State: R12=pos R13=eb R14=row R15=col RBX=shape RBP=orientation.
rec:
    push    rbx
    push    rbp
    push    r12
    push    r13
    push    r14
    push    r15
    mov     r12, rdi
    mov     r13, rsi
    cmp     qword [left], 0
    je      .true
.adv:
    cmp     r12, [area]
    jae     .false
    cmp     byte [grid + r12], 0
    je      .found
    inc     r12
    jmp     .adv
.found:
    mov     rax, r12
    xor     rdx, rdx
    div     qword [rW]
    mov     r14, rax            ; row
    mov     r15, rdx            ; col

    xor     rbx, rbx            ; shape
.s_loop:
    cmp     rbx, 6
    jge     .try_empty
    cmp     qword [remaining + rbx*8], 0
    je      .s_next
    xor     rbp, rbp            ; orientation
.t_loop:
    cmp     rbp, 8
    jge     .s_next
    mov     rax, rbx
    shl     rax, 3
    add     rax, rbp
    mov     r10, rax            ; orientation index
    mov     r11, [oncells + r10*8]
    ; validate placement
    xor     rcx, rcx
.chk:
    cmp     rcx, r11
    jge     .place
    mov     rax, r10
    imul    rax, 9
    add     rax, rcx
    movsxd  r8, dword [odr + rax*4]
    movsxd  r9, dword [odc + rax*4]
    add     r8, r14             ; rr
    add     r9, r15             ; cc
    cmp     r8, [rL]
    jge     .t_next
    cmp     r9, 0
    jl      .t_next
    cmp     r9, [rW]
    jge     .t_next
    mov     rax, r8
    imul    rax, [rW]
    add     rax, r9
    cmp     byte [grid + rax], 0
    jne     .t_next
    inc     rcx
    jmp     .chk
.place:
    xor     rcx, rcx
.place_k:
    cmp     rcx, r11
    jge     .place_done
    mov     rax, r10
    imul    rax, 9
    add     rax, rcx
    movsxd  r8, dword [odr + rax*4]
    movsxd  r9, dword [odc + rax*4]
    add     r8, r14
    add     r9, r15
    imul    r8, [rW]
    add     r8, r9
    mov     byte [grid + r8], 1
    inc     rcx
    jmp     .place_k
.place_done:
    dec     qword [remaining + rbx*8]
    dec     qword [left]
    mov     rdi, r12
    mov     rsi, r13
    call    rec
    test    rax, rax
    jnz     .true
    inc     qword [remaining + rbx*8]
    inc     qword [left]
    mov     rax, rbx            ; child clobbered r10/r11 - rebuild them
    shl     rax, 3
    add     rax, rbp
    mov     r10, rax
    mov     r11, [oncells + r10*8]
    xor     rcx, rcx
.unplace_k:
    cmp     rcx, r11
    jge     .unplace_done
    mov     rax, r10
    imul    rax, 9
    add     rax, rcx
    movsxd  r8, dword [odr + rax*4]
    movsxd  r9, dword [odc + rax*4]
    add     r8, r14
    add     r9, r15
    imul    r8, [rW]
    add     r8, r9
    mov     byte [grid + r8], 0
    inc     rcx
    jmp     .unplace_k
.unplace_done:
.t_next:
    inc     rbp
    jmp     .t_loop
.s_next:
    inc     rbx
    jmp     .s_loop
.try_empty:
    test    r13, r13
    jz      .false
    mov     byte [grid + r12], 1
    mov     rdi, r12
    mov     rsi, r13
    dec     rsi
    call    rec
    test    rax, rax
    jnz     .true
    mov     byte [grid + r12], 0
.false:
    xor     eax, eax
    jmp     .ret
.true:
    mov     eax, 1
.ret:
    pop     r15
    pop     r14
    pop     r13
    pop     r12
    pop     rbp
    pop     rbx
    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