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();
}