C++
Dynamic programming and recursion - it's the AoC classic. Nothing tricky here, which is a relief after yesterday.
No sign of Dijkstra's yet, which is a surprise. Maybe it'll be tomorrow's puzzle? 25th is usually an open goal if you've done the rest of the puzzles, but I don't know if that applies to the new shorter format.
#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_map.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <vector>
namespace {
using Map =
boost::unordered::unordered_flat_map<std::string, std::vector<std::string>>;
auto read(const std::string &name) {
auto rval = Map{};
auto ih = std::ifstream{name};
if (!ih)
throw std::runtime_error{"file?"};
auto line = std::string{};
while (std::getline(ih, line)) {
auto ss = std::istringstream{line};
auto tmp = std::string{};
ss >> tmp;
auto key = tmp.substr(0, tmp.size() - 1);
auto value = std::vector<std::string>{};
while (ss >> tmp)
value.push_back(std::move(tmp));
rval[key] = std::move(value);
}
return rval;
}
auto part1() {
auto map = read("11.1.txt");
auto current = std::vector<std::vector<std::string>>{};
auto paths = boost::unordered::unordered_flat_set<std::vector<std::string>>{};
current.push_back(std::vector<std::string>{"you"});
while (!current.empty()) {
auto next_up = decltype(current){};
std::swap(current, next_up);
for (const auto &next : next_up) {
auto &outputs = map.at(next.back());
for (auto &output : outputs) {
if (output == "you")
continue;
auto token = next;
token.push_back(output);
if (output == "out") {
paths.insert(std::move(token));
} else {
current.push_back(std::move(token));
}
}
}
}
return paths.size();
}
struct Route {
std::string current;
bool has_fft, has_dac;
};
struct RouteHash {
std::size_t operator()(const Route &p) const {
std::size_t seed = 0;
boost::hash_combine(seed, p.current);
boost::hash_combine(seed, p.has_fft);
boost::hash_combine(seed, p.has_dac);
return seed;
}
};
auto operator==(const Route &a, const Route &b) {
return a.current == b.current && a.has_fft == b.has_fft &&
a.has_dac == b.has_dac;
}
auto cache = boost::unordered::unordered_flat_map<Route, size_t, RouteHash>{};
auto count_target(Route start, const Map &map) -> size_t {
auto outputs = map.at(start.current);
if (start.current == "dac")
start.has_dac = true;
if (start.current == "fft")
start.has_fft = true;
auto rval = size_t{};
for (auto &output : outputs) {
if (auto f = cache.find({output, start.has_fft, start.has_dac});
f != cache.end()) {
rval += f->second;
continue;
}
if (output == "out") {
if (start.has_dac && start.has_fft) {
++rval;
}
continue;
}
rval += count_target({output, start.has_fft, start.has_dac}, map);
}
cache[start] = rval;
return rval;
}
auto part2() {
auto map = read("11.2.txt");
return count_target({"svr", false, false}, map);
}
} // namespace
auto main() -> int {
BOOST_LOG_TRIVIAL(info) << "Day 11";
BOOST_LOG_TRIVIAL(info) << "1: " << part1();
BOOST_LOG_TRIVIAL(info) << "2: " << part2();
}