summaryrefslogtreecommitdiff
path: root/18_2024.py
blob: 1fb5a62500a41c63eb8a551dbacd16ffaf9083b9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import deque

input = "data/18_2024.txt"
data = open(input).read().strip()
cnt = 71
v = [["." for c in range(cnt)] for r in range(cnt)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]

for i, line in enumerate(data.split("\n")):
    x, y = [int(x) for x in line.split(",")]
    if 0 <= y < cnt and 0 <= x < cnt:
        v[y][x] = "#"
    q = deque([(0, 0, 0)])
    vis, ok = set(), False
    while q:
        d, r, c = q.popleft()
        if (r, c) == (cnt - 1, cnt - 1):
            if i == 1023:
                print(d)
            ok = True
            break
        if (r, c) in vis:
            continue
        vis.add((r, c))
        for dr, dc in dirs:
            rr = r + dr
            cc = c + dc
            if 0 <= rr < cnt and 0 <= cc < cnt and v[rr][cc] != "#":
                q.append((d + 1, rr, cc))
    if not ok:
        print(f"{x},{y}")
        break