C++

BFS for part 1, “Z3 of shame” for part 2. On the plus side, it’s not that goddamned hailstones question from 2023 day 24 again. On the minus side, if I wanted to be reminded how bad I am at maths, then I could head on over to Project Euler and struggle with the questions there.

Z3 is incredibly fast. Well done, Microsoft research.

#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>
#include <z3++.h>

namespace {

using Button = boost::unordered::unordered_flat_set<size_t>;
using Joltage = std::vector<int>;

struct Machine {
  std::string pattern;
  std::vector<Button> buttons;
  Joltage joltage;
};

using Machines = std::vector<Machine>;
using PatternCount = boost::unordered::unordered_flat_map<std::string, size_t>;

auto parse_button(const std::string &in) {
  auto rval = Button{};
  auto start = size_t{};
  while (start < in.size()) {
    auto comma = in.find(',', start);
    if (comma == std::string::npos)
      comma = in.size();
    rval.insert(std::stoull(in.substr(start, comma - start)));
    start = comma + 1;
  }
  return rval;
}

auto parse_joltage(const std::string &in) {
  auto rval = Joltage{};
  auto start = size_t{};
  while (start < in.size()) {
    auto comma = in.find(',', start);
    if (comma == std::string::npos)
      comma = in.size();
    rval.push_back(std::stoi(in.substr(start, comma - start)));
    start = comma + 1;
  }
  return rval;
}

auto read() {
  auto rval = Machines{};
  auto ih = std::ifstream{"10.txt"};
  if (!ih)
    throw std::runtime_error{"file?"};
  auto line = std::string{};
  while (std::getline(ih, line)) {
    auto m = Machine{};
    auto ss = std::istringstream{line};
    auto str = std::string{};
    ss >> m.pattern;
    m.pattern = m.pattern.substr(1, m.pattern.size() - 2);
    while (ss >> str) {
      if (str.at(0) == '(')
        m.buttons.push_back(parse_button(str.substr(1, str.size() - 2)));
      else
        m.joltage = parse_joltage(str.substr(1, str.size() - 2));
    }
    rval.push_back(std::move(m));
  }
  return rval;
}

auto minimum_presses(const Machine &m) {
  auto presses = size_t{};
  auto pattern = PatternCount{};
  auto first = std::string(m.pattern.size(), '.');
  auto next_iter = std::vector<std::string>{};

  pattern[first] = 0;
  next_iter.push_back(first);

  while (true) {
    auto this_iter = next_iter;
    next_iter.clear();
    ++presses;

    for (auto &iter : this_iter) {
      for (auto &button : m.buttons) {
        auto copy = iter;
        for (auto toggle : button)
          copy[toggle] = copy[toggle] == '.' ? '#' : '.';
        if (copy == m.pattern)
          return presses;
        if (auto f = pattern.find(copy); f != pattern.end())
          continue;
        pattern[copy] = presses;
        next_iter.push_back(std::move(copy));
      }
    }
  }
}

auto part1(const Machines &machines) {
  auto rval = size_t{};
  for (const auto &machine : machines)
    rval += minimum_presses(machine);
  return rval;
}

auto solve(const Machine &m) {
  z3::context context;
  z3::optimize opt(context);

  auto array = std::vector<z3::expr>{};
  auto sum = z3::expr{context.int_val(0)};
  for (auto i = size_t{}; i < m.buttons.size(); ++i) {
    auto name = std::string{"a"};
    name[0] += i;
    auto x = context.int_const(name.c_str());
    opt.add(x >= 0);
    sum = sum + x;
    array.push_back(std::move(x));
  }
  auto z = context.int_const("z");
  opt.add(sum == z);

  for (auto joltage = size_t{}; joltage < m.joltage.size(); ++joltage) {
    auto ex = z3::expr{context.int_val(0)};
    for (auto button = size_t{}; button < m.buttons.size(); ++button) {
      if (m.buttons.at(button).contains(joltage))
        ex = ex + array.at(button);
    }
    opt.add(ex == m.joltage.at(joltage));
  }

  z3::optimize::handle handle = opt.minimize(z);
  opt.check();
  return opt.lower(handle).as_uint64();
}

auto part2(const Machines &machines) {
  auto total = size_t{};
  for (auto &machine : machines)
    total += solve(machine);
  return total;
}

} // namespace

auto main() -> int {
  auto machine = read();
  BOOST_LOG_TRIVIAL(info) << "Day 10: read " << machine.size();
  BOOST_LOG_TRIVIAL(info) << "1: " << part1(machine);
  BOOST_LOG_TRIVIAL(info) << "2: " << part2(machine);
}