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_view>
      11              : 
      12              : namespace {
      13              : 
      14          200 : int64_t extrapolateMeasurementBack(std::string_view const measurement) {
      15          200 :   std::vector<int64_t> derivativesBuffer = parseRange<int64_t>(measurement);
      16          200 :   std::span<int64_t> derivatives(derivativesBuffer);
      17              : 
      18          200 :   int64_t result = derivatives.back();
      19          200 :   bool allZero = false;
      20         2372 :   while (!allZero) {
      21         2172 :     DEBUG_ASSERT(derivatives.size() > 1U);
      22         2172 :     allZero = true;
      23        32356 :     for (size_t i = 1; i < derivatives.size(); ++i) {
      24        30184 :       derivatives[i - 1] = derivatives[i] - derivatives[i - 1];
      25        30184 :       allZero = allZero && derivatives[i - 1] == 0;
      26        30184 :     }
      27         2172 :     derivatives = std::span(derivatives.data(), derivatives.size() - 1u);
      28         2172 :     result += derivatives.back();
      29         2172 :   }
      30          200 :   return result;
      31          200 : }
      32              : 
      33          200 : int64_t extrapolateMeasurementFront(std::string_view const measurement) {
      34          200 :   std::vector<int64_t> derivativesBuffer = parseRange<int64_t>(measurement);
      35          200 :   std::span<int64_t> derivatives(derivativesBuffer);
      36              : 
      37          200 :   int64_t result = derivatives.front();
      38          200 :   bool allZero = false;
      39          200 :   int64_t sign = -1;
      40         2372 :   while (!allZero) {
      41         2172 :     DEBUG_ASSERT(derivatives.size() > 1U);
      42         2172 :     allZero = true;
      43        32356 :     for (size_t i = 1; i < derivatives.size(); ++i) {
      44        30184 :       derivatives[i - 1] = derivatives[i] - derivatives[i - 1];
      45        30184 :       allZero = allZero && derivatives[i - 1] == 0;
      46        30184 :     }
      47         2172 :     derivatives = std::span(derivatives.data(), derivatives.size() - 1u);
      48         2172 :     result += sign * derivatives.front();
      49         2172 :     sign *= -1;
      50         2172 :   }
      51          200 :   return result;
      52          200 : }
      53              : 
      54              : } // namespace
      55              : 
      56            1 : template <> size_t part1<2023, 9>(std::string_view const input) {
      57            1 :   LinewiseInput const lines(input);
      58              : 
      59            1 :   return integerCast<size_t>(std::transform_reduce(lines.begin(), lines.end(), int64_t(0),
      60            1 :                                                    std::plus<>(), extrapolateMeasurementBack));
      61            1 : }
      62              : 
      63            1 : template <> size_t part2<2023, 9>(std::string_view const input) {
      64            1 :   LinewiseInput const lines(input);
      65              : 
      66            1 :   return integerCast<size_t>(std::transform_reduce(lines.begin(), lines.end(), int64_t(0),
      67            1 :                                                    std::plus<>(), extrapolateMeasurementFront));
      68            1 : }