From 47bdba2c0a8dda2fb69da639a226e21911cfb651 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 20 Dec 2023 23:50:06 +0100
Subject: Lösungen für Tag 20, Teil 2
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 src/day20.cpp | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)

diff --git a/src/day20.cpp b/src/day20.cpp
index 71b83a3..a17f2f2 100644
--- a/src/day20.cpp
+++ b/src/day20.cpp
@@ -3,6 +3,7 @@
 #include <iostream>
 #include <map>
 #include <memory>
+#include <numeric>
 #include <queue>
 #include <string>
 #include <vector>
@@ -197,8 +198,97 @@ part1()
 	cout << sums[0] * sums[1] << endl;
 }
 
+void
+part2()
+{
+	queue<tuple<string, int, string>> queue;
+	map<string, shared_ptr<Module>>   modules;
+
+	modules["output"] = make_shared<OutputModule>("output", queue);
+
+	const auto input = read_file("data/day20.txt");
+	for ( const auto& line: input ) {
+		const auto parts  = split(line, " -> ");
+		auto       module = parts[0];
+		const auto dests  = split(parts[1], ", ");
+
+		shared_ptr<Module> ptr;
+		if ( module == "broadcaster" ) {
+			ptr = make_shared<BroadcasterModuler>(module, queue);
+		}
+		else if ( module.starts_with('%') ) {
+			module.erase(0, 1);
+			ptr = make_shared<FlipFlopModule>(module, queue);
+		}
+		else if ( module.starts_with('&') ) {
+			module.erase(0, 1);
+			ptr = make_shared<ConjunctionModule>(module, queue);
+		}
+		else {
+			cerr << "unknown module type: " << module << endl;
+			return;
+		}
+
+		for ( const auto& dest: dests ) {
+			ptr->add_link(dest);
+		}
+
+		modules[module] = ptr;
+	}
+
+	// register senders
+	string to_rx;
+	for ( auto& module: modules ) {
+		auto [name, ptr] = module;
+
+		for ( const auto& link: ptr->links_ ) {
+			if ( modules.contains(link) ) { // link == "rx"
+				modules[link]->register_sender(name);
+			}
+			else {
+				to_rx = name;
+			}
+		}
+	}
+
+	map<string, long> cycle_modules;
+	for ( auto& module: modules ) {
+		auto [name, ptr] = module;
+		const auto links = ptr->links_;
+
+		if ( find(links.begin(), links.end(), to_rx) != links.end() ) {
+			cycle_modules[name] = 0;
+		}
+	}
+
+	for ( long i = 1;; ++i ) {
+		queue.emplace("button", 0, "broadcaster");
+		while ( !queue.empty() ) {
+			const auto [sender, signal, receiver] = queue.front();
+			queue.pop();
+
+			if ( signal == 1 && cycle_modules.contains(sender) ) {
+				cycle_modules[sender] = i;
+			}
+
+			if ( modules.contains(receiver) ) {
+				modules[receiver]->trigger(sender, signal);
+			}
+		}
+		if ( all_of(cycle_modules.begin(), cycle_modules.end(), [](const auto& module) { return module.second != 0; }) ) {
+			long result = 1;
+			for ( const auto& module: cycle_modules ) {
+				result = lcm(result, module.second);
+			}
+			cout << result << endl;
+			break;
+		}
+	}
+}
+
 int
 main()
 {
 	part1();
+	part2();
 }
-- 
cgit v1.3