13
๐ - 2023 DAY 20 SOLUTIONS - ๐
(programming.dev)
C++, kind of
Ok so this is a little weird. My code for task1 is attached to this comment, but I actually solved task2 by hand. After checking that bruteforce indeed takes longer than a second, I plotted the graph just to see what was going on, and you can immediately tell that the result is the least common multiple of four numbers, which can easily be obtained by running task1 with a debugger, and maybe read directly from the graph as well. I also pre-broke my include statements, so hopefully the XSS protection isn't completely removing them again.
My graph: https://files.catbox.moe/1u4daw.png
blue is the broadcaster/button, yellows are flipflops, purples are nand gates and green is the output gate.
Also I abandoned scala again, because there is so much state modification going on.
#include fstream>
#include memory>
#include algorithm>
#include optional>
#include stdexcept>
#include set>
#include vector>
#include map>
#include deque>
#include unordered_map>
#include fmt/format.h>
#include fmt/ranges.h>
#include flux.hpp>
#include scn/all.h>
#include scn/scan/list.h>
enum Pulse { Low=0, High };
struct Module {
std::string name;
Module(std::string _name) : name(std::move(_name)) {}
virtual std::optional handle(Module const& from, Pulse type) = 0;
virtual ~Module() = default;
};
struct FlipFlop : public Module {
using Module::Module;
bool on = false;
std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
if(type == Low) {
on = !on;
return on ? High : Low;
}
return {};
}
virtual ~FlipFlop() = default;
};
struct Nand : public Module {
using Module::Module;
std::unordered_map last;
std::optional handle(Module const& from, Pulse type) override {
last[from.name] = type;
for(auto& [k, v] : last) {
if (v == Low) {
return High;
}
}
return Low;
}
virtual ~Nand() = default;
};
struct Broadcaster : public Module {
using Module::Module;
std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
return type;
}
virtual ~Broadcaster() = default;
};
struct Sink : public Module {
using Module::Module;
std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
return {};
}
virtual ~Sink() = default;
};
struct Button : public Module {
using Module::Module;
std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
throw std::runtime_error{"Button should never recv signal"};
}
virtual ~Button() = default;
};
void run(Module* button, std::map> connections, long& lows, long& highs) {
std::deque> pending;
pending.push_back({button, Low});
while(!pending.empty()) {
auto [m, p] = pending.front();
pending.pop_front();
for(auto& m2 : connections.at(m->name)) {
++(p == Low ? lows : highs);
fmt::println("{} -{}-> {}", m->name, p == Low ? "low":"high", m2->name);
if(auto p2 = m2->handle(*m, p)) {
pending.push_back({m2, *p2});
}
}
}
}
struct Setup {
std::vector> modules;
std::map by_name;
std::map> connections;
};
Setup parse(std::string path) {
std::ifstream in(path);
Setup res;
auto lines = flux::getlines(in).to>();
std::map> pre_connections;
for(const auto& line : lines) {
std::string name;
if(auto r = scn::scan(line, "{} -> ", name)) {
if(name == "broadcaster") {
res.modules.push_back(std::make_unique(name));
}
else if(name.starts_with('%')) {
name = name.substr(1);
res.modules.push_back(std::make_unique(name));
}
else if(name.starts_with('&')) {
name = name.substr(1);
res.modules.push_back(std::make_unique(name));
}
res.by_name[name] = res.modules.back().get();
std::vector cons;
if(auto r2 = scn::scan_list_ex(r.range(), cons, scn::list_separator(','))) {
for(auto& c : cons) if(c.ends_with(',')) c.pop_back();
fmt::println("name={}, rest={}", name, cons);
pre_connections[name] = cons;
} else {
throw std::runtime_error{r.error().msg()};
}
} else {
throw std::runtime_error{r.error().msg()};
}
}
res.modules.push_back(std::make_unique("sink"));
for(auto& [k, v] : pre_connections) {
res.connections[k] = flux::from(std::move(v)).map([&](std::string s) {
try {
return res.by_name.at(s);
} catch(std::out_of_range const& e) {
fmt::print("out of range at {}\n", s);
return res.modules.back().get();
}}).to>();
}
res.modules.push_back(std::make_unique("button"));
res.connections["button"] = {res.by_name.at("broadcaster")};
res.connections["sink"] = {};
for(auto& [m, cs] : res.connections) {
for(auto& m2 : cs) {
if(auto nand = dynamic_cast(m2)) {
nand->last[m] = Low;
}
}
}
return res;
}
int main(int argc, char* argv[]) {
auto setup = parse(argc > 1 ? argv[1] : "../task1.txt");
long lows{}, highs{};
for(int i = 0; i < 1000; ++i)
run(setup.modules.back().get(), setup.connections, lows, highs);
fmt::println("task1: low={} high={} p={}", lows, highs, lows*highs);
}
My graph: https://files.catbox.moe/1u4daw.png
blue is the broadcaster/button, yellows are flipflops, purples are nand gates and green is the output gate.