From b13d1071a270c8ba655800cca26a76f9d6735e6e Mon Sep 17 00:00:00 2001
From: Oscar Najera <hi@oscarnajera.com>
Date: Fri, 29 Dec 2023 20:16:29 +0100
Subject: part2

---
 AoC2023/day20/solver.lisp | 42 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

(limited to 'AoC2023/day20/solver.lisp')

diff --git a/AoC2023/day20/solver.lisp b/AoC2023/day20/solver.lisp
index 87597cf..d57af9a 100644
--- a/AoC2023/day20/solver.lisp
+++ b/AoC2023/day20/solver.lisp
@@ -1,5 +1,7 @@
 (ql:quickload '(fiveam str arrows))
-(use-package '(alexandria fiveam))
+(defpackage :day20
+  (:use :cl :fiveam :alexandria))
+(in-package :day20)
 
 (defstruct module
   type state outputs)
@@ -85,7 +87,43 @@
             sum low into n-low
             finally (return  (* n-high n-low))))))
 
+(defun common-cycle (cycles)
+  (apply #'lcm (mapcar #'cdr cycles)))
+
+(defun solver2 ()
+  (let* ((board (prepare-board (parse-input (uiop:read-file-lines "input"))))
+         ;; feed is a single conjunction that gives to rx by inspecting input
+         ;; feed has 4 inputs, it needs them all to be on high before it outputs
+         ;; a low for rx
+         ;; The main assumption is that each one of those inputs will send a high
+         ;; periodically, and all will be on high on the least common multiple of
+         ;; their cycle.
+         (feed (loop for name being the hash-key of board
+                       using (hash-value module)
+                     when (member 'rx (slot-value module 'outputs))
+                       return name))
+         (cycles (loop for name being the hash-key of board
+                         using (hash-value module)
+                       when (member feed (slot-value module 'outputs))
+                         collect (cons name 0)))
+         (presses 1)
+         (start '((button broadcaster low))))
+
+    (loop named outer
+          for signals = (propagate board start) then (propagate board (or signals start))
+          when (null signals)
+            do (incf presses)
+               ;; until (< 4000 presses)
+          do
+             (loop for (from to pulse) in signals do
+               (when (and (eq to feed) (eq pulse 'high))
+                 (setf (cdr (assoc from cycles)) presses))
+               (when (every (compose #'positive-fixnum-p #'cdr) cycles)
+                 (return-from outer (common-cycle cycles)))))))
+
+
 (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")))))
+  (is (= 791120136 (solver1 (uiop:read-file-lines "input"))))
+  (is (= 215252378794009 (solver2))))
-- 
cgit v1.2.3