commit ce65cacb7ef7342f884331b4d818e71545285496
from: Lukas Henkel <lh@entf.net>
date: Fri Dec 20 18:00:39 2024 UTC

Simplify pathfinding

BFS is not actually needed

commit - 40d0e7fa0bd499411078dea1a651ddb2d286e9a0
commit + ce65cacb7ef7342f884331b4d818e71545285496
blob - f31f9c2af34456030b37c79241424629c2ab91c4
blob + 90f0475c5c3d9ea7d0c05076d3ee27df5980588d
--- src/day-20.lisp
+++ src/day-20.lisp
@@ -19,25 +19,22 @@
                         do (setf end pos))
         finally (return (values start end))))
 
-(defun bfs (map start end)
+(defun find-steps (map start end)
   (loop with width = (input-map-width map)
         with height = (input-map-height map)
-        with queue = (make-queue :simple-queue)
-        with visited = (make-hash-table :test #'equal)
-        initially (qpush queue (list start (list start)))
-                  (setf (gethash start visited) t)
-        for (pos steps) = (qpop queue)
-        when (null pos)
-          do (return nil)
+        with pos = start
+        with last = nil
+        with steps = nil
+        do (push pos steps)
         when (equal pos end)
           do (return (nreverse steps))
-        do (loop for dir in *directions*
-                 for next = (point+ pos dir)
-                 when (and (point-in-bounds-p next width height)
-                           (not (gethash next visited))
-                           (char/= (map-cell map next) #\#))
-                   do (qpush queue (list next (cons next steps)))
-                      (setf (gethash next visited) t))))
+        do (psetf last pos
+                  pos (loop for dir in *directions*
+                            for next = (point+ pos dir)
+                            when (and (point-in-bounds-p next width height)
+                                      (not (equal last next))
+                                      (char/= (map-cell map next) #\#))
+                              do (return next)))))
 
 (defun count-cheats (steps threshold)
   (let ((cache (make-hash-table :test #'equal)))
@@ -64,4 +61,4 @@
   (let ((map (make-map input)))
     (multiple-value-bind (start end)
         (find-start-end map)
-      (count-cheats (bfs map start end) 100))))
+      (count-cheats (find-steps map start end) 100))))