From e2f5b6c2d5bb67013ba1b612252781e4cd9b6fe1 Mon Sep 17 00:00:00 2001
From: Oscar Najera <hi@oscarnajera.com>
Date: Sat, 30 Dec 2023 21:39:28 +0100
Subject: [BUG FIX] LIFO Queue and visited map are adversary

The test for seen was steps-left independent. Yet the queue treats the
last suggested place first. It happens than, that places reached by
longer paths where not available when the sorter path options got a
chance. Thus the visited controls now how many steps are left, and in
the case of having more available, then the suggestion is taken.
---
 AoC2023/day21/solver.lisp | 70 +++++++++++++++++++++++------------------------
 1 file changed, 35 insertions(+), 35 deletions(-)

(limited to 'AoC2023/day21/solver.lisp')

diff --git a/AoC2023/day21/solver.lisp b/AoC2023/day21/solver.lisp
index 87c70c4..05c4c74 100644
--- a/AoC2023/day21/solver.lisp
+++ b/AoC2023/day21/solver.lisp
@@ -13,40 +13,40 @@
         (when (eq (aref field row col) #\S)
           (return-from find-start (list row col)))))))
 
-(let* ((lines
-         (uiop:read-file-lines "input"))
-       (field (make-array (list (length lines) (length (car lines)))
-                          :initial-contents lines))
-       end-positions
-       pending
-       (start (find-start field))
-       (visited (make-hash-table :test #'equal))
-       )
-  (push (cons 64 start) pending)
-  (setf (gethash start visited) t)
+(defun solver1 (lines step-count)
+  (let* ((field (make-array (list (length lines) (length (car lines)))
+                            :initial-contents lines))
+         pending
+         (end-positions (make-hash-table :test #'equal))
+         (visited (make-hash-table :test #'equal))
+         (start (find-start field)))
+    (destructuring-bind (rows cols)
+        (array-dimensions field)
 
-  (destructuring-bind (rows cols)
-      (array-dimensions field)
-    (loop while pending
-          for (steps-left row col) = (pop pending) do
-            (when (zerop (mod steps-left 2))
-              (push (list row col) end-positions))
-            (unless (zerop steps-left)
-              (loop
-                for (dr dc) in '((0 1) (0 -1) (1 0) (-1 0))
-                for nr = (+ row dr)
-                for nc = (+ col dc)
-                for new-pos = (list nr nc)
-                when (and (< -1 nr rows)
-                          (< -1 nc cols)
-                          (not (eq #\# (aref field nr nc)))
-                          (not (gethash new-pos visited)))
-                  do (setf (gethash new-pos visited) t)
-                     (push (cons (1- steps-left) new-pos) pending)))))
-  ;; (list
-  ;;  end-positions)
-  ;; (length (remove-duplicates end-positions :test #'equal))
-  (length
-   end-positions)
+      (push (cons step-count start) pending)
+      (setf (gethash start visited) step-count)
+
+      (loop while pending
+            for (steps-left row col) = (pop pending)
+            ;; an even number of steps left means it is possible
+            ;; to go and return to the place in the steps available
+            ;; Thus count to the solution.
+            when (evenp steps-left)
+              do (setf (gethash (list row col) end-positions) t)
+            unless (zerop steps-left)
+              do (loop
+                   for (dr dc) in '((-1 0) (0 -1) (1 0) (0 1))
+                   for nr = (+ row dr)
+                   for nc = (+ col dc)
+                   for new-pos = (list nr nc)
+                   when (and (< (gethash new-pos visited -1) (1- steps-left))
+                             (< -1 nr rows)
+                             (< -1 nc cols)
+                             (not (eq #\# (aref field nr nc))))
+                     do (setf (gethash new-pos visited) (1- steps-left))
+                        (push (cons (1- steps-left) new-pos) pending))))
+    (hash-table-count end-positions)))
 
-  )
+(test solutions
+  (is (= 16 (solver1 (uiop:read-file-lines "eg-in") 6)))
+  (is (= 3574 (solver1 (uiop:read-file-lines "input") 64))))
-- 
cgit v1.2.3