diff options
| -rw-r--r-- | AoC2022/17/solver.lisp | 65 |
1 files changed, 35 insertions, 30 deletions
diff --git a/AoC2022/17/solver.lisp b/AoC2022/17/solver.lisp index b84807c..90a8b0c 100644 --- a/AoC2022/17/solver.lisp +++ b/AoC2022/17/solver.lisp @@ -100,44 +100,22 @@ next-shift) (declare (type fixnum posible-high)) (let ((new-high (max highpoint posible-high))) - (vector-push new-high raise-history) - (solver (1- drops-left) new-high raise-history + (solver (1- drops-left) new-high (cons new-high raise-history) ;; new-obstacles (if (zerop (mod drops-left 100)) ;; arbitrarily chop list (subseq new-obstacles 0 (min 128 (length new-obstacles))) new-obstacles) next-rock next-shift))))) -(fiveam:test solutions - (fiveam:is - (= 3068 (solver 2022 0 nil (gen-object *rocks*) (gen-object (uiop:read-file-line "eg-in"))))) - (fiveam:is - (= 3141 (solver 2022 0 nil (gen-object *rocks*) (gen-object (uiop:read-file-line "input")))))) - -;; (print (solver 1000000000000 0 nil (gen-object *rocks*) (gen-object (uiop:read-file-line "eg-in")))) - -(length (uiop:read-file-line "eg-in")) - -(let ((drops 2065)) - (multiple-value-bind (hi hist) (solver drops 0 (make-array drops :initial-element 0 :fill-pointer 1) nil (gen-object *rocks*) (gen-object (uiop:read-file-line "eg-in"))) - (length hi) - (find-period hi 620))) -(+ 22 37) -;; (require :sb-sprof) -;; (sb-sprof::start-profiling) -;; (sb-sprof:report :type :flat) (defun occurrences (lst) (let ((table (make-hash-table :test #'eq))) (loop for e in lst do (incf (gethash e table 0))) (loop for k being the hash-key of table using (hash-value v) collect (cons k v)))) -(* 59 35) -(length '(60 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 - 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 - 53 53 53 53 53 53 53 53 53 )) + (defun find-period (history max-window) - (let* ((len (1- (length history)))) + (let ((len (1- (length history)))) (loop for size from 1 to max-window for raises = (loop for start from 0 to len by size @@ -146,9 +124,36 @@ ;; collect (reduce #'+ (subseq history start (min end len))) ) for periods = (occurrences raises) - when (<= (length periods) 3) - collect (list size periods raises) - ;; finally (return (list size periods raises)) + until (<= (length periods) 3) + finally (return (values size periods))))) + +(defun height-reached (max-drops history max-window) + (multiple-value-bind (period frequencies) (find-period history max-window) + (destructuring-bind (block-height . _) (find-if (lambda (f) (< 1 (cdr f))) frequencies) + (declare (ignore _)) + (multiple-value-bind (cycles left) (floor max-drops period) + (let ((offset (aref history period)) + (remaining (- (aref history (+ left period)) (aref history period)))) + (+ offset (* (1- cycles) block-height) remaining)))))) - ;; collect (list size (length periods) periods) - ))) +(fiveam:test solutions + ;; part 1 + (fiveam:is + (= 3068 (car (solver 2022 0 '(0) nil (gen-object *rocks*) (gen-object (uiop:read-file-line "eg-in")))))) + (fiveam:is + (= 3141 (car (solver 2022 0 '(0) nil (gen-object *rocks*) (gen-object (uiop:read-file-line "input")))))) + + ;; part 2 + (let* ((drops 1000000000000) + (quick-run 10000) + (max-period-window 3620) + (history-eg (nreverse (solver quick-run 0 '(0) nil (gen-object *rocks*) + (gen-object (uiop:read-file-line "eg-in"))))) + (history-my (nreverse (solver quick-run 0 '(0) nil (gen-object *rocks*) + (gen-object (uiop:read-file-line "input")))))) + (fiveam:is (= 1514285714288 + (height-reached drops (make-array (length history-eg) :initial-contents history-eg) + max-period-window))) + (fiveam:is (= 1561739130391 + (height-reached drops (make-array (length history-my) :initial-contents history-my) + max-period-window))))) |