--- 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