Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Views.h"
       4              : 
       5              : #include <algorithm>
       6              : #include <map>
       7              : #include <ranges>
       8              : #include <string>
       9              : #include <string_view>
      10              : #include <vector>
      11              : 
      12              : using namespace std::literals;
      13              : 
      14              : namespace {
      15              : 
      16              : auto parse(std::string_view const input) {
      17              :   auto lines = input | views::split('\n');
      18              : 
      19          894 :   return std::make_tuple(lines.front() | views::split(", "sv) | views::transform([](auto &&r) {
      20          894 :                            return std::string_view(r);
      21          894 :                          }) | std::ranges::to<std::vector<std::string_view>>(),
      22          800 :                          lines | views::drop(2) | views::transform([](auto &&r) {
      23          800 :                            return std::string_view(r);
      24          800 :                          }) | std::ranges::to<std::vector<std::string_view>>());
      25              : }
      26              : 
      27              : struct Tester {
      28              : 
      29            2 :   Tester(std::vector<std::string_view> const &prefixes) : _prefixes(&prefixes) {}
      30              : 
      31       107148 :   size_t operator()(std::string_view word) {
      32       107148 :     if (word.empty())
      33          386 :       return true;
      34              : 
      35       106762 :     if (auto it = _cache.find(word); it != _cache.end())
      36        69676 :       return it->second;
      37              : 
      38     16577442 :     auto prefixFind = [&](std::string_view prefix) { return word.starts_with(prefix); };
      39              : 
      40        37086 :     auto it = std::ranges::find_if(*_prefixes, prefixFind);
      41              : 
      42        37086 :     size_t ctr = 0;
      43       143434 :     while (it != _prefixes->end()) {
      44       106348 :       ctr += (*this)(word | views::drop(it->size()));
      45              : 
      46       106348 :       ++it;
      47              : 
      48       106348 :       it = std::ranges::find_if(it, _prefixes->end(), prefixFind);
      49       106348 :     }
      50              : 
      51        37086 :     _cache.emplace(word, ctr);
      52        37086 :     return ctr;
      53       106762 :   }
      54              : 
      55              :   std::vector<std::string_view> const *_prefixes;
      56              :   std::map<std::string_view, size_t> _cache;
      57              : };
      58              : 
      59              : } // namespace
      60              : 
      61            1 : template <> std::string solvePart1<2024, 19>(std::string_view const input) {
      62            1 :   auto [prefixes, words] = parse(input);
      63            1 :   Tester t(prefixes);
      64              : 
      65          400 :   return std::to_string(std::ranges::count_if(words, [&](auto w) { return t(w) > 0; }));
      66            1 : }
      67              : 
      68            1 : template <> std::string solvePart2<2024, 19>(std::string_view const input) {
      69              : 
      70            1 :   auto [prefixes, words] = parse(input);
      71            1 :   Tester t(prefixes);
      72              : 
      73          400 :   auto counts = words | views::transform([&](auto w) { return t(w); });
      74              : 
      75            1 :   return std::to_string(std::ranges::fold_left(counts, size_t(0), std::plus{}));
      76            1 : }