aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2023/day20
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2023/day20')
-rw-r--r--AoC2023/day20/eg-i15
-rw-r--r--AoC2023/day20/eg-i25
-rw-r--r--AoC2023/day20/input58
-rw-r--r--AoC2023/day20/solver.lisp91
4 files changed, 159 insertions, 0 deletions
diff --git a/AoC2023/day20/eg-i1 b/AoC2023/day20/eg-i1
new file mode 100644
index 0000000..2dc1bab
--- /dev/null
+++ b/AoC2023/day20/eg-i1
@@ -0,0 +1,5 @@
+broadcaster -> a, b, c
+%a -> b
+%b -> c
+%c -> inv
+&inv -> a
diff --git a/AoC2023/day20/eg-i2 b/AoC2023/day20/eg-i2
new file mode 100644
index 0000000..2738ceb
--- /dev/null
+++ b/AoC2023/day20/eg-i2
@@ -0,0 +1,5 @@
+broadcaster -> a
+%a -> inv, con
+&inv -> b
+%b -> con
+&con -> output
diff --git a/AoC2023/day20/input b/AoC2023/day20/input
new file mode 100644
index 0000000..410063f
--- /dev/null
+++ b/AoC2023/day20/input
@@ -0,0 +1,58 @@
+%fg -> nt, gt
+&zp -> rx
+%fh -> nt, xz
+%pj -> zj, zq
+%jc -> nt, nk
+%mr -> vv, pz
+%cl -> fp, zq
+%xb -> bl, vv
+%nc -> zq
+%mg -> vn
+%zj -> cf
+&sb -> zp
+%ht -> pp
+%gt -> jc
+%rq -> ft
+&nt -> rq, fg, ft, nd, gt, xz
+%ps -> xm
+%fs -> ff
+%nb -> dv
+%qd -> xb
+%kg -> mr, vv
+%dv -> vv, hr
+%rm -> zq, fs
+%nk -> rq, nt
+%hr -> dm, vv
+%xm -> vn, ht
+%pp -> mq
+%br -> vn, jz
+%gr -> ln
+%bh -> qd, vv
+%cf -> gr, zq
+&vv -> dm, bl, sb, nb, qd, bh
+%zc -> zv
+%zv -> dc, vn
+%jz -> qs
+&nd -> zp
+%rd -> nc, zq
+&ds -> zp
+%mq -> vn, zc
+%bl -> bb
+%qn -> nt
+%pz -> vv
+%qs -> vn, ps
+%lm -> nt, qn
+%xz -> dr
+%bb -> nb, vv
+%dm -> kg
+%ft -> fh
+&vn -> br, jz, ht, ps, zc, pp, ds
+%xd -> nt, lm
+&hf -> zp
+broadcaster -> pj, fg, bh, br
+%fp -> rd, zq
+&zq -> fs, gr, ff, hf, ln, zj, pj
+%ff -> cl
+%dr -> xd, nt
+%ln -> rm
+%dc -> mg, vn
diff --git a/AoC2023/day20/solver.lisp b/AoC2023/day20/solver.lisp
new file mode 100644
index 0000000..87597cf
--- /dev/null
+++ b/AoC2023/day20/solver.lisp
@@ -0,0 +1,91 @@
+(ql:quickload '(fiveam str arrows))
+(use-package '(alexandria fiveam))
+
+(defstruct module
+ type state outputs)
+
+(defun parse-input (lines)
+ (let ((board (make-hash-table)))
+ (dolist (instruction lines board)
+ (destructuring-bind (module outputs) (str:split " -> " instruction)
+ (let ((outputs (mapcar #'read-from-string (str:split ", " outputs)))
+ (name (if (string-equal "broadcaster" module) 'broadcaster (read-from-string (subseq module 1))))
+ (type (ecase (elt module 0)
+ (#\b 'broadcaster)
+ (#\& 'conjunction)
+ (#\% 'flip-flop))))
+ (setf (gethash name board) (make-module :type type
+ :state (if (eq type 'conjunction) (make-hash-table) 'off)
+ :outputs outputs)))))))
+
+(defun prepare-board (board)
+ (maphash (lambda (name value)
+ (with-slots (type state outputs) value
+ (dolist (out outputs)
+ (when (arrows:some->
+ (gethash out board)
+ (slot-value 'type)
+ (eq 'conjunction))
+ (setf (gethash name (slot-value (gethash out board) 'state)) 'low)))))
+ board)
+ board)
+
+(defun toggle (state)
+ (ecase state
+ (off 'on)
+ (on 'off)))
+
+(defun all-high-p (state)
+ (every (lambda (v) (eq 'high v)) (hash-table-values state)))
+
+(defun propagate (board signals)
+ (mapcan
+ (lambda (in)
+ (destructuring-bind (from to signal) in
+ (when (gethash to board)
+ (with-slots (type state outputs) (gethash to board)
+ (when-let
+ ((msg
+ (ecase type
+ (broadcaster signal)
+ (flip-flop (when (eq signal 'low)
+ (ecase (setf state (toggle state))
+ (on 'high)
+ (off 'low))))
+ (conjunction
+ (setf (gethash from state) signal)
+ (if (all-high-p state) 'low 'high)))))
+ (mapcar (lambda (o) (list to o msg)) outputs))))))
+ signals))
+
+(test parts
+ (let ((board (prepare-board (parse-input (uiop:read-file-lines "eg-i1")))))
+ (is (equal
+ '((BROADCASTER A LOW) (BROADCASTER B LOW) (BROADCASTER C LOW))
+ (propagate board '((button broadcaster low)))))
+ (is (equal
+ '((C INV HIGH))
+ (propagate board '((broadcaster C low)))))
+ (is (equal
+ '((INV A LOW))
+ (propagate board '((c inv high)))))
+ (is (null (propagate board '((c blank low)))))))
+
+(defun solver1 (lines)
+ (let ((board (prepare-board (parse-input lines))))
+ (labels ((rec (signals n-high n-low)
+ (if (null signals)
+ (list n-high n-low)
+ (rec (propagate board signals)
+ (+ n-high (count 'high signals :key #'caddr))
+ (+ n-low (count 'low signals :key #'caddr))))))
+ (loop repeat 1000
+ for (high low) = (rec '((button broadcaster low)) 0 0)
+ sum high into n-high
+ sum low into n-low
+ finally (return (* n-high n-low))))))
+
+(test solutions
+ (is (= 32000000 (solver1 (uiop:read-file-lines "eg-i1"))))
+ (is (= 11687500 (solver1 (uiop:read-file-lines "eg-i2"))))
+ (is (= 791120136 (solver1 (uiop:read-file-lines "input")))))