aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorOscar Najera <hi@oscarnajera.com>2023-01-06 21:09:36 +0100
committerOscar Najera <hi@oscarnajera.com>2023-01-06 21:10:31 +0100
commitc37acab5a83d7b2e2d06bf7a258c2a053e0fc196 (patch)
tree10e16741ba2cc2455b3b3002f46718a83c683d80
parent5c9f0cd12ae2099dd730442ab8983ef17c44bb1e (diff)
downloadscratch-c37acab5a83d7b2e2d06bf7a258c2a053e0fc196.tar.gz
scratch-c37acab5a83d7b2e2d06bf7a258c2a053e0fc196.tar.bz2
scratch-c37acab5a83d7b2e2d06bf7a258c2a053e0fc196.zip
Day 17 part 2
There is no better optimization that calculating less
-rw-r--r--AoC2022/17/solver.lisp65
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)))))