commit 8c78fb5cb90087550a894bd7d8d992922ece70ce
parent ca198cf627cb5c39d486e44e55c3ccfbd16b23c7
Author: Lukas Henkel <lh@entf.net>
Date: Wed, 20 Dec 2023 20:59:09 +0100
Day 20 task 1
Diffstat:
| A | input/20.txt | | | 58 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/day-20.lisp | | | 111 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | t/day-20.lisp | | | 20 | ++++++++++++++++++++ |
3 files changed, 189 insertions(+), 0 deletions(-)
diff --git a/input/20.txt b/input/20.txt
@@ -0,0 +1,58 @@
+%dm -> jz, ct
+&ft -> rx
+%hc -> kh
+%kg -> gd, sl
+&sl -> bs, bq, ts, zd, gk, xx, lp
+%rf -> xk, jz
+%zd -> kg
+%dp -> ql, pq
+%ss -> pq, mb
+&rr -> hc, lt, kh, fv, tc, vg
+%hv -> nh
+%nh -> pq, xm
+&jz -> bn, vz, xz
+%vf -> nc, sl
+%gk -> pc
+%bs -> gk
+&pq -> tb, qh, ls, hv, ql
+%jb -> rr, hc
+%fv -> cd, rr
+&vz -> ft
+%mm -> jr, rr
+%vg -> mm
+%cd -> tc, rr
+&bq -> ft
+%xg -> pb, jz
+%xx -> zd
+%ls -> tb, pq
+%pb -> jz, rz
+%tc -> vp
+%kh -> ck
+%lp -> xx
+%tb -> ss
+%qk -> jz, xg
+%xz -> dm
+%jr -> rb, rr
+%mb -> hv, pq
+&qh -> ft
+< -> ft
+%rb -> rr
+%pc -> hr, sl
+%hr -> vf, sl
+%gd -> bs, sl
+%xm -> dp, pq
+%ct -> jz, rj
+%ck -> vg, rr
+%cr -> jz, rf
+%bn -> xz, jz
+%vp -> rr, jb
+%hl -> pq, vj
+%ts -> lp, sl
+%rz -> jz, cr
+%ql -> tr
+%xk -> jz
+%vj -> pq
+%tr -> pq, hl
+broadcaster -> ls, fv, ts, bn
+%nc -> sl
+%rj -> jz, qk
diff --git a/src/day-20.lisp b/src/day-20.lisp
@@ -0,0 +1,111 @@
+(defpackage #:aoc/day-20
+ (:use #:cl #:aoc/utils)
+ (:export #:day-20))
+(in-package #:aoc/day-20)
+
+(defclass module ()
+ ((label
+ :initarg :label
+ :reader module-label)
+ (targets
+ :initarg :targets
+ :accessor module-targets)
+ (connected
+ :initform nil
+ :accessor module-connected)))
+
+(defmethod print-object ((module module) stream)
+ (print-unreadable-object (module stream :type t)
+ (format stream "~A" (module-label module))))
+
+(defclass flip-flop (module)
+ ((state
+ :initform nil)))
+
+(defmethod print-object ((module flip-flop) stream)
+ (print-unreadable-object (module stream :type t)
+ (with-slots (state)
+ module
+ (format stream "~A (~A)" (module-label module)
+ (if state "on" "off")))))
+
+(defclass conjunction (module)
+ ((states
+ :initform (make-hash-table))))
+
+(defclass noop-module (module)
+ ())
+
+(defmethod pulse ((module module) sender type)
+ (with-slots (targets)
+ module
+ (loop for target in targets
+ collect (list module target type))))
+
+(defmethod pulse ((module flip-flop) sender type)
+ (with-slots (state)
+ module
+ (when (eq type :low)
+ (setf state (not state))
+ (call-next-method module sender (if state :high :low)))))
+
+(defmethod pulse ((module conjunction) sender type)
+ (with-slots (states connected)
+ module
+ (setf (gethash sender states) type)
+ (call-next-method module sender (if (loop for from in connected
+ for mem = (gethash from states)
+ always (eq mem :high))
+ :low
+ :high))))
+
+(defmethod pulse ((module noop-module) sender type))
+
+(defun parse-line (line)
+ (let* ((pos-source-end (position #\Space line))
+ (source-type (case (aref line 0)
+ (#\% 'flip-flop)
+ (#\& 'conjunction)
+ (t 'module)))
+ (source-label (subseq line
+ (if (eq source-type 'module) 0 1)
+ pos-source-end))
+ (target-labels (loop for pos from (+ pos-source-end 4) below (length line)
+ for end = (or (position #\, line :start pos)
+ (length line))
+ collect (subseq line pos end)
+ do (setf pos (1+ end)))))
+ (make-instance source-type :label source-label :targets target-labels)))
+
+(defun parse-input (input)
+ (let ((modules (make-hash-table :test 'equal)))
+ (loop for line = (read-line input nil)
+ while line
+ for module = (parse-line line)
+ do (setf (gethash (module-label module) modules) module))
+ (loop for module being the hash-value of modules
+ do (setf (module-targets module)
+ (loop for target-label in (module-targets module)
+ for target-module = (or (gethash target-label modules)
+ (setf (gethash target-label modules)
+ (make-instance 'noop-module
+ :label target-label)))
+ do (push module (module-connected target-module))
+ collect target-module)))
+ modules))
+
+(defun day-20 (input)
+ (let* ((modules (parse-input input))
+ (broadcast (gethash "broadcaster" modules)))
+ (loop with low-count = 0
+ with high-count = 0
+ repeat 1000
+ do (loop with next = (list (list nil broadcast :low))
+ while next
+ for next-next = (loop for (from to type) in next
+ do (ecase type
+ (:low (incf low-count))
+ (:high (incf high-count)))
+ nconc (pulse to from type))
+ do (setf next next-next))
+ finally (return (* low-count high-count)))))
diff --git a/t/day-20.lisp b/t/day-20.lisp
@@ -0,0 +1,20 @@
+(defpackage #:aoc-test/day-20
+ (:use #:cl #:lisp-unit2))
+(in-package #:aoc-test/day-20)
+
+(define-test test-day-20
+ ()
+ (multiple-value-bind (task-1)
+ (aoc:run-day 20 "broadcaster -> a, b, c
+%a -> b
+%b -> c
+%c -> inv
+&inv -> a")
+ (assert= 32000000 task-1))
+ (multiple-value-bind (task-1)
+ (aoc:run-day 20 "broadcaster -> a
+%a -> inv, con
+&inv -> b
+%b -> con
+&con -> output")
+ (assert= 11687500 task-1)))
