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