diff options
| -rw-r--r-- | AoC2022/19/eg-in | 2 | ||||
| -rw-r--r-- | AoC2022/19/input | 30 | ||||
| -rw-r--r-- | AoC2022/19/solver.lisp | 108 |
3 files changed, 140 insertions, 0 deletions
diff --git a/AoC2022/19/eg-in b/AoC2022/19/eg-in new file mode 100644 index 0000000..f39c094 --- /dev/null +++ b/AoC2022/19/eg-in @@ -0,0 +1,2 @@ +Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian. +Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian. diff --git a/AoC2022/19/input b/AoC2022/19/input new file mode 100644 index 0000000..2c1044f --- /dev/null +++ b/AoC2022/19/input @@ -0,0 +1,30 @@ +Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 12 clay. Each geode robot costs 4 ore and 19 obsidian. +Blueprint 2: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 4 ore and 12 obsidian. +Blueprint 3: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 18 clay. Each geode robot costs 2 ore and 11 obsidian. +Blueprint 4: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 4 ore and 20 obsidian. +Blueprint 5: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 4 ore and 17 obsidian. +Blueprint 6: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 19 clay. Each geode robot costs 2 ore and 12 obsidian. +Blueprint 7: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 9 clay. Each geode robot costs 2 ore and 10 obsidian. +Blueprint 8: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 5 clay. Each geode robot costs 3 ore and 7 obsidian. +Blueprint 9: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 11 clay. Each geode robot costs 4 ore and 8 obsidian. +Blueprint 10: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 2 ore and 15 obsidian. +Blueprint 11: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 19 obsidian. +Blueprint 12: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 16 clay. Each geode robot costs 3 ore and 20 obsidian. +Blueprint 13: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 3 ore and 14 obsidian. +Blueprint 14: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 2 ore and 15 obsidian. +Blueprint 15: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 3 ore and 12 obsidian. +Blueprint 16: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 3 ore and 19 obsidian. +Blueprint 17: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 4 ore and 9 obsidian. +Blueprint 18: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 6 clay. Each geode robot costs 3 ore and 16 obsidian. +Blueprint 19: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 6 clay. Each geode robot costs 2 ore and 14 obsidian. +Blueprint 20: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 3 ore and 15 obsidian. +Blueprint 21: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 18 clay. Each geode robot costs 4 ore and 19 obsidian. +Blueprint 22: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 2 ore and 20 obsidian. +Blueprint 23: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 5 clay. Each geode robot costs 2 ore and 10 obsidian. +Blueprint 24: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 14 obsidian. +Blueprint 25: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 7 clay. Each geode robot costs 4 ore and 13 obsidian. +Blueprint 26: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 2 ore and 20 obsidian. +Blueprint 27: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 18 clay. Each geode robot costs 2 ore and 19 obsidian. +Blueprint 28: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 7 obsidian. +Blueprint 29: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 3 ore and 7 obsidian. +Blueprint 30: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 4 ore and 18 obsidian. diff --git a/AoC2022/19/solver.lisp b/AoC2022/19/solver.lisp new file mode 100644 index 0000000..0c67060 --- /dev/null +++ b/AoC2022/19/solver.lisp @@ -0,0 +1,108 @@ +(ql:quickload '(fiveam uiop cl-ppcre)) + + +(defun material (string) + (cond + ((string= string "ore") :ore) + ((string= string "clay") :clay) + ((string= string "obsidian") :obsidian) + ((string= string "geode") :geode))) + +(defun parse-robot-recipe (line) + (cl-ppcre:register-groups-bind ((#'material robot) (#'parse-integer fq) (#'material fm) (#'parse-integer sq) (#'material sm)) + ("(\\w+) robot costs (\\d+) (\\w+)(?: and (\\d+) (\\w+))?" line) + (append + (list robot fm fq) + (when sm (list sm sq))))) + +(defun start-resources () + (list :ore 0 :clay 0 :obsidian 0 :geode 0)) +(defun start-bots () + (list :ore 1 :clay 0 :obsidian 0 :geode 0)) + +(defun can-build-robot-p (requirements available) + (loop for (material amount) on requirements by #'cddr + always (<= amount (getf available material 0)))) + +(defun consume (requirements available) + (loop for (material amount) on requirements by #'cddr + do (decf (getf available material) amount)) + available) + +(fiveam:test requirements + (fiveam:is-false (can-build-robot-p '(:ore 6) '(:ore 5))) + (fiveam:is-false (can-build-robot-p '(:ore 6) '(:clay 5))) + (fiveam:is-true (can-build-robot-p '(:ore 2) '(:ore 5))) + (fiveam:is-true (can-build-robot-p '(:ore 2) '(:clay 2 :ore 5))) + (fiveam:is (equal '(:ore 2) (consume '(:ore 3) '(:ore 5))))) + +(defun material-collect (bots available-materials) + (loop for (material amount) on bots by #'cddr + nconc (list material (+ (getf available-materials material 0) amount)))) + +(defun bot-requirements (type recipes) + (cdr (assoc type recipes :test #'eq))) + +(defun plist-merge (func p1 p2 &optional default) + "Merge 2 flat plists P1 & P2 by FUNC. Use DEFAULT when value is missing on one list." + (flet ((keys (plist) (loop for key in plist by #'cddr collect key))) + (loop for key in (union (keys p1) (keys p2)) + nconc (list key (funcall func (getf p1 key default) (getf p2 key default)))))) + +(defun max-costs (blueprint) + (reduce + (lambda (acc item) + (plist-merge #'max acc item 0)) + (mapcar #'cdr blueprint))) + +(defun can-build (recipes available-materials) + (mapcan (lambda (bot-recipes) + (when (can-build-robot-p (cdr bot-recipes) available-materials) + (list (car bot-recipes)))) + recipes)) + +(defun should-build (blueprints robots) + (let ((max-cost (max-costs blueprints))) + (loop for (type amount) on robots by #'cddr + when (or (eq type :geode) + (<= amount (getf max-cost type 0))) + collect type))) + +(defun try! (build-next robots resources blueprints) + (let ((req (bot-requirements build-next blueprints))) + (when (can-build-robot-p req resources) + (consume req resources) + (incf (getf robots build-next 0))))) + + +(defun next-step (build-next robots resources blueprints time-left) + (if (zerop time-left) + (list robots resources) + (let ((new-robots (try! build-next robots resources blueprints))) + (mapcar + (lambda (next) + (next-step next robots (material-collect robots resources) blueprints (1- time-left))) + (if new-robots + (should-build blueprints robots) + (list build-next)))) + )) + +(let ((blueprints + (cdar + (mapcar + (lambda (l) + (let ((blueprint (uiop:split-string l :separator ":."))) + (cons (car blueprint) + (mapcar #'parse-robot-recipe (butlast (cdr blueprint)))))) + (uiop:read-file-lines "eg-in")))) + ;; (materials '(:ore 8 :clay 20)) + (materials (start-resources)) + (bots (start-bots)) + ;; (bots '(:geode 1 :ore 8 :clay 20)) + (time-left 5)) + + + (next-step :clay bots materials blueprints time-left) + + + ) |