diff options
Diffstat (limited to 'AoC2023')
| -rw-r--r-- | AoC2023/day21/solver.lisp | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/AoC2023/day21/solver.lisp b/AoC2023/day21/solver.lisp index 05c4c74..a120be0 100644 --- a/AoC2023/day21/solver.lisp +++ b/AoC2023/day21/solver.lisp @@ -50,3 +50,72 @@ (test solutions (is (= 16 (solver1 (uiop:read-file-lines "eg-in") 6))) (is (= 3574 (solver1 (uiop:read-file-lines "input") 64)))) + +(defun solver2 (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) + + (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)) + (not (eq #\# (aref field (mod nr rows) (mod nc cols))))) + do (setf (gethash new-pos visited) (1- steps-left)) + (push (cons (1- steps-left) new-pos) pending)))) + (hash-table-count end-positions))) + +(solver2 (uiop:read-file-lines "eg-in") 6) +(solver2 (uiop:read-file-lines "eg-in") 10) +(solver2 (uiop:read-file-lines "eg-in") 50) +(solver2 (uiop:read-file-lines "eg-in") 100) +;; (time (solver2 (uiop:read-file-lines "eg-in") 500)) + +(defun solve-part2 () + (let ((x 202300)) + (multiple-value-bind (a b c) + (solve-quadratic 3719 33190 91987) + (+ (* a x x) (* b x) c)))) + +(defun solve-quadratic (r-one r-two r-three) + ;; The covered area grows proportional to the square of steps taken. + ;; The requested numbers of steps (= 26501365 (+ (* 202300 131) 65)) + ;; The function that takes to the the edge of the field g(x) = 65 + x * 131 + ;; The standard quadratic function q(x) = a*x^2 + b*x + c + ;; r₁ = q o g (0) = c + ;; r₂ = q o g (1) = a + b + c + ;; r₃ = q o g (2) = 4a + 2b + c + ;; + ;; solving is simple + ;; a = (r₃ - 2r₂ + r₁) / 2 + ;; b = (4r₂ - 3r₁ - r₃) / 2 + ;; c = r₁ + (values (/ (+ (- r-three (* 2 r-two)) + r-one) + 2) + (/ (- (* 4 r-two) (* 3 r-one) r-three) 2) + r-one)) + +(test sols + (loop for steps in (list 65 (+ 65 131) (+ 65 (* 131 2))) + for result in '(3719 33190 91987) + do (is (= result (solver2 (uiop:read-file-lines "input") steps)))) + (is (= 600090522932119 (solve-part2)))) |