blob: dd061ad6cdafa7eb0840884914174487694fb1a1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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 (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)))))
|
