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

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