aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2023
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2023')
-rw-r--r--AoC2023/day21/solver.lisp70
1 files changed, 35 insertions, 35 deletions
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))))