path: root/aoc-2025/day3.asm

; Advent of Code 2025 - Day 3

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

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

    newline   db 10

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

section .bss
    buffer       resb 4096
    line_buffer   resb 65536
    line_len      resd 1

    sum1         resq 1
    sum2         resq 1

    work_digits   resb 64  ; stack for greedy subsequence
    number_buffer resb 32  ; for printing

section .text

_start:
    mov     rax, SYS_OPEN
    mov     rdi, input_path
    mov     rsi, O_RDONLY
    xor     rdx, rdx
    syscall

    mov     r12, rax  ; fd
    mov     dword [line_len], 0

read_loop:
    mov     rax, SYS_READ
    mov     rdi, r12
    mov     rsi, buffer
    mov     rdx, 4096
    syscall

    cmp     rax, 0
    jle     eof

    mov     rdi, buffer
    mov     rbp, rax

scan_chunk:
    cmp     rbp, 0
    je      read_loop

    mov     al, [rdi]

    cmp     al, 13
    je      skip_cr

    cmp     al, 10
    je      end_line

    mov     edx, [line_len]
    cmp     edx, 65535
    jae     skip_store
    mov     [line_buffer+rdx], al
    inc     edx
    mov     [line_len], edx

skip_store:
    inc     rdi
    dec     rbp
    jmp     scan_chunk

skip_cr:
    inc     rdi
    dec     rbp
    jmp     scan_chunk

end_line:
    mov     edx, [line_len]
    mov     byte [line_buffer+edx], 0

    cmp     edx, 0
    je      clear_line

    push    rdi
    mov     rsi, line_buffer
    call    handle_line
    pop     rdi

clear_line:
    mov     dword [line_len], 0
    inc     rdi
    dec     rbp
    jmp     scan_chunk

eof:
    ; possible last partial line
    mov     edx, [line_len]
    cmp     edx, 0
    jle     print_results

    mov     byte [line_buffer+edx], 0
    mov     rsi, line_buffer
    call    handle_line

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

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

    mov     rax, SYS_CLOSE
    mov     rdi, r12
    syscall

    mov     rax, SYS_EXIT
    xor     rdi, rdi
    syscall

handle_line:
    mov     rdi, rsi
    xor     ecx, ecx  ; ECX = 0
.length_loop:
    mov     al, [rdi+rcx]
    cmp     al, 0
    je      .length_done
    inc     ecx
    jmp     .length_loop
.length_done:
    mov     r15d, ecx  ; r15d = n

    ; part 1: k = 2
    mov     ecx, r15d      ; ECX = n
    mov     edi, 2         ; K = 2
    call    get_max_for_k  ; RAX = best 2-digit value
    add     qword [sum1], rax

    ; part 2: k = 12, only if n >= 12
    cmp     r15d, 12
    jl      .skip_part2

    mov     ecx, r15d
    mov     edi, 12
    call    get_max_for_k  ; RAX = best 12-digit value
    add     qword [sum2], rax

.skip_part2:
    ret

; Greedy lexicographically largest subsequence of length K
;
; Input:
;   RSI -> digits string
;   ECX = n (length)
;   EDI = k
; Output:
;   RAX = numeric value of chosen k digits
; Clobbers: R8..R11, EAX, EDX
get_max_for_k:
    ; drops_remaining = n - k
    mov     eax, ecx
    sub     eax, edi
    mov     r8d, eax  ; r8d = drops

    xor     r9d, r9d    ; r9d = stack_size
    xor     r10d, r10d  ; r10d = i

.loop:
    cmp     r10d, ecx
    jge     .after_input

    ; current digit in AL
    mov     r11, r10
    mov     al, [rsi + r11]

.pop:
    cmp     r9d, 0
    jle     .push
    cmp     r8d, 0
    jle     .push

    mov     edx, r9d
    dec     edx
    mov     r11d, edx
    mov     bl, [work_digits + r11]

    cmp     bl, al
    jge     .push

    dec     r9d
    dec     r8d
    jmp     .pop
.push:
    mov     r11d, r9d
    mov     [work_digits + r11], al
    inc     r9d
    inc     r10d
    jmp     .loop

.after_input:
    ; trim if stack_size > k
.trim:
    cmp     r9d, edi
    jle     .convert
    dec     r9d
    jmp     .trim
.convert:
    xor     rax, rax
    xor     r11d, r11d
.convert_loop:
    cmp     r11d, edi
    jge     .done

    mov     rdx, r11
    mov     dl, [work_digits + rdx]
    sub     dl, '0'
    movzx   rdx, dl

    imul    rax, rax, 10
    add     rax, rdx

    inc     r11d
    jmp     .convert_loop
.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