diff options
| -rw-r--r-- | AoC2022/21/solver.lisp | 71 |
1 files changed, 58 insertions, 13 deletions
diff --git a/AoC2022/21/solver.lisp b/AoC2022/21/solver.lisp index fa28e31..dd061ad 100644 --- a/AoC2022/21/solver.lisp +++ b/AoC2022/21/solver.lisp @@ -1,26 +1,71 @@ (ql:quickload '(fiveam uiop cl-ppcre trivia)) +(defun parse-line (line table) + (cond + ((ppcre:register-groups-bind ((#'read-from-string monkey dep1 op dep2)) + ("(\\w+): (\\w+) ([*+/-]) (\\w+)" line) + (setf (gethash monkey table) (list op dep1 dep2)))) + ((ppcre:register-groups-bind ((#'read-from-string monkey number)) + ("(\\w+): (\\d+)" line) + (setf (gethash monkey table) number))))) + (defun build-monkey-table (filename) (let ((table (make-hash-table :test #'eq))) (with-open-file (stream filename) (loop for line = (read-line stream nil nil) while line - do - (cond - ((ppcre:register-groups-bind ((#'read-from-string monkey dep1 op dep2)) - ("(\\w+): (\\w+) ([*+/-]) (\\w+)" line) - (setf (gethash monkey table) (list op dep1 dep2)))) - ((ppcre:register-groups-bind ((#'read-from-string monkey number)) - ("(\\w+): (\\d+)" line) - (setf (gethash monkey table) number)))))) + do (parse-line line table))) table)) (defun resolver (entry table) (trivia:match entry - ((list op a b) (funcall op - (resolver (gethash a table) table) - (resolver (gethash b table) table))) + ((list op a b) + (funcall op + (resolver (gethash a table) table) + (resolver (gethash b table) table))) (a a))) -(let ((table (build-monkey-table "input"))) - (= 56490240862410 (resolver (gethash 'root table) table))) +;;; part2 + +(defun human-in-tree-p (name table) + (or (eq name 'humn) + (trivia:match (gethash name table) + ((list _ left right) + (or (human-in-tree-p left table) + (human-in-tree-p right table)))))) + +(defun invert-operation (human-lhs-p op target known) + (ecase op + (+ (- target known)) + (- (if human-lhs-p + (+ target known) + (- known target))) + (* (/ target known)) + (/ (if human-lhs-p + (* target known) + (/ known target))))) + +(defun reverse-solver (entry target table) + (destructuring-bind (op left right) entry + (let* ((human-lhs-p (human-in-tree-p left table)) + (next-entry (if human-lhs-p left right)) + (known-term (resolver (gethash (if human-lhs-p right left) table) table)) + (new-target (invert-operation human-lhs-p op target known-term))) + (if (eq next-entry 'humn) new-target + (reverse-solver (gethash next-entry table) new-target table))))) + +(defun part2 (table) + (reverse-solver + (cons '- (cdr (gethash 'root table))) + 0 table)) + + +;; solutions + +(fiveam:test solutions + (let ((table (build-monkey-table "eg-in"))) + (fiveam:is (= 152 (resolver (gethash 'root table) table))) + (fiveam:is (= 301 (part2 table)))) + (let ((table (build-monkey-table "input"))) + (fiveam:is (= 56490240862410 (resolver (gethash 'root table) table))) + (fiveam:is (= 3403989691757 (part2 table))))) |