Line data    Source code

       1              : #include "IntegerCast.h"
       2              : #include "LinewiseInput.h"
       3              : #include "Parsing.h"
       4              : #include "PuzzleImpl.h"
       5              : 
       6              : #include <libassert/assert.hpp>
       7              : 
       8              : #include <cstdint>
       9              : #include <numeric>
      10              : #include <string>
      11              : #include <string_view>
      12              : 
      13              : namespace {
      14              : 
      15          200 : int64_t extrapolateMeasurementBack(std::string_view const measurement) {
      16          200 :   std::vector<int64_t> derivativesBuffer = parseRange<int64_t>(measurement);
      17          200 :   std::span<int64_t> derivatives(derivativesBuffer);
      18              : 
      19          200 :   int64_t result = derivatives.back();
      20          200 :   bool allZero = false;
      21         2372 :   while (!allZero) {
      22         2172 :     DEBUG_ASSERT(derivatives.size() > 1U);
      23         2172 :     allZero = true;
      24        32356 :     for (size_t i = 1; i < derivatives.size(); ++i) {
      25        30184 :       derivatives[i - 1] = derivatives[i] - derivatives[i - 1];
      26        30184 :       allZero = allZero && derivatives[i - 1] == 0;
      27        30184 :     }
      28         2172 :     derivatives = std::span(derivatives.data(), derivatives.size() - 1u);
      29         2172 :     result += derivatives.back();
      30         2172 :   }
      31          200 :   return result;
      32          200 : }
      33              : 
      34          200 : int64_t extrapolateMeasurementFront(std::string_view const measurement) {
      35          200 :   std::vector<int64_t> derivativesBuffer = parseRange<int64_t>(measurement);
      36          200 :   std::span<int64_t> derivatives(derivativesBuffer);
      37              : 
      38          200 :   int64_t result = derivatives.front();
      39          200 :   bool allZero = false;
      40          200 :   int64_t sign = -1;
      41         2372 :   while (!allZero) {
      42         2172 :     DEBUG_ASSERT(derivatives.size() > 1U);
      43         2172 :     allZero = true;
      44        32356 :     for (size_t i = 1; i < derivatives.size(); ++i) {
      45        30184 :       derivatives[i - 1] = derivatives[i] - derivatives[i - 1];
      46        30184 :       allZero = allZero && derivatives[i - 1] == 0;
      47        30184 :     }
      48         2172 :     derivatives = std::span(derivatives.data(), derivatives.size() - 1u);
      49         2172 :     result += sign * derivatives.front();
      50         2172 :     sign *= -1;
      51         2172 :   }
      52          200 :   return result;
      53          200 : }
      54              : 
      55              : } // namespace
      56              : 
      57            1 : template <> std::string solvePart1<2023, 9>(std::string_view const input) {
      58            1 :   LinewiseInput const lines(input);
      59              : 
      60            1 :   return std::to_string(std::transform_reduce(lines.begin(), lines.end(), int64_t(0), std::plus<>(),
      61            1 :                                               extrapolateMeasurementBack));
      62            1 : }
      63              : 
      64            1 : template <> std::string solvePart2<2023, 9>(std::string_view const input) {
      65            1 :   LinewiseInput const lines(input);
      66              : 
      67            1 :   return std::to_string(std::transform_reduce(lines.begin(), lines.end(), int64_t(0), std::plus<>(),
      68            1 :                                               extrapolateMeasurementFront));
      69            1 : }