diff options
Diffstat (limited to 'AoC2023')
| -rw-r--r-- | AoC2023/day21/solver.lisp | 70 |
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)))) |