aboutsummaryrefslogtreecommitdiff
path: root/src/day20.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day20.cpp')
-rw-r--r--src/day20.cpp293
1 files changed, 0 insertions, 293 deletions
diff --git a/src/day20.cpp b/src/day20.cpp
deleted file mode 100644
index f85ac90..0000000
--- a/src/day20.cpp
+++ /dev/null
@@ -1,293 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <memory>
6#include <numeric>
7#include <queue>
8#include <string>
9#include <vector>
10
11using namespace std;
12
13vector<string>
14read_file(string_view filename)
15{
16 fstream input{ filename };
17 vector<string> data;
18
19 for ( string line; getline(input, line); ) {
20 data.emplace_back(line);
21 }
22
23 return data;
24}
25
26vector<string>
27split(string_view line, string_view delimiter)
28{
29 size_t pos_start = 0;
30 size_t pos_end = 0;
31
32 vector<string> res;
33
34 while ( (pos_end = line.find(delimiter, pos_start)) != string::npos ) {
35 auto token = line.substr(pos_start, pos_end - pos_start);
36 pos_start = pos_end + delimiter.length();
37
38 res.emplace_back(token);
39 }
40
41 if ( pos_start != line.size() ) {
42 res.emplace_back(line.substr(pos_start));
43 }
44 return res;
45}
46
47struct Module { // NOLINT
48protected:
49 explicit Module(string_view name, queue<tuple<string, int, string>>& queue)
50 : name_(name)
51 , queue_(queue)
52 {
53 }
54 virtual ~Module() = default;
55
56public:
57 virtual void trigger(string_view sender, int signal) = 0;
58
59 void register_sender(string_view sender) { senders_.emplace(sender, 0); }
60
61protected:
62 void send_signal(int signal) const
63 {
64 for ( const auto& link: links_ ) {
65 queue_.emplace(name_, signal, link);
66 }
67 }
68
69public:
70 void add_link(string_view link) { links_.emplace_back(link); }
71
72protected:
73 const string name_;
74 queue<tuple<string, int, string>>& queue_;
75
76public:
77 vector<string> links_;
78 map<string, int> senders_;
79};
80
81struct BroadcasterModuler : public Module {
82 explicit BroadcasterModuler(string_view name, queue<tuple<string, int, string>>& queue)
83 : Module(name, queue)
84 {
85 }
86 void trigger(string_view, int signal) override
87 {
88 send_signal(signal);
89 }
90};
91
92struct FlipFlopModule : public Module {
93 explicit FlipFlopModule(string_view name, queue<tuple<string, int, string>>& queue)
94 : Module(name, queue)
95 {
96 }
97 void trigger(string_view, int signal) override
98 {
99 if ( signal == 1 ) {
100 return;
101 }
102 state_ = (state_ + 1) % 2;
103 send_signal(state_);
104 }
105 int state_{ 0 };
106};
107
108struct ConjunctionModule : public Module {
109 explicit ConjunctionModule(string_view name, queue<tuple<string, int, string>>& queue)
110 : Module(name, queue)
111 {
112 }
113 void trigger(string_view sender, int signal) override
114 {
115 senders_[string(sender)] = signal;
116 if ( all_of(senders_.begin(), senders_.end(), [](const auto& link) { return link.second == 1; }) ) {
117 send_signal(0);
118 }
119 else {
120 send_signal(1);
121 }
122 }
123};
124
125struct OutputModule : public Module {
126 explicit OutputModule(string_view name, queue<tuple<string, int, string>>& queue)
127 : Module(name, queue)
128 {
129 }
130 void trigger(string_view, int) override
131 {
132 }
133};
134
135void
136part1(const vector<string>& input)
137{
138 queue<tuple<string, int, string>> queue;
139 map<string, shared_ptr<Module>> modules;
140
141 modules["output"] = make_shared<OutputModule>("output", queue);
142
143 for ( const auto& line: input ) {
144 const auto parts = split(line, " -> ");
145 auto module = parts[0];
146 const auto dests = split(parts[1], ", ");
147
148 shared_ptr<Module> ptr;
149 if ( module == "broadcaster" ) {
150 ptr = make_shared<BroadcasterModuler>(module, queue);
151 }
152 else if ( module.starts_with('%') ) {
153 module.erase(0, 1);
154 ptr = make_shared<FlipFlopModule>(module, queue);
155 }
156 else if ( module.starts_with('&') ) {
157 module.erase(0, 1);
158 ptr = make_shared<ConjunctionModule>(module, queue);
159 }
160 else {
161 cerr << "unknown module type: " << module << endl;
162 return;
163 }
164
165 for ( const auto& dest: dests ) {
166 ptr->add_link(dest);
167 }
168
169 modules[module] = ptr;
170 }
171
172 // register senders
173 for ( auto& module: modules ) {
174 auto [name, ptr] = module;
175
176 for ( const auto& link: ptr->links_ ) {
177 if ( modules.contains(link) ) {
178 modules[link]->register_sender(name);
179 }
180 }
181 }
182
183 long sums[2] = { 0, 0 };
184 for ( int i = 0; i != 1000; ++i ) {
185 queue.emplace("button", 0, "broadcaster");
186 while ( !queue.empty() ) {
187 const auto [sender, signal, receiver] = queue.front();
188 queue.pop();
189
190 sums[signal]++;
191
192 if ( modules.contains(receiver) ) {
193 modules[receiver]->trigger(sender, signal);
194 }
195 }
196 }
197 cout << sums[0] * sums[1] << endl;
198}
199
200void
201part2(const vector<string>& input)
202{
203 queue<tuple<string, int, string>> queue;
204 map<string, shared_ptr<Module>> modules;
205
206 modules["output"] = make_shared<OutputModule>("output", queue);
207
208 for ( const auto& line: input ) {
209 const auto parts = split(line, " -> ");
210 auto module = parts[0];
211 const auto dests = split(parts[1], ", ");
212
213 shared_ptr<Module> ptr;
214 if ( module == "broadcaster" ) {
215 ptr = make_shared<BroadcasterModuler>(module, queue);
216 }
217 else if ( module.starts_with('%') ) {
218 module.erase(0, 1);
219 ptr = make_shared<FlipFlopModule>(module, queue);
220 }
221 else if ( module.starts_with('&') ) {
222 module.erase(0, 1);
223 ptr = make_shared<ConjunctionModule>(module, queue);
224 }
225 else {
226 cerr << "unknown module type: " << module << endl;
227 return;
228 }
229
230 for ( const auto& dest: dests ) {
231 ptr->add_link(dest);
232 }
233
234 modules[module] = ptr;
235 }
236
237 // register senders
238 string to_rx;
239 for ( auto& module: modules ) {
240 auto [name, ptr] = module;
241
242 for ( const auto& link: ptr->links_ ) {
243 if ( modules.contains(link) ) { // link == "rx"
244 modules[link]->register_sender(name);
245 }
246 else {
247 to_rx = name;
248 }
249 }
250 }
251
252 map<string, long> cycle_modules;
253 for ( auto& module: modules ) {
254 auto [name, ptr] = module;
255 const auto links = ptr->links_;
256
257 if ( find(links.begin(), links.end(), to_rx) != links.end() ) {
258 cycle_modules[name] = 0;
259 }
260 }
261
262 for ( long i = 1;; ++i ) {
263 queue.emplace("button", 0, "broadcaster");
264 while ( !queue.empty() ) {
265 const auto [sender, signal, receiver] = queue.front();
266 queue.pop();
267
268 if ( signal == 1 && cycle_modules.contains(sender) ) {
269 cycle_modules[sender] = i;
270 }
271
272 if ( modules.contains(receiver) ) {
273 modules[receiver]->trigger(sender, signal);
274 }
275 }
276 if ( all_of(cycle_modules.begin(), cycle_modules.end(), [](const auto& module) { return module.second != 0; }) ) {
277 long result = 1;
278 for ( const auto& module: cycle_modules ) {
279 result = lcm(result, module.second);
280 }
281 cout << result << endl;
282 break;
283 }
284 }
285}
286
287int
288main()
289{
290 const auto input = read_file("data/day20.txt");
291 part1(input);
292 part2(input);
293}