#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";
}