Lösungen für Tag 20, Teil 2

1 files changed, 90 insertions, 0 deletions

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();
 }