summaryrefslogtreecommitdiff
path: root/18_2024.py
diff options
context:
space:
mode:
Diffstat (limited to '18_2024.py')
-rw-r--r--18_2024.py32
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