Day 17 part 2

There is no better optimization that calculating less

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)))))