commit - d2acc5d04156c20564f7a69ecb395d930c192279
commit + 4f33aa74e3fc0f489f1d20fe970de7370eb84f9f
blob - a400cc67c3a5ca08ee2f743591aa96a47fa94351
blob + 4ea40c724fd5a1a5a0e28d5057d3eeb8375b80c4
--- src/day-16.lisp
+++ src/day-16.lisp
@@ -17,23 +17,22 @@
 (defun node-compare (node-a node-b)
   (< (node-cost node-a) (node-cost node-b)))
 
-(defun process-next (open-list closed-list next-position next-direction next-cost parent)
+(defun process-next (open-list node-cache closed-list next-position next-direction next-cost parent)
   (when (gethash (list next-position next-direction) closed-list)
     (return-from process-next nil))
-  (let* ((existing (queue-find open-list (lambda (existing)
-                                           (and (equal (node-position existing) next-position)
-                                                (equal (node-direction existing) next-direction)))))
-         (existing (and existing (q::node-value existing))))
+  (let* ((cache-key (list next-direction next-position))
+         (existing (gethash cache-key node-cache)))
     (if existing
         (when (<= next-cost (node-cost existing))
           (setf (node-parents existing) (if (= next-cost (node-cost existing))
                                             (cons parent (node-parents existing))
                                             (list parent))
                 (node-cost existing) next-cost))
-        (qpush open-list (make-node :position next-position
-                                    :direction next-direction
-                                    :cost next-cost
-                                    :parents (list parent))))))
+        (qpush open-list (setf (gethash cache-key node-cache)
+                               (make-node :position next-position
+                                          :direction next-direction
+                                          :cost next-cost
+                                          :parents (list parent)))))))
 
 (defun path-length (end-node)
   (loop with seen = (make-hash-table :test #'equal)
@@ -45,6 +44,7 @@
 
 (defun dijkstra (map start end)
   (loop with open-list = (make-queue :priority-queue :compare #'node-compare)
+        with node-cache = (make-hash-table :test #'equal)
         with closed-list = (make-hash-table :test #'equal)
         initially (qpush open-list (make-node :position start
                                               :direction (first *directions-clockwise*)))
@@ -59,12 +59,12 @@
                              (path-length current)))
         do (setf (gethash (list current-pos current-dir) closed-list) t)
         when (char/= (map-cell map next) #\#)
-          do (process-next open-list closed-list next current-dir (1+ current-cost) current)
-        do (process-next open-list closed-list current-pos
+          do (process-next open-list node-cache closed-list next current-dir (1+ current-cost) current)
+        do (process-next open-list node-cache closed-list current-pos
                          (cadr (member current-dir *directions-clockwise* :test #'equal))
                          (+ current-cost 1000)
                          current)
-           (process-next open-list closed-list current-pos
+           (process-next open-list node-cache closed-list current-pos
                          (cadr (member current-dir *directions-counterclockwise* :test #'equal))
                          (+ current-cost 1000)
                          current)))