From 05c2d1627fdbd28dc5986f9e057773350b3c6625 Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Sat, 24 Dec 2022 12:55:39 +0100
Subject: day 24 part 2

almost a minute of runtime, gee golly
---
 22.24/main.py | 24 ++++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/22.24/main.py b/22.24/main.py
index 49fb875..bd348a0 100644
--- a/22.24/main.py
+++ b/22.24/main.py
@@ -16,7 +16,7 @@ def tdir(f):
 
 data = stdin.readlines()
 start = (data[0].index('.') - 1, -1)
-end = (data[-1].index('.') - 1, len(data) - 3)
+end = (data[-1].index('.') - 1, len(data) - 2)
 data = [l.strip()[1:-1] for l in data[1:-1]]
 w = len(data[0])
 h = len(data)
@@ -32,6 +32,7 @@ for y, line in enumerate(data):
 
 def coll(x, y, t):
     if (x, y) == start: return False
+    if (x, y) == end: return False
     if not 0 <= x < w: return True
     if not 0 <= y < h: return True
     for d in range(4):
@@ -41,20 +42,31 @@ def coll(x, y, t):
     return False
 
 def search():
-    cur = {(start, 0)}
+    cur = {(start, 0, 0)}
     frontier = set()
+    visited = set(cur)
     while True:
-        for bv, t in cur:
+        for bv, t, gid 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:
+                    new = None
+                    if v == end and gid == 0:
+                        new = (v, t+1, 1)
+                    elif v == start and gid == 1:
+                        new = (v, t+1, 2)
+                    elif v == end and gid == 2:
                         return t+1
-                    frontier.add((v, t+1))
+                    else:
+                        new = (v, t+1, gid)
+                    chk = (new[0], new[1] % cycle, new[2])
+                    if not chk in visited:
+                        visited.add(chk)
+                        frontier.add(new)
         cur = frontier
         frontier = set()
     return None
 
-print(search() + 1)
+print(search())
-- 
cgit 1.4.1-2-gfad0