Advent of Code 2024 Day 18

from pathlib import Path
from collections import deque


def parse(inp: str) -> list[complex]:
    return [
        complex(int(c[0]), int(c[1]))
        for row in inp.splitlines()
        if (c := row.split(","))
    ]


def part1(points: list[complex], number: int, width: int) -> int:
    corrupted = set(points[:number])
    good = set(
        complex(x, y)
        for y in range(width)
        for x in range(width)
        if complex(x, y) not in corrupted
    )
    start = 0 + 0j
    end = complex(width - 1, width - 1)
    points: deque[tuple[complex, int]] = deque([(start, 0)])
    path: dict[complex, int] = {}
    while points:
        p, cost = points.popleft()
        if p in path and cost <= path[p]:
            continue
        path[p] = cost
        points.extend(
            (q, cost + 1)
            for q in (p + 1, p - 1, p + 1j, p - 1j)
            if q in good and q not in path
        )
    return path[end] if end in path else None


TEST = parse(Path("input/day18-test.txt").read_text())
assert part1(TEST, 12, 7) == 22

INPUT = parse(Path("input/day18.txt").read_text())
part1_total = part1(INPUT, 1024, 71)
print(f"{part1_total=:,}")


def part2(points: list[complex], number: int, width: int) -> str:
    lo, hi = number, len(points)
    while lo < hi:
        n = (lo + hi) // 2 + 1
        distance = part1(points, n, width)
        if distance is None:
            hi = n - 1
        else:
            lo = n
    p = points[lo]
    return f"{int(p.real)},{int(p.imag)}"


assert part2(TEST, 12, 7) == "6,1"
print("part2:", part2(INPUT, 1024, 71))  # 24,30