f08be8f420ea

--- a/src/2021/days/day-15.lisp	Wed Dec 15 19:09:20 2021 -0500
+++ b/src/2021/days/day-15.lisp	Wed Dec 15 19:32:47 2021 -0500
@@ -17,7 +17,7 @@
   (cref data to))
 
 (defun find-path (data)
-  (declare (inline astar curry)
+  (declare (inline dijkstra curry)
            (optimize (speed 3) (debug 1) (safety 1)))
   (let ((goal (complex (1- (array-dimension data 0))
                        (1- (array-dimension data 1)))))
@@ -25,8 +25,11 @@
            :neighbors (curry #'neighbors data)
            :goalp (curry #'= goal)
            :cost (curry #'cost data)
-           :heuristic (curry #'manhattan-distance goal)
-           :test #'eql)))
+           :test #'eql
+           ;; Manhattan distance is the only candidate for a heuristic, but for
+           ;; this problem it's not particularly helpful and slows things down.
+           ;; Just use a constant and degrade to Dijkstra.
+           :heuristic (constantly 0))))
 
 (defun path-cost (data path)
   (reduce #'+ (rest path) :key (curry #'cref data)))

--- a/src/utils.lisp	Wed Dec 15 19:09:20 2021 -0500
+++ b/src/utils.lisp	Wed Dec 15 19:32:47 2021 -0500
@@ -913,7 +913,8 @@
     passing to `make-hash-table`.
 
   If the heuristic function is admissable (i.e. it never overestimates the
-  remaining distance) the algorithm will find the shortest path.
+  remaining distance) the algorithm will find the shortest path.  If you don't
+  have a decent heuristic, just use `(constantly 0)` to degrade to Dijkstra.
 
   Note that `test` is required.  The only sensible default would be `eql`, but
   if you were using states that need a different predicate and forgot to pass it