Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "IntegerCast.h"
       4              : #include "Parsing.h"
       5              : #include "Views.h"
       6              : #include "mdspan.hpp"
       7              : 
       8              : #include <algorithm>
       9              : #include <cstddef>
      10              : #include <map>
      11              : #include <set>
      12              : #include <string>
      13              : #include <string_view>
      14              : #include <vector>
      15              : 
      16              : using namespace std::literals;
      17              : 
      18              : namespace {
      19              : 
      20      7148000 : uint64_t next(uint64_t n) {
      21      7148000 :   constexpr uint64_t modulo = 16777216u;
      22      7148000 :   n ^= n << 6u;
      23      7148000 :   n %= modulo;
      24      7148000 :   n ^= n >> 5u;
      25      7148000 :   n %= modulo;
      26      7148000 :   n ^= n << 11u;
      27      7148000 :   return n % modulo;
      28      7148000 : }
      29              : 
      30              : } // namespace
      31              : 
      32            1 : template <> std::string solvePart1<2024, 22>(std::string_view const input) {
      33            1 :   std::vector<uint64_t> secretNumbers = parseIntegerRange<uint64_t>(input, '\n');
      34              : 
      35            1 :   for (auto &n : secretNumbers)
      36      3575787 :     for (unsigned i = 0; i < 2000; ++i) {
      37      3574000 :       n = next(n);
      38      3574000 :     }
      39              : 
      40            1 :   return std::to_string(std::ranges::fold_left(secretNumbers, uint64_t(0), std::plus{}));
      41            1 : }
      42              : 
      43            1 : template <> std::string solvePart2<2024, 22>(std::string_view const input) {
      44            1 :   std::vector<uint64_t> secretNumbers = parseIntegerRange<uint64_t>(input, '\n');
      45              : 
      46            1 :   using Extents = std::extents<int, 19u, 19u, 19u, 19u>;
      47            1 :   std::array<bool, integerCast<std::size_t>(19u * 19u * 19u * 19u)> priceChangesSeenData{};
      48            1 :   std::mdspan<bool, Extents> priceChangesSeen(priceChangesSeenData.data());
      49            1 :   priceChangesSeen = std::mdspan<bool, Extents>(&priceChangesSeen[9, 9, 9, 9]);
      50              : 
      51            1 :   std::array<int, integerCast<std::size_t>(19u * 19u * 19u * 19u)> seqPricesData{};
      52            1 :   std::mdspan<int, Extents> seqPrices(seqPricesData.data());
      53            1 :   seqPrices = std::mdspan<int, Extents>(&seqPrices[9, 9, 9, 9]);
      54              : 
      55         1787 :   for (auto &n : secretNumbers) {
      56         1787 :     std::ranges::fill(priceChangesSeenData, false);
      57         1787 :     int8_t lastPrice = 0;
      58         1787 :     std::array<int8_t, 4u> priceDelta{};
      59      3575787 :     for (unsigned i = 0; i < 2000; ++i) {
      60      3574000 :       n = next(n);
      61      3574000 :       auto const price = integerCast<int8_t>(n % 10);
      62      3574000 :       std::ranges::rotate(priceDelta, std::next(priceDelta.begin()));
      63      3574000 :       priceDelta.back() = integerCast<int8_t>(lastPrice - price);
      64      3574000 :       lastPrice = price;
      65              : 
      66      3574000 :       if (i > 3 && !priceChangesSeen[priceDelta]) {
      67      3448949 :         priceChangesSeen[priceDelta] = true;
      68      3448949 :         seqPrices[priceDelta] += price;
      69      3448949 :       }
      70      3574000 :     }
      71         1787 :   }
      72            1 :   return std::to_string(std::ranges::max(seqPricesData));
      73            1 : }