day 24 part 1

1 files changed, 60 insertions, 0 deletions

diff --git a/22.24/main.py b/22.24/main.py
new file mode 100644
index 0000000..49fb875
--- /dev/null
+++ b/22.24/main.py
@@ -0,0 +1,60 @@
+from sys import stdin
+from math import lcm
+
+def tadd(a, b):
+    return tuple(map(sum, zip(a, b)))
+
+def tmul(a, b):
+    return tuple([n*b for n in a])
+
+def tmod(a, b):
+    return tuple([a%b for (a,b) in zip(a, b)])
+
+# direction tuple
+def tdir(f):
+    return ([0, 1, 0, -1][f%4], [-1, 0, 1, 0][f%4])
+
+data = stdin.readlines()
+start = (data[0].index('.') - 1, -1)
+end = (data[-1].index('.') - 1, len(data) - 3)
+data = [l.strip()[1:-1] for l in data[1:-1]]
+w = len(data[0])
+h = len(data)
+cycle = lcm(w, h)
+
+# 0 N  1 E  2 S  3 W
+blizzards = [set() for _ in range(4)]
+for y, line in enumerate(data):
+    for x, c in enumerate(line):
+        dirs = "^>v<"
+        if c in dirs:
+            blizzards[dirs.index(c)].add((x, y))
+
+def coll(x, y, t):
+    if (x, y) == start: return False
+    if not 0 <= x < w: return True
+    if not 0 <= y < h: return True
+    for d in range(4):
+        v = tmod(tadd((x, y), tmul(tdir(d), -t)), (w, h))
+        if v in blizzards[d]:
+            return True
+    return False
+
+def search():
+    cur = {(start, 0)}
+    frontier = set()
+    while True:
+        for bv, t in cur:
+            vs = [bv]
+            for d in range(4):
+                vs.append(tadd(bv, tdir(d)))
+            for v in vs:
+                if not coll(*v, t+1):
+                    if v == end:
+                        return t+1
+                    frontier.add((v, t+1))
+        cur = frontier
+        frontier = set()
+    return None
+
+print(search() + 1)