aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2023
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2023')
-rw-r--r--AoC2023/day21/solver.lisp69
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))))