Line data    Source code

       1              : #include "LinewiseInput.h"
       2              : #include "Parsing.h"
       3              : #include "PuzzleImpl.h"
       4              : 
       5              : #include <libassert/assert.hpp>
       6              : 
       7              : #include <algorithm>
       8              : #include <numeric>
       9              : #include <vector>
      10              : 
      11              : namespace {
      12              : 
      13              : template <class InputIt1, class InputIt2>
      14          402 : size_t countingSetIntersection(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) {
      15          402 :   size_t ctr = 0;
      16        11868 :   while (first1 != last1 && first2 != last2) {
      17        11466 :     if (*first1 < *first2)
      18         2194 :       ++first1;
      19         9272 :     else {
      20         9272 :       if (!(*first2 < *first1)) {
      21         1744 :         ++ctr;
      22         1744 :         ++first1;
      23         1744 :       }
      24         9272 :       ++first2;
      25         9272 :     }
      26        11466 :   }
      27          402 :   return ctr;
      28          402 : }
      29              : 
      30          402 : size_t checkCard(std::string_view cardString) {
      31          402 :   auto colonIt = std::ranges::find(cardString, ':');
      32          402 :   ASSUME(colonIt != cardString.end());
      33          402 :   auto pipeIt = std::find(colonIt, cardString.end(), '|');
      34          402 :   ASSUME(pipeIt != cardString.end());
      35              : 
      36          402 :   std::string_view const winningNumbersStr(std::next(colonIt), pipeIt);
      37          402 :   std::vector<unsigned> winningNumbers = parseRange<unsigned>(winningNumbersStr);
      38              : 
      39          402 :   std::string_view const ownNumbersStr(std::next(pipeIt), cardString.end());
      40          402 :   std::vector<unsigned> ownNumbers = parseRange<unsigned>(ownNumbersStr);
      41              : 
      42          402 :   std::ranges::sort(winningNumbers);
      43          402 :   std::ranges::sort(ownNumbers);
      44              : 
      45          402 :   return countingSetIntersection(winningNumbers.begin(), winningNumbers.end(), ownNumbers.begin(),
      46          402 :                                  ownNumbers.end());
      47          402 : }
      48              : 
      49              : } // namespace
      50              : 
      51            1 : template <> size_t part1<2023, 4>(std::string_view const input) {
      52            1 :   LinewiseInput const lines(input);
      53              : 
      54            1 :   return std::transform_reduce(lines.begin(), lines.end(), size_t(0), std::plus<>(),
      55          201 :                                [](std::string_view const s) {
      56          201 :                                  size_t const matches = checkCard(s);
      57          201 :                                  return matches == 0u ? 0u : (1 << (matches - 1u));
      58          201 :                                });
      59            1 : }
      60              : 
      61            1 : template <> size_t part2<2023, 4>(std::string_view const input) {
      62            1 :   LinewiseInput const lines(input);
      63              : 
      64            1 :   std::vector<size_t> matches(lines.size());
      65              : 
      66            1 :   std::ranges::transform(lines, matches.begin(), checkCard);
      67              : 
      68            1 :   std::vector<size_t> instances(lines.size(), 1u);
      69          202 :   for (size_t i = 0u; i < matches.size(); ++i) {
      70         1073 :     for (size_t j = 1u; j <= matches[i] && i + j < instances.size(); ++j) {
      71          872 :       instances[i + j] += instances[i];
      72          872 :     }
      73          201 :   }
      74              : 
      75            1 :   return std::reduce(instances.begin(), instances.end());
      76            1 : }