aoc/2024/18_memspace.py

#!/usr/bin/env python3
import sys
from heapq import heappop, heappush

def shortest_path(falls):
    work = [(0, ((0, 0),))]
    dist = {(0, 0): 0}
    while work:
        length, path = heappop(work)
        x, y = path[-1]
        if dist[x, y] != length:
            continue
        if x == 70 and y == 70:
            return set(path)
        for nb in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            nx, ny = nb
            if 0 <= nx <= 70 and 0 <= ny <= 70 and nb not in falls and \
                    dist.get(nb, 1e4) > length + 1:
                dist[nb] = length + 1
                heappush(work, (length + 1, path + (nb,)))

falls = [tuple(map(int, line.split(','))) for line in sys.stdin]
cur = set(falls[:1024])
path = shortest_path(cur)
print(len(path) - 1)
for fall in falls[1024:]:
    cur.add(fall)
    if fall in path:
        path = shortest_path(cur)
        if path is None:
            print('%d,%d' % fall)
            break