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