72 lines
1.4 KiB
C++
72 lines
1.4 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 <string>
|
|
#include <string_view>
|
|
#include <tuple>
|
|
#include <vector>
|
|
|
|
namespace qi = boost::spirit::qi;
|
|
|
|
using std::istream;
|
|
using std::ostream;
|
|
using std::size_t;
|
|
using std::string;
|
|
using std::string_view;
|
|
using std::tuple;
|
|
using std::uint64_t;
|
|
using std::vector;
|
|
|
|
namespace
|
|
{
|
|
|
|
auto ways(const vector<string> &towels, const string &design) -> uint64_t
|
|
{
|
|
const auto n = design.size();
|
|
vector<uint64_t> counts(n + 1);
|
|
counts[0] = 1;
|
|
|
|
for (size_t i = 0; i < n; i++)
|
|
{
|
|
string_view const suffix{begin(design) + i, end(design)};
|
|
for (auto &&towel : towels)
|
|
{
|
|
if (suffix.starts_with(towel))
|
|
{
|
|
counts[i + towel.size()] += counts[i];
|
|
}
|
|
}
|
|
}
|
|
|
|
return counts.back();
|
|
}
|
|
|
|
} // namespace
|
|
|
|
auto Main(istream &in, ostream &out) -> void
|
|
{
|
|
const auto [towels, designs] =
|
|
aocpp::ParseSimple
|
|
<tuple<vector<string>, vector<string>>>
|
|
(in, +qi::alpha % ", " >> "\n\n" >> *(+qi::alpha >> "\n"));
|
|
|
|
uint64_t p1 = 0, p2 = 0;
|
|
for (auto &&design : designs)
|
|
{
|
|
const auto n = ways(towels, design);
|
|
if (n > 0)
|
|
{
|
|
p1++;
|
|
}
|
|
p2 += n;
|
|
}
|
|
|
|
out << "Part 1: " << p1 << "\n"
|
|
<< "Part 2: " << p2 << "\n";
|
|
}
|