Line data    Source code

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