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

---
 src/day20.cpp | 204 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 204 insertions(+)
 create mode 100644 src/day20.cpp

(limited to 'src/day20.cpp')

diff --git a/src/day20.cpp b/src/day20.cpp
new file mode 100644
index 0000000..71b83a3
--- /dev/null
+++ b/src/day20.cpp
@@ -0,0 +1,204 @@
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <memory>
+#include <queue>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+vector<string>
+read_file(string_view filename)
+{
+	fstream        input{ filename };
+	vector<string> data;
+
+	for ( string line; getline(input, line); ) {
+		data.emplace_back(line);
+	}
+
+	return data;
+}
+
+vector<string>
+split(string_view line, string_view delimiter)
+{
+	size_t pos_start = 0;
+	size_t pos_end   = 0;
+
+	vector<string> res;
+
+	while ( (pos_end = line.find(delimiter, pos_start)) != string::npos ) {
+		auto token = line.substr(pos_start, pos_end - pos_start);
+		pos_start  = pos_end + delimiter.length();
+
+		res.emplace_back(token);
+	}
+
+	if ( pos_start != line.size() ) {
+		res.emplace_back(line.substr(pos_start));
+	}
+	return res;
+}
+
+struct Module { // NOLINT
+protected:
+	explicit Module(string_view name, queue<tuple<string, int, string>>& queue)
+	    : name_(name)
+	    , queue_(queue)
+	{
+	}
+	virtual ~Module() = default;
+
+public:
+	virtual void trigger(string_view sender, int signal) = 0;
+
+	void register_sender(string_view sender) { senders_.emplace(sender, 0); }
+
+protected:
+	void send_signal(int signal) const
+	{
+		for ( const auto& link: links_ ) {
+			queue_.emplace(name_, signal, link);
+		}
+	}
+
+public:
+	void add_link(string_view link) { links_.emplace_back(link); }
+
+protected:
+	const string                       name_;
+	queue<tuple<string, int, string>>& queue_;
+
+public:
+	vector<string>   links_;
+	map<string, int> senders_;
+};
+
+struct BroadcasterModuler : public Module {
+	explicit BroadcasterModuler(string_view name, queue<tuple<string, int, string>>& queue)
+	    : Module(name, queue)
+	{
+	}
+	void trigger(string_view, int signal) override
+	{
+		send_signal(signal);
+	}
+};
+
+struct FlipFlopModule : public Module {
+	explicit FlipFlopModule(string_view name, queue<tuple<string, int, string>>& queue)
+	    : Module(name, queue)
+	{
+	}
+	void trigger(string_view, int signal) override
+	{
+		if ( signal == 1 ) {
+			return;
+		}
+		state_ = (state_ + 1) % 2;
+		send_signal(state_);
+	}
+	int state_{ 0 };
+};
+
+struct ConjunctionModule : public Module {
+	explicit ConjunctionModule(string_view name, queue<tuple<string, int, string>>& queue)
+	    : Module(name, queue)
+	{
+	}
+	void trigger(string_view sender, int signal) override
+	{
+		senders_[string(sender)] = signal;
+		if ( all_of(senders_.begin(), senders_.end(), [](const auto& link) { return link.second == 1; }) ) {
+			send_signal(0);
+		}
+		else {
+			send_signal(1);
+		}
+	}
+};
+
+struct OutputModule : public Module {
+	explicit OutputModule(string_view name, queue<tuple<string, int, string>>& queue)
+	    : Module(name, queue)
+	{
+	}
+	void trigger(string_view, int) override
+	{
+	}
+};
+
+void
+part1()
+{
+	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
+	for ( auto& module: modules ) {
+		auto [name, ptr] = module;
+
+		for ( const auto& link: ptr->links_ ) {
+			if ( modules.contains(link) ) {
+				modules[link]->register_sender(name);
+			}
+		}
+	}
+
+	long sums[2] = { 0, 0 };
+	for ( int i = 0; i != 1000; ++i ) {
+		queue.emplace("button", 0, "broadcaster");
+		while ( !queue.empty() ) {
+			const auto [sender, signal, receiver] = queue.front();
+			queue.pop();
+
+			sums[signal]++;
+
+			if ( modules.contains(receiver) ) {
+				modules[receiver]->trigger(sender, signal);
+			}
+		}
+	}
+	cout << sums[0] * sums[1] << endl;
+}
+
+int
+main()
+{
+	part1();
+}
-- 
cgit v1.3