Line data Source code
1 : #include "LinewiseInput.h"
2 : #include "PuzzleImpl.h"
3 :
4 : #include <libassert/assert.hpp>
5 : #include <re2/re2.h>
6 :
7 : #include <algorithm>
8 : #include <cstdlib>
9 : #include <map>
10 : #include <memory>
11 : #include <numeric>
12 : #include <queue>
13 : #include <span>
14 : #include <string_view>
15 : #include <tuple>
16 :
17 : namespace {
18 :
19 : constexpr bool HI = true;
20 : constexpr bool LO = false;
21 :
22 : constexpr bool ON = true;
23 : constexpr bool OFF = false;
24 :
25 : class Module;
26 :
27 : using Call = std::tuple<Module *, Module *, bool>;
28 : using CallQueue = std::queue<Call>;
29 :
30 : class Module {
31 : public:
32 : Module(std::string_view const name, std::shared_ptr<CallQueue> const &calls)
33 118 : : _name(name), _calls(calls) {}
34 :
35 118 : virtual ~Module() = default;
36 :
37 : virtual void receiveSignal(Module const *const sender, bool signal) = 0;
38 :
39 : virtual void registerInput(Module const &sender) = 0;
40 218 : void registerOutput(Module &receiver) { _outputs.push_back(&receiver); };
41 :
42 218 : static void connect(Module *const sender, Module *const receiver) {
43 218 : sender->registerOutput(*receiver);
44 218 : receiver->registerInput(*sender);
45 218 : }
46 :
47 89921 : [[nodiscard]] std::string_view name() const { return _name; }
48 :
49 : protected:
50 134947 : void send(bool const signal) {
51 134947 : for (Module *m : _outputs)
52 319623 : _calls->emplace(this, m, signal);
53 134947 : }
54 :
55 : private:
56 : std::string_view _name;
57 : std::shared_ptr<CallQueue> _calls;
58 : std::vector<Module *> _outputs;
59 : };
60 :
61 : class FlipFlopModule final : public Module {
62 : public:
63 : using Module::Module;
64 :
65 134 : void registerInput(Module const &) final {}
66 :
67 199843 : void receiveSignal(Module const *const, bool signal) final {
68 199843 : if (signal == LO) {
69 40099 : _state = !_state;
70 40099 : send(_state == ON ? HI : LO);
71 40099 : }
72 199843 : }
73 :
74 : private:
75 : bool _state = OFF;
76 : };
77 :
78 : class ConjunctionModule final : public Module {
79 : public:
80 : using Module::Module;
81 :
82 82 : void registerInput(Module const &sender) final { _inputStates.emplace(sender.name(), LO); }
83 :
84 89835 : void receiveSignal(Module const *const sender, bool signal) final {
85 89835 : auto it = _inputStates.find(sender->name());
86 89835 : ASSUME(it != _inputStates.end());
87 89835 : it->second = signal;
88 :
89 89835 : if (signal == HI && _hiCallback)
90 4 : _hiCallback(sender->name());
91 :
92 110624 : if (std::ranges::all_of(_inputStates, [](std::pair<std::string_view, bool> const &p) {
93 110624 : return p.second == HI;
94 110624 : }))
95 29945 : send(LO);
96 59890 : else
97 59890 : send(HI);
98 89835 : }
99 :
100 1 : void registerHiCallback(std::function<void(std::string_view)> const &f) { _hiCallback = f; }
101 :
102 1 : [[nodiscard]] size_t numInputs() const { return _inputStates.size(); }
103 :
104 : private:
105 : std::map<std::string_view, bool> _inputStates;
106 : std::function<void(std::string_view)> _hiCallback;
107 : };
108 :
109 : class OutputModule final : public Module {
110 : public:
111 : using Module::Module;
112 2 : void registerInput(Module const &) final {}
113 29945 : void receiveSignal(Module const *const, bool) final {}
114 : };
115 :
116 : class BroadcastModule final : public Module {
117 : public:
118 : using Module::Module;
119 :
120 0 : void registerInput(Module const &) final { UNREACHABLE(); }
121 :
122 5013 : void receiveSignal(Module const *const, bool signal) final { send(signal); }
123 : };
124 :
125 : class Network {
126 : public:
127 : Network(std::span<std::string_view const> const flipFlopModules,
128 : std::span<std::string_view const> const conjunctionModules,
129 : std::span<std::pair<std::string_view, std::string_view> const> const connections)
130 2 : : _calls(std::make_shared<CallQueue>()) {
131 :
132 2 : auto [it, inserted] =
133 2 : _modules.emplace("broadcaster", std::make_unique<BroadcastModule>("broadcaster", _calls));
134 2 : ASSUME(inserted);
135 2 : _broadcaster = dynamic_cast<BroadcastModule *>(it->second.get());
136 2 : ASSUME(_broadcaster);
137 :
138 2 : for (auto const m : flipFlopModules)
139 96 : _modules.emplace(m, std::make_unique<FlipFlopModule>(m, _calls));
140 :
141 2 : for (auto const m : conjunctionModules)
142 18 : _modules.emplace(m, std::make_unique<ConjunctionModule>(m, _calls));
143 :
144 218 : for (auto const &c : connections) {
145 218 : auto senderIt = _modules.find(c.first);
146 218 : ASSUME(senderIt != _modules.end());
147 218 : auto receiverIt = _modules.find(c.second);
148 218 : if (receiverIt == _modules.end()) {
149 2 : receiverIt =
150 2 : _modules.emplace(c.second, std::make_unique<OutputModule>(c.second, _calls)).first;
151 2 : }
152 218 : Module::connect(senderIt->second.get(), receiverIt->second.get());
153 218 : }
154 2 : }
155 :
156 5013 : void pushButton() {
157 5013 : ++_loCtr;
158 5013 : _broadcaster->receiveSignal(nullptr, LO);
159 324636 : while (!_calls->empty()) {
160 319623 : auto [sender, receiver, signal] = _calls->front();
161 319623 : if (signal == HI)
162 234618 : ++_hiCtr;
163 85005 : else
164 85005 : ++_loCtr;
165 319623 : receiver->receiveSignal(sender, signal);
166 319623 : _calls->pop();
167 319623 : }
168 5013 : }
169 :
170 1 : [[nodiscard]] auto ctrs() const { return std::make_tuple(_hiCtr, _loCtr); }
171 :
172 1 : Module *findModule(std::string_view const name) {
173 1 : auto it = _modules.find(name);
174 1 : if (it == _modules.end())
175 0 : return nullptr;
176 1 : return it->second.get();
177 1 : }
178 :
179 : private:
180 : std::shared_ptr<CallQueue> _calls;
181 : std::map<std::string_view, std::unique_ptr<Module>> _modules;
182 : BroadcastModule *_broadcaster;
183 : size_t _hiCtr = 0;
184 : size_t _loCtr = 0;
185 : };
186 :
187 2 : Network parse(std::string_view const input) {
188 2 : static const RE2 frontPattern("([%&]?)([a-z]+) -> ");
189 2 : static const RE2 listPattern(" ?([a-z]+),?");
190 2 : LinewiseInput lines(input);
191 2 : std::vector<std::string_view> conjunctionModules;
192 2 : std::vector<std::string_view> flipFlopModules;
193 2 : std::vector<std::pair<std::string_view, std::string_view>> connections;
194 :
195 116 : for (auto line : lines) {
196 116 : std::string_view c;
197 116 : std::string_view name;
198 116 : ASSUME(RE2::Consume(&line, frontPattern, &c, &name));
199 116 : std::string_view outputName;
200 116 : std::vector<std::string_view> outputs;
201 334 : while (RE2::Consume(&line, listPattern, &outputName))
202 218 : outputs.push_back(outputName);
203 :
204 116 : if (c == "%") {
205 96 : flipFlopModules.push_back(name);
206 96 : } else if (c == "&") {
207 18 : conjunctionModules.push_back(name);
208 18 : }
209 116 : for (auto const &output : outputs)
210 218 : connections.emplace_back(name, output);
211 116 : }
212 :
213 2 : return {flipFlopModules, conjunctionModules, connections};
214 2 : }
215 :
216 : } // namespace
217 :
218 1 : template <> size_t part1<2023, 20>(std::string_view const input) {
219 1 : Network network = parse(input);
220 :
221 1001 : for (int i = 0; i < 1000; ++i)
222 1000 : network.pushButton();
223 :
224 1 : auto [hiCtr, loCtr] = network.ctrs();
225 :
226 1 : return hiCtr * loCtr;
227 1 : }
228 :
229 1 : template <> size_t part2<2023, 20>(std::string_view const input) {
230 1 : Network network = parse(input);
231 :
232 1 : auto *const hj = dynamic_cast<ConjunctionModule *>(network.findModule("hj"));
233 1 : ASSUME(hj);
234 1 : std::map<std::string_view, size_t> cycleLengths;
235 1 : size_t loopCtr = 1;
236 4 : hj->registerHiCallback([&cycleLengths, &loopCtr](std::string_view name) {
237 4 : auto it = cycleLengths.find(name);
238 4 : if (it == cycleLengths.end())
239 4 : cycleLengths.emplace(name, loopCtr);
240 0 : else
241 4 : ASSUME(loopCtr % it->second == 0);
242 4 : });
243 :
244 1 : size_t numInputs = hj->numInputs();
245 :
246 4014 : while (cycleLengths.size() != numInputs) {
247 4013 : network.pushButton();
248 4013 : ++loopCtr;
249 4013 : }
250 :
251 1 : return std::transform_reduce(
252 1 : cycleLengths.begin(), cycleLengths.end(), size_t(1),
253 4 : [](size_t lhs, size_t rhs) { return std::lcm(lhs, rhs); },
254 4 : [](auto const &p) { return p.second; });
255 1 : }
|
