85 lines
1.9 KiB
C++
85 lines
1.9 KiB
C++
#include <aocpp/Parsing.hpp>
|
|
#include <aocpp/Startup.hpp>
|
|
|
|
#include <boost/spirit/include/qi.hpp>
|
|
#include <boost/fusion/include/std_tuple.hpp>
|
|
|
|
#include <cstdint>
|
|
#include <iostream>
|
|
#include <optional>
|
|
#include <stack>
|
|
#include <tuple>
|
|
#include <vector>
|
|
|
|
namespace qi = boost::spirit::qi;
|
|
|
|
namespace {
|
|
|
|
auto try_subtract(std::uint64_t t, std::uint64_t x) -> std::optional<std::uint64_t> {
|
|
return x < t ? std::optional{t - x} : std::nullopt;
|
|
}
|
|
|
|
auto try_divide(std::uint64_t t, std::uint64_t x) -> std::optional<std::uint64_t> {
|
|
return t % x == 0 ? std::optional{t / x} : std::nullopt;
|
|
}
|
|
|
|
auto try_unsuffix(std::uint64_t x, std::uint64_t y) -> std::optional<std::uint64_t>
|
|
{
|
|
while (x > 0) {
|
|
if (y == 0) { return x; }
|
|
if (x % 10 != y % 10) return std::nullopt;
|
|
x /= 10;
|
|
y /= 10;
|
|
}
|
|
return std::nullopt;
|
|
}
|
|
|
|
auto calibrated(
|
|
std::uint64_t const target,
|
|
std::vector<std::uint64_t> const& numbers,
|
|
auto... ops
|
|
) -> bool
|
|
{
|
|
if (numbers.empty()) { return false; }
|
|
|
|
auto work = std::stack<std::tuple<std::size_t, std::uint64_t>>{};
|
|
work.emplace(numbers.size() - 1, target);
|
|
|
|
while (not work.empty())
|
|
{
|
|
auto const [i, t] = work.top();
|
|
work.pop();
|
|
auto const x = numbers[i];
|
|
if (i == 0) {
|
|
if (x == t) { return true; }
|
|
} else {
|
|
for (auto const op : {ops...}) {
|
|
if (auto const u = op(t, x)) {
|
|
work.emplace(i - 1, *u);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
} // namespace
|
|
|
|
auto Main(std::istream & in, std::ostream & out) -> void
|
|
{
|
|
auto const input =
|
|
aocpp::ParseSimple
|
|
<std::vector<std::tuple<std::uint64_t, std::vector<std::uint64_t>>>>
|
|
(in, *(qi::ulong_long >> ':' >> +(' ' >> qi::ulong_long) >> '\n'));
|
|
|
|
std::uint64_t p1 = 0, p2 = 0;
|
|
for (auto && [x, xs] : input) {
|
|
if (calibrated(x, xs, try_subtract, try_divide)) p1 += x;
|
|
if (calibrated(x, xs, try_subtract, try_divide, try_unsuffix)) p2 += x;
|
|
}
|
|
|
|
out << "Part 1: " << p1 << "\n"
|
|
<< "Part 2: " << p2 << "\n";
|
|
}
|