Day 21 Full solve

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)))))