aoc_2024_day_18.py

text = """5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0"""
w=7
h=7

with open('input18.txt', 'r') as f:
    text = f.read()
    w = h = 71

blocks = [tuple([int(x) for x in line.split(',')]) for line in text.splitlines()]
s = (0, 0)
e = (w-1, h-1)


def mk_map(limit):
    m = set()
    for pos in blocks[:limit]:
        m.add(pos)
    return m

def list_neighs(pos):
    x, y = pos
    if x < w-1: yield (x+1, y)
    if x > 0: yield (x-1, y)
    if y < h-1: yield (x, y+1)
    if y > 0: yield (x, y-1)

def solve(m):
    to_explore = [s]
    cost_map = {s: 0}

    while len(to_explore):
        pos = min(to_explore, key=lambda p: w-p[0] + h-p[1])
        to_explore.remove(pos)
        cost = cost_map[pos]
        for neigh in list_neighs(pos):
            if neigh in m:
                continue
            if cost + 1 < cost_map.get(neigh, 99999999):
                cost_map[neigh] = cost + 1
                to_explore.append(neigh)

    return cost_map.get(e, None)


##

print(solve(mk_map(1024)))


## bisect:

lo = 0
hi = len(blocks) - 1

while hi > lo:
    mid = (lo + hi) // 2

    res = solve(mk_map(mid))
    print(f"Try until block {mid}: {blocks[mid - 1]} -- " + ("success" if res is not None else "failure"))

    if res is None:
        hi = mid
    else:
        lo = mid + 1

print(blocks[hi - 1])