18.py

from collections.abc import Generator
from heapq import heappop, heappush

with open("../18.txt") as f:
    incoming = [(int(y), int(x)) for x, y in (line.strip().split(",") for line in f)]

space = [[False] * 71 for _ in range(71)]
# space = [[False] * 7 for _ in range(7)]

for y, x in incoming[:1024]:
    # for y, x in incoming[:12]:
    space[y][x] = True


def manhattan(coord: tuple[int, int]) -> int:
    return 70 - coord[0] + 70 - coord[1]
    # return 6 - coord[0] + 6 - coord[1]


def neighbors(coord: tuple[int, int]) -> Generator[tuple[int, int]]:
    y, x = coord
    if y - 1 >= 0 and not space[y - 1][x]:
        yield y - 1, x
    if x + 1 <= 70 and not space[y][x + 1]:
        # if x + 1 <= 6 and not space[y][x + 1]:
        yield y, x + 1
    if y + 1 <= 70 and not space[y + 1][x]:
        # if y + 1 <= 6 and not space[y + 1][x]:
        yield y + 1, x
    if x - 1 >= 0 and not space[y][x - 1]:
        yield y, x - 1


def a_star() -> set[tuple[int, int]]:
    to_check = [(manhattan((0, 0)), (0, 0))]
    prev = {}
    best_path = {(0, 0): 0}
    goal = (70, 70)
    # goal = (6, 6)

    while to_check:
        guess, coord = heappop(to_check)
        if coord == goal:
            break

        for neighbor in neighbors(coord):
            maybe_best = best_path[coord] + 1
            if (cur_best := best_path.get(neighbor)) is None or maybe_best < cur_best:
                prev[neighbor] = coord
                best_path[neighbor] = maybe_best
                heappush(to_check, (maybe_best + manhattan(neighbor), neighbor))
    else:
        raise ValueError

    node = (70, 70)
    # node = (6, 6)
    path = set()
    while node in prev:
        path.add(node)
        node = prev[node]
    return path


path = a_star()
print(len(path))

for byte in incoming[1024:]:
    # for byte in incoming[12:]:
    space[byte[0]][byte[1]] = True
    if byte not in path:
        continue
    try:
        path = a_star()
    except ValueError:
        print(f"{byte[1]},{byte[0]}")
        break

# space2 = [["#" if x else "." for x in row] for row in space]
# for y, x in path:
#    space2[y][x] = "!"
# space2[byte[0]][byte[1]] = "%"
# print("\n".join("".join(row) for row in space2))