aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--AoC2022/21/solver.lisp71
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)))))