aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorOscar Najera <hi@oscarnajera.com>2023-01-06 15:59:33 +0100
committerOscar Najera <hi@oscarnajera.com>2023-01-06 15:59:33 +0100
commitfafd80c0c46c064aca6efe2da2eacf99df0df43a (patch)
treefcee429d618982bdb919b6db7648f84f55b8c188
parentcaaf5de9066daebfcb4bbd4a3f4953746739c225 (diff)
downloadscratch-fafd80c0c46c064aca6efe2da2eacf99df0df43a.tar.gz
scratch-fafd80c0c46c064aca6efe2da2eacf99df0df43a.tar.bz2
scratch-fafd80c0c46c064aca6efe2da2eacf99df0df43a.zip
solve day 17 part 1
-rw-r--r--AoC2022/17/eg-in1
-rw-r--r--AoC2022/17/input1
-rw-r--r--AoC2022/17/solver.lisp90
3 files changed, 92 insertions, 0 deletions
diff --git a/AoC2022/17/eg-in b/AoC2022/17/eg-in
new file mode 100644
index 0000000..97a1aa1
--- /dev/null
+++ b/AoC2022/17/eg-in
@@ -0,0 +1 @@
+>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
diff --git a/AoC2022/17/input b/AoC2022/17/input
new file mode 100644
index 0000000..5ec90a1
--- /dev/null
+++ b/AoC2022/17/input
@@ -0,0 +1 @@
+>><<<<>>><>><<>>>><<<>>><<>>><<>><>><<<>>>><<<<>>>><<<<>><<<<><<>><<<><<<<>>>><<>>>><<<<>>>><<>>>><><<<>>>><<>>>><<<<><>>>><<<>>>><<><<<>><<<<>>><<>>>><<><<>>><<>>><<<>>><<>><<><<><<>>><<<>><<<>>><>>><<<>>>><<<<><<<>>><>>>><<<>><<><<>>>><<>>><<<>>><<<><<>>>><<<<><<>>>><<>><<<<>><<<>>><><<<>>>><<<><>>><<<>>><<<>>>><<<<>>><<<<>>>><<<>><<<>><>><<<>>>><>>>><<<>><<<<><<<>>><<<<>>><<><<>>><>><<<>>>><<<>>>><>>><<<>>><<<<>>>><<<<>>>><<<<>><<<><<<<>>>><><<<>><<<<><><>>><<<<>>>><<>>><<>>><><><<<>>>><>>><<>><<><<<<><<<>>>><<<>>><>><<>>>><>>><<<>>><><<>>>><>><<>>>><<<>>><<<<>>>><<>>>><<>><<<>>>><<<>>><<<<>><<<<>>><<><<>>>><<>><>><<>>>><><>><<>>>><<>>><<>>>><<<>>>><<<>>><<<>>><<<<>>>><<<><<<>><<<><<<>><<<<>><<<>>><<<<>><<<>>>><<<<>><>><<<>>>><<>>><<<<>>>><<<<>>><<<<><<<<>>><<<<>>><<<<>>><<<<>><<>>><<<<><<<><<<<>>><<<>><<<>>><<<>>><<<<><<<<><<<<>><<>>><<<><<<><<<>>>><<<<>><<<<>>><<>><>>>><<<>><><<<><<<<>>>><<>>><<<><>><<>><>><<>>>><<>>><>>><<<>>>><<>>>><<>>><<<><<>><<<<>><>>><<<>>>><<<><<><<>><<<<><<<><>>>><<>>>><<>><<>>><><<><>>><<><>>><<>>><>><<<>>><<>>>><<<>><<<>>>><<>>><<<><<<<><<<<>>><<>>><<><<>>><<>>><<<><<<><<>>>><>><<<<>><<>>>><<>>><>>><<<>>><<>><<>><<<<>>>><<>>>><<<<>><<<<>><<<<><<<<>>>><<><<<<>>>><<<<>>><<<<>><<<>>>><<>>>><<<<>><<<>>><>>><<<<><><>><<<>>>><>>>><><<<>><<>>>><<<<>><<<<>><>>><<>>><<<<>><<<<>><<<<><<>>>><<><><<<>>>><>>><>>>><<<<><>>><<<>>><>>>><<<<>><><<<<><>>><<<>>>><<<<>>>><>>>><<<>>>><>><><<<<>>>><<<>><><<<><>>><<><<<<>><<><<<<>><<<<>>>><><<><<>>><<<<>><<<<>>><<>>><<>><>>><>>><<<>><><<><<<><<><<>>>><><<<<>><<<>>>><>><>><<<<><>><<<<><>>><<><<<<>>>><<<><<><>><><<<>>><>>>><><>>>><<<<>>><<>>><<<<>>><<>>>><<<<>>>><>>><<<<>>><>><<>>><<<>><<>><<<<>>>><><<><<<<>>><<<>>><<<>><><<<><<>>>><<<<>>><<>><<<>><<>>>><>>><<>>>><<>>><<>>><<<<>>><<<<>>><<<>><<>><<>>>><<<>><>><<<>>>><<>>>><<<><<><<>><<<<><>>><<>><<<<>>>><<<<><>><<<>><<<><><>><>>>><>><<>>><<>><<<>>>><<<<>>><<<<>><<<>><><<<<>>>><<<>>>><<<<>>><<<><<<<>><<<<>>>><<<>>><<>>><<<<><<<<>>><<<<>><<<>><<<<>>>><<<<>>>><><><<<<>>>><<>>>><<<>><<>>>><<><>>><<<>><>>>><>>>><<<>><><<<>>>><>>><<<>><<<<>><><<><><<<<>><<<>>>><<<>><><<><<<<>><<<>>><>>><>>>><<<>>>><<<<>>><<<<>><>>><<<>><<><><>><<<<>>>><>><>>>><<>>>><<>><<>>><<>><<<>><<<>>><<>>><<<<>>><<><<<<>>>><<<>><<<<><<>><<<>>>><><<<<>><<<>><>>>><<>><<<<><>>>><>>>><<>><>>>><<<<>>>><<>>><<<<><<<>>><<>><<<><<<>><<<<>>>><><<<<>>><>><>>>><>>>><<>>><<>>>><<<<><>><>>>><>>><<<<>>><<>><<<<>>>><>><>>>><<<<>>><<<<>>><<<>>><<<<>>><<<<><<<<>><<<><<>><><<<>>><<<>>><<<<>>><<<<>><<<><<<<>>><<>><<<<>><<>><>><<<<>>>><<>>>><<<<><>><><<<<>>><>>><><<>>>><>>>><>>><<<>>>><<<><<><>><<<<>><<>>><<>>><<>>>><>><<><<<>>><>>>><<<><<><<>><<<>>><<><>>>><<<<><>><<<<>>><<>>>><<>>><<>><<<>>><>>><<<<><><<<<>><<<<>><<<<>>><<<>>><<<<>>><<<><<>><>><<<<><>>>><<<>>><>><<>>><<>><<>>>><<<>>><<<<>><<<>>>><<<<>>>><>><<<<><<>><<<<><<>>>><<<><<<>><>>><<>>><<>>><<>>>><<>><<>><<<>>><<><<<><<<>>><<<><<><<<><<<><>>><<>>>><<<<>>>><<<<>>><<<><<<><<<<><<<<>>><<<>>><<><>>><<<<>><>><<><<<>>><<<>><>>><<<<>><<><<>><<<<>>><<<<>><><<<<><<<>>>><<<>><>>><<<<><>>><<<<>>><<<<>>><<<<>>><>>>><<<<><<<>>>><>>>><<<>>>><<<>>><<<<>>><<<<>><>>>><<<<>>><<<<>><>><<><><<<>>><<>><<<<><<<<>>>><<<<>>>><<<>><<<<><<<<>><<<>><<<<><<><<>><<<>><<><<<<>><>><<<<><<<>>><>>>><<<<><<>>>><<<<>>><>>>><<<<><<<<>><>><<>>><<<>><><>><<<<>>>><<>><<<><>><>>>><>><<<<>>><<>>>><>>>><<<>><<<>>>><>>><<<<><<<<>>><<<>>>><>><<>>><<<>><<<>>><<<<>>><<<>>><<>>><<<><<<<>>>><>>><<>>><>>>><<<>>>><<<<>>><<<>>>><<<<>><>>><>>>><<<>>><>>><<<<>>>><<<<>>>><<><<<>><<<>><>><>><<<<>>>><>>><>><<<>><<<><<<><<><><<<>>>><<>><<<>><><>><>>>><<>>><<<>>>><><><<><<<>>><<<><<<<>>>><<<<><><<<<>><>>><<>>><>>><>><<<>><<<<>><<>>><<<>><<>><<<<>>><>><<<>>>><<<<><<>>><<<<><<<<><<<>>><<<><>>><<>><<<>><>><>>>><<>>>><<<>>>><<<>><<<<><<<><>>>><<>>><<>>>><<<<>><<<>><>>>><<<>>>><<>>><<>><<<><<>><>>><<<><<>>><><<<<>>>><<>><<>>><<<><<<>><<<<><<<<>>><<>>><>><>>>><>><>><<>>><<>>><><<<<>><<<>><<<<>>><<>><>>><<<>>>><<>><<<><<<<>><<>><<<>>><<<>><<<>>><<<<>>><>><<>>>><<><<>><<<>>>><<<>>><>><>>><>>><<>>>><<<>>><<<<><>>>><<<<>><<>><><><<<>>><<<<><<<<>>>><<<<>><<>>><<<<>><>>><<<<>>>><<<>><<>><<>>>><>><<<<>>><><<<>>><<<>><<<><<<<>><<>>>><<<<>>><<<<>>><>><>>>><<<>><<<>>><<>>><<<<>>>><>><>><<<>>>><><<<<>><<<>><<>><><>><>>>><<>>>><<>>><<>><<<<>>><>>>><<<<><<><<<<>><<<<>>><<<<><<>>>><<>><<<<>>>><<<>>><<<>><>>>><<<<><<>>>><<>>>><<<<>>>><<>>>><<<<>>><<<>>><<<<><<>><<>>><<<>><<><<>>>><<<>><<<>>><<<>>><>>>><><>>>><<>>>><>>>><<<>>><<>><<<<><<>><<<<>>><<<<>><<<<>><<<<>><<>>><<<>>>><>><<>>>><>>>><<<<><<<>>><>>><<>>>><<<><>>><<>>><<<>><<<<><<<<>>>><<<<>>>><<<<><<><<>><<><>><<><<<<><><<<<>>><<<<>><<>>><<<>>>><<<<>>>><<<><<<<><>>><<<>>><<><><<<>><<>>>><<<<><<<><>>>><<<>><<<<>>>><<<>>><>>><<<<>>>><<<<>>><<<<>><<><<<<>>><<<>>><<<><<><<><<>>>><<><<<>>><<<<><<<><<<<>><>>><<><<><<><<><<<<>>>><<><<<>><<<<><<>>><><>>><><<><<>><<<<>><<<>><><<<>>><<<<>>><>>>><<>><<<<>><<>><<<<>>>><<<<>>><><>><<<<>><<>>>><<>>>><<<>><<><>>>><<<<>><>>>><<<>><<<<>>>><><<<>>>><<><<><>><<<<><<<<>><<>>><>>>><<<<>>><<<>>><<>><<><<>>>><>><>><<<>>><>><<><<<<><<<>>>><<<<>>>><>>>><<<>>>><>>>><<>><<<><<<<>>><>>>><<<<><<<>><<><>>>><<<><>><>>>><>>>><<>>><>>>><<>>><<<<><<>><>><>>><<><<>>><<<><<<<><<><<<<>>><<<>>><<<>><<<>>>><<<<>>><<<<><<<>>><>><>>><>><<<<>><<>>><>>><<<<>>><<<>><>>><<<><<<<>>>><<<<><>>><<<<>><<<>>><>>>><<<>>><<>>>><<>>><><><>>><<<>>><<<>><><<>>><>><<<<>><>>>><<>><<<<>>><<<><<><<>>>><<><<>>>><<<<>>>><<><<>><<>>>><>>>><>>>><<<<>>><><<<<><<<<>><<<<><<>>><>>>><<<<>><<<<>>><<<>>><<<><<<>>>><<>>><<<<>>><<>>><<<>>><<<><<<<><<>>>><<<<>>><<><<<<><<<<><><<<>><<<<><<><<<<><<<<><<><<<>><><>>><>>><<>><<<><<><>><<<<>>><<<><<<>>><<><>>>><<<<>>><<>>><><<<<>>>><<>><<><>><>><>>>><<<>>>><<><<>>>><><<<><>>><<<<>>><<<>>><<<<>>>><<>>><>><><<<><>>>><<>><>>>><<<>>>><>>><<<<>>><<<<>>>><<>><>>>><>><<<>>><<<>><>>><<>>><<><<<>>><<>>>><>><<<>>><<<<>><><<<>><>><<>>><<<<>>>><<<>>>><<<<>>><<<<><<<<>>><<<>><<<<>>>><<>>><<<><>>>><><<>><<<>>>><<>><<<>>><<><>>>><<<>><<>>>><><<<<>><<<<>>><>>>><<<<>><<<<>>>><<><<<>>>><<<>>>><<<<>>><<<>><><<><<<<>>>><<<<>><<>><<<><<<>>><><>>><<>><<<>>><><<<<>>><>><>><><<><<<><<<<>>><<<<><>>><<<>><<>><<><<<><<><>>>><<>><<>>>><<<>>>><>>>><<>>><<><<>>><<>><<<<><>>>><<<><<<>>><<<>>><<>>><<<<>>><<<<><<<<><>><<<>>><>>><>>><<<<>>><<>>>><>><<<<>>><<<<>><<<>>><<<>>><>>>><>>>><<>>><><<><<><>>>><>><<>>>><<<>><<<><<<<>>>><<>><>>><<>><>>>><<<>>><>><<><>>><<<<><<<<>>><<>><<>>>><<<><<><<<<><>><<<<>>><<<><><<<><<<><>><<>>>><<>>>><<><<>>><<>>>><>>>><<><<<>>>><<<>><<<>><<<<>>><<>>>><<<<>>>><>>><<<><<<<><<<<><><<>>>><<<<>>><>>>><<><<<>><<<>>>><<<<>>><<<<>>>><>>>><<>>>><<<<><>>>><<<<>>>><<>>>><<<<>>><<>>><<<>>>><>>><<<<>>><><<<>>><<><<<<><<<<>>>><<><>>><<><<<<>>>><<<<>>>><<<>><<<><<<<><<<><>>>><<<>>><<>>><>>><<<<><<<<><>>>><<<>><<<<>>>><<<<>><<<<>>>><<<<>>><<<>>>><<<>>><<<<><>><<<<><>>>><<<>>><<<>>><<<<><<><>>><>><<<<>>><<>>><<<<>><<><>>>><<><<>>>><<<<>><<<>>>><<>><<<><<<<>>>><>><>><<<>>>><>>><<>><<<<>>><<<><<>>>><<<<><<>>>><>><>><<<><><><<<><<><<>><<><<<<><<<<>><<<><<>>>><<><<>>>><>><<><<<<>>>><>>><<>>>><<><>>>><<<><<<<><<><>><<><<<>>><<><<<<>>><<><<<<>>><<<>>><><<<<>>>><><>>><<>>><><<<<>>><<><<>>>><<<<>><<>>>><>>>><<>>><<><<<<>><<>>>><<><<<<>><<<><>>>><<<<>>><<<<>>><<<>><<<><<<<>>><<<<>><<>>>><>>><>>>><>>><<><<<>><<>>><<>>>><<><<<>>>><>>><><<<>>>><><>>><<<<>>>><<<>>><<>><<>>><<<>>><<>>><>>>><<<>><<<<><<>><<<>>>><<<<><<>><<>>>><<<<><<<<>>>><><<>><<<>>>><<>>>><<><<<><<>><<><<><<<<><>>><<<>>><>><<<>><<<<><><>><<<<><<><<<><<<<>>>><>>>><<<<>>>><>>>><<<>>>><><<<<>>>><<>>>><<>>>><<<<><<<>>>><<<><>>><>><<<<><<<<>>><<<<>>><<>>>><><<<>><<<<>>><<>><<>>>><<<>><<<<>>>><<<<><<<<>>><<<<>><<>>><<<<><<>><<<<><>><<<><<>><<>><<><<<>><<<<>><<>>>><<>>>><>>><<<<>>><<<>><<<>>>><<<<>>>><<<<><<<<>><<<<>>>><<<>>><<<<><>><<>>>><>>>><<><<<>>>><<>>>><>>>><<>><>><<<<><<<>>><<><<<<>>><<>><<<>>><<<<>><<<>><<><><<<>>><<<>>><<>><<<<>>>><<<>>><<><<<>>>><<><>>>><>>>><>>><<<>>><>>>><<>>>><<><<<>>>><<>><<<<>>><<<<>><<<>>><<>>><<<>><<<><<<>>>><>>>><>>>><<<>>><<<><<><<<<>><<<<>>>><<<<>>><<<<><<>>>><><<<<><<<><<<<><<<<>>><>>>><<>><<<><<<<><<<<>>><<>>>><<>>>><<<>><<>>><<>>><<<<>>><<>>>><<<<>>><>>>><<<<>><<><<>>><<>>>><<>>><<<<><<><<<<>>>><<<<><<<>>><<><<<<>>>><<>>><<>>>><>><>><<<<>><<<<>>>><<<>><>>><<<<>><>>><<<>>>><<>><<<>>>><<<>>>><>><>>>><<<><<<<><<<>><>>>><>>><<>><<><<>>>><<>><<<>>><<>><<>>>><<<>>><<>>>><<><<<>>>><<>>><<<<>>>><<<>>>><<<<>>><>>>><<>><<<<>>><><<>>>><<<>><<>><<<>><>>><>>>><<<>><><>><<<>>>><<>>>><<<>>><<><<<<>><<<<>><<<><<>><>>>><<<<><<>>><<<<>>>><<<<>>>><<>>>><<<<><<<<><<<>>><>><>>>><<<<><<<>>>><>><<>><<<<>><<<>><<>><<<<>><><<>><<<>>><>>><<<<>>>><<<>><<>>><<>><<<>>><<<>>>><<<><<>><<<>>><<<>><<<><<>><<<>>>><>><<<<><<<<>><<<<>><><<<<>>>><>>><><<>>>><<>>><><>>>><<>>>><><<>><><<>>><<<<>><>>><<>>>><>><<<>>><<<><<><<<<><<><>><<>><<<><<<>><><<><<<>><<<<>>><<<<>>>><<<<>>><<><<><>><<<>><<<<>>>><>>>><<>><>>><>><><<<><<<<>>><<<>>>><<>>><<<>><<<>><<<>>>><>>>><>>>><<<<>>>><><<<>><<<<><<<<>>>><<<<>>><>><<<<>><<<<>>><<>>><>><<>>>><<<>><<>><<<>>><<<<><<><<<>><<<<><<<<>>>><>><<<>>>><<>><>><<<>>>><<<>><>>><<<<>>>><>>>><>>>><<<>>><<<>>>><<<<>>>><<>>><<<<>><<<<><<<<>>>><<<>><<<><<<><<>>><>>><<><<<<><<<<><<<<>><><>>>><<<><<<>>>><<>>><>>>><<<<>><<<<>>>><<<<>>><<<<>>>><<>><>>><<<>>>><<<>>><><<>>>><<<<>>>><<<<>>><<<>>><<<>><>>><<><><<<>><<><>>><<<>>>><><>><<>><<><<<<>>>><>>>><>>><<<><<<><<<<>>><>><<<>>><<><<<>><<<>><><><>>>><<<<><<>>><>><<<>><>>>><<<>>>><<<<>>><<>>><<<>>><<<><<<>><<<<>>>><>>>><<<<>>>><>>>><<<<>><><<>>><<<<>>><<<>>><<><<<>>><<>>><<>>><<>>><>>>><>>><><<<><<>>>><<><<>>>><<<>><<<>>><<>>><>>>><<<>>>><<<<>><><<>>>><<>>>><><>>>><<<>>>><>>><<><><>><<<<>>>><<><>><<<>>><<>>><<<>><<<>>>><>>><<><>>>><<><>>><<>><<><<<<>>>><<><<>>><>>>><>>><<<<><<<<>><><<<<>><<<>>><<<<><<>>><<<<>>>><>><<<<>>>><<>>><>>><<>>><<>>>><<<><>>><><>>><<><<>><<<<>>><<<>>><<<><<<><<<<>>><<<>>>><>><><<<<>>><<><<<<>><<>>>><<<<>>>><<>>>><<>><>>><<>>>><>>><<>>>><<>><<<>><>>>><<<<><<<<>><<<>>><<<<>>><<<>>>><><>><<<>>>><<<<>>><<<>>>><<<><<<<><<<>>>><>><<<>>><<<<>><<><<<<>><<<<>>><<<<>><<<<>><<><<<<>><>><<>><<<<>>><<<>>><<<>>>><<<>><>>><<<<><<<>>><<<>>><<>>>><<<>><<<>>><<>><><>>><<><<><<<>>><<>>><<
diff --git a/AoC2022/17/solver.lisp b/AoC2022/17/solver.lisp
new file mode 100644
index 0000000..0be6c02
--- /dev/null
+++ b/AoC2022/17/solver.lisp
@@ -0,0 +1,90 @@
+(ql:quickload '(:fiveam :uiop :arrows))
+
+(defparameter *chamber-width* 7)
+
+(defun point (x y)
+ (+ x (* y *chamber-width*)))
+
+(defun coords (point)
+ (floor point *chamber-width*))
+
+(defparameter *rocks*
+ (vector (list (point 0 0) (point 1 0) (point 2 0) (point 3 0))
+ (list (point 1 0)
+ (point 0 1) (point 1 1) (point 2 1)
+ (point 1 2))
+ (list (point 0 0) (point 1 0) (point 2 0)
+ (point 2 1)
+ (point 2 2))
+ (list (point 0 0) (point 0 1) (point 0 2) (point 0 3))
+ (list (point 0 0) (point 1 0)
+ (point 0 1) (point 1 1))))
+
+(defun left (point) (1- point))
+(defun right (point) (1+ point))
+(defun down (point) (- point *chamber-width*))
+
+(defun no-collision-move (object direction obstacles)
+ (mapcar
+ (lambda (current)
+ (let ((next (funcall
+ (ecase direction
+ (#\> #'right)
+ (#\< #'left)
+ (#\v #'down))
+ current)))
+ (multiple-value-bind (y2 x2) (coords next)
+ (and (>= y2 0)
+ ;; no rolling boundaries
+ (multiple-value-bind (y x) (coords current)
+ (= 1 (+ (abs (- x x2)) (abs (- y y2)))))
+ (not (member next obstacles :test #'=))
+ next))))
+ object))
+
+(defun gen-object (seq)
+ (let ((len (length seq))
+ (index 0))
+ (lambda ()
+ (prog1 (aref seq index)
+ (setf index (mod (1+ index) len))))))
+
+(defun place-rock (rock highpoint)
+ (let ((left-pad 2))
+ (mapcar (lambda (point) (+ point left-pad (* *chamber-width* highpoint))) rock)))
+
+(defun advance (chamber next-move rock)
+ (let ((next-place (no-collision-move rock next-move chamber)))
+ (if (every #'integerp next-place)
+ next-place rock)))
+
+(defun next-move (chamber next-move rock)
+ (let* ((shift (advance chamber next-move rock))
+ (drop (advance chamber #\v shift)))
+ (values drop (equal shift drop))))
+
+(defun simulate (chamber rock next-shift)
+ (multiple-value-bind (new-place done-falling-p)
+ (next-move chamber (funcall next-shift) rock)
+ (if done-falling-p
+ (append new-place chamber)
+ (simulate chamber new-place next-shift))))
+
+(defun highpoint (obstacles)
+ (1+ (coords (reduce #'max obstacles))))
+
+(defun solver (drops-left highpoint obstacles next-rock next-shift)
+ (if (zerop drops-left)
+ (values highpoint obstacles)
+ (let ((obstacles (simulate obstacles
+ (place-rock (funcall next-rock) (+ highpoint 3))
+ next-shift)))
+ (solver (1- drops-left) (highpoint obstacles) 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"))))