path: root/aoc-2025/day7.asm

; Advent of Code 2025 - Day 7

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   1048576
%define MAX_W      1024
%define MAX_H      1024
%define GRID_SIZE  (MAX_W * MAX_H)

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

    newline    db 10

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

section .bss
    raw           resb RAW_SIZE
    grid          resb GRID_SIZE          ; height x width, '.'-filled
    g             resq (MAX_W * MAX_H)     ; part 2 timeline counts
    cur           resb MAX_W               ; part 1 active columns (this row)
    nxt           resb MAX_W               ; part 1 active columns (next row)

    raw_len       resq 1
    width         resq 1
    height        resq 1
    srow          resq 1
    scol          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

    ; width = length of the first line
    xor     rcx, rcx
width_scan:
    cmp     rcx, [raw_len]
    jge     width_done
    mov     al, [raw + rcx]
    cmp     al, 10
    je      width_done
    cmp     al, 13
    je      width_done
    inc     rcx
    jmp     width_scan
width_done:
    mov     [width], rcx

    ; height = number of lines
    xor     rcx, rcx
    xor     r8, r8
height_scan:
    cmp     rcx, [raw_len]
    jge     height_tail
    mov     al, [raw + rcx]
    cmp     al, 10
    jne     height_next
    inc     r8
height_next:
    inc     rcx
    jmp     height_scan
height_tail:
    mov     rax, [raw_len]
    test    rax, rax
    jz      height_store
    mov     dl, [raw + rax - 1]
    cmp     dl, 10
    je      height_store
    inc     r8
height_store:
    mov     [height], r8

    ; '.'-fill the grid, then copy the raw bytes into it
    mov     rax, [height]
    imul    rax, [width]
    mov     rcx, rax
    lea     rdi, [grid]
    mov     al, '.'
    rep     stosb

    xor     r8, r8   ; raw index
    xor     r9, r9   ; row
    xor     r10, r10 ; col
fill_loop:
    cmp     r8, [raw_len]
    jge     fill_done
    mov     al, [raw + r8]
    inc     r8
    cmp     al, 10
    je      fill_newline
    cmp     al, 13
    je      fill_loop
    cmp     r10, [width]
    jge     fill_loop
    mov     rdx, r9
    imul    rdx, [width]
    add     rdx, r10
    mov     [grid + rdx], al
    inc     r10
    jmp     fill_loop
fill_newline:
    inc     r9
    xor     r10, r10
    jmp     fill_loop
fill_done:

    ; locate S
    xor     r8, r8
    mov     rax, [height]
    imul    rax, [width]
    mov     r9, rax
find_s:
    cmp     r8, r9
    jge     s_done
    mov     al, [grid + r8]
    cmp     al, 'S'
    je      s_found
    inc     r8
    jmp     find_s
s_found:
    mov     rax, r8
    xor     rdx, rdx
    div     qword [width]
    mov     [srow], rax
    mov     [scol], rdx
s_done:

    ; part 1: flood a set of active columns, counting splitter hits
    lea     rdi, [cur]
    mov     rcx, MAX_W
    xor     al, al
    rep     stosb
    mov     rax, [scol]
    mov     byte [cur + rax], 1

    xor     r15, r15   ; row
p1_row:
    cmp     r15, [height]
    jge     p1_done
    lea     rdi, [nxt]
    mov     rcx, MAX_W
    xor     al, al
    rep     stosb

    mov     rax, r15
    imul    rax, [width]
    mov     r14, rax   ; row offset
    xor     r13, r13   ; col
    xor     r12, r12   ; any beam alive?
p1_col:
    cmp     r13, [width]
    jge     p1_col_done
    mov     al, [cur + r13]
    test    al, al
    jz      p1_next
    mov     rdx, r14
    add     rdx, r13
    mov     al, [grid + rdx]
    cmp     al, '^'
    jne     p1_pass
    inc     qword [part1]
    mov     rbx, r13   ; left neighbor
    test    rbx, rbx
    jz      p1_no_left
    dec     rbx
    mov     byte [nxt + rbx], 1
    mov     r12, 1
p1_no_left:
    mov     rbx, r13   ; right neighbor
    inc     rbx
    cmp     rbx, [width]
    jge     p1_no_right
    mov     byte [nxt + rbx], 1
    mov     r12, 1
p1_no_right:
    jmp     p1_next
p1_pass:
    mov     byte [nxt + r13], 1
    mov     r12, 1
p1_next:
    inc     r13
    jmp     p1_col
p1_col_done:
    lea     rsi, [nxt]
    lea     rdi, [cur]
    mov     rcx, MAX_W
    rep     movsb
    test    r12, r12
    jz      p1_done
    inc     r15
    jmp     p1_row
p1_done:

    ; part 2: bottom-up DP of timeline counts, g[r][c]
    mov     r15, [height]
    dec     r15        ; row, counting down
p2_row:
    cmp     r15, 0
    jl      p2_done
    mov     rax, r15
    imul    rax, [width]
    mov     r14, rax   ; row offset
    xor     r13, r13   ; col
p2_col:
    cmp     r13, [width]
    jge     p2_col_done
    mov     rdx, r14
    add     rdx, r13   ; idx = r*W + c
    mov     al, [grid + rdx]
    cmp     al, '^'
    je      p2_split

    ; pass straight down: g = (r+1 in grid ? g[r+1][c] : 1)
    mov     rbx, r15
    inc     rbx
    cmp     rbx, [height]
    jge     p2_pass_exit
    mov     rcx, rdx
    add     rcx, [width]
    mov     rax, [g + rcx*8]
    jmp     p2_store
p2_pass_exit:
    mov     rax, 1
    jmp     p2_store

p2_split:
    ; left child enters (r+1, c-1)
    mov     rbx, r15
    inc     rbx
    cmp     rbx, [height]
    jge     p2_left_one
    cmp     r13, 0
    jle     p2_left_one
    mov     rcx, rdx
    add     rcx, [width]
    dec     rcx
    mov     r8, [g + rcx*8]
    jmp     p2_left_done
p2_left_one:
    mov     r8, 1
p2_left_done:
    ; right child enters (r+1, c+1)
    mov     rbx, r15
    inc     rbx
    cmp     rbx, [height]
    jge     p2_right_one
    mov     rbx, r13
    inc     rbx
    cmp     rbx, [width]
    jge     p2_right_one
    mov     rcx, rdx
    add     rcx, [width]
    inc     rcx
    mov     r9, [g + rcx*8]
    jmp     p2_right_done
p2_right_one:
    mov     r9, 1
p2_right_done:
    mov     rax, r8
    add     rax, r9
p2_store:
    mov     [g + rdx*8], rax
    inc     r13
    jmp     p2_col
p2_col_done:
    dec     r15
    jmp     p2_row
p2_done:
    mov     rax, [srow]
    imul    rax, [width]
    add     rax, [scol]
    mov     rax, [g + rax*8]
    mov     [part2], rax

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

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