diff options
Diffstat (limited to '18_2024.py')
-rw-r--r-- | 18_2024.py | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/18_2024.py b/18_2024.py new file mode 100644 index 0000000..1fb5a62 --- /dev/null +++ b/18_2024.py @@ -0,0 +1,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 |