From 8b859a325322960934344accc35650a68bafabd3 Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Sat, 24 Dec 2022 13:17:44 +0100
Subject: day 24 gotta go fast

---
 22.24/main.py | 71 ++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 44 insertions(+), 27 deletions(-)

diff --git a/22.24/main.py b/22.24/main.py
index bd348a0..9e5783e 100644
--- a/22.24/main.py
+++ b/22.24/main.py
@@ -1,14 +1,21 @@
 from sys import stdin
 from math import lcm
+from heapq import heappop, heappush
 
 def tadd(a, b):
-    return tuple(map(sum, zip(a, b)))
+    return (a[0] + b[0], a[1] + b[1])
+    # return tuple(map(sum, zip(a, b)))
 
 def tmul(a, b):
-    return tuple([n*b for n in a])
+    return (a[0] * b, a[1] * b)
+    # return tuple([n*b for n in a])
 
 def tmod(a, b):
-    return tuple([a%b for (a,b) in zip(a, b)])
+    return (a[0] % b[0], a[1] % b[1])
+    # return tuple([a%b for (a,b) in zip(a, b)])
+
+def tdist(a, b):
+    return abs(a[0] - b[0]) + abs(a[1] - b[1])
 
 # direction tuple
 def tdir(f):
@@ -42,31 +49,41 @@ def coll(x, y, t):
     return False
 
 def search():
-    cur = {(start, 0, 0)}
-    frontier = set()
-    visited = set(cur)
+    partOne = None
+    cur = [(0, (start, 0, 0))]
+    visited = set(cur[0][1])
+    asdf = 0
+    gid_bonus = tdist(start, end)
+    def dist(node):
+        bv, t, gid = node
+        goal = end if gid != 1 else start
+        score = 0
+        score += tdist(bv, goal)
+        score += t
+        score -= gid * gid_bonus
     while True:
-        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):
-                    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
-                    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()
+        _, node = heappop(cur)
+        bv, t, gid = node
+        vs = [bv]
+        for d in range(4):
+            vs.append(tadd(bv, tdir(d)))
+        for v in vs:
+            if not coll(*v, t+1):
+                node = None
+                if v == end and gid == 0:
+                    if not partOne: partOne = t+1
+                    node = (v, t+1, 1)
+                elif v == start and gid == 1:
+                    node = (v, t+1, 2)
+                elif v == end and gid == 2:
+                    return partOne, t+1
+                else:
+                    node = (v, t+1, gid)
+                chk = (node[0], node[1], node[2])
+                if not chk in visited:
+                    visited.add(chk)
+                    heappush(cur, (asdf, node))
+                    asdf += 1
     return None
 
 print(search())
-- 
cgit 1.4.1-2-gfad0