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              : 
       9              : namespace {
      10              : 
      11              : struct Calibration {
      12              :   uint64_t result;
      13              :   std::vector<uint64_t> operands;
      14              : };
      15              : 
      16            2 : auto parse(std::string_view const input) {
      17            2 :   std::vector<Calibration> result;
      18         1700 :   for (auto l : getLineWise(input)) {
      19         1700 :     auto it = std::ranges::find(l, ':');
      20         1700 :     ASSERT(it != l.end());
      21         1700 :     std::string_view resultStr(l.begin(), it);
      22         1700 :     std::string_view numberStr(std::next(it, 2), l.end());
      23              : 
      24         1700 :     result.push_back({parseInt<uint64_t>(resultStr), parseIntegerRange<uint64_t>(numberStr, ' ')});
      25         1700 :   }
      26              : 
      27            2 :   return result;
      28            2 : }
      29              : 
      30      2735950 : uint64_t concat(uint64_t const lhs, uint64_t const rhs) {
      31      2735950 :   uint64_t n = 1;
      32      6469265 :   while (n <= rhs)
      33      3733315 :     n *= 10u;
      34      2735950 :   return lhs * n + rhs;
      35      2735950 : }
      36              : 
      37              : bool isValidPt1(uint64_t const expectedResult, uint64_t const intermediateResult,
      38       327501 :                 std::span<uint64_t const> const operands) {
      39              : 
      40       327501 :   if (intermediateResult > expectedResult)
      41        21114 :     return false;
      42       306387 :   if (operands.empty())
      43       142670 :     return intermediateResult == expectedResult;
      44              : 
      45       163717 :   std::span<uint64_t const> const tail{std::next(operands.begin()), operands.end()};
      46       163717 :   return isValidPt1(expectedResult, intermediateResult * operands.front(), tail) ||
      47       163717 :          isValidPt1(expectedResult, intermediateResult + operands.front(), tail);
      48       306387 : }
      49              : 
      50              : bool isValidPt2(uint64_t const expectedResult, uint64_t const intermediateResult,
      51      8212091 :                 std::span<uint64_t const> const operands) {
      52              : 
      53      8212091 :   if (intermediateResult > expectedResult)
      54      1551279 :     return false;
      55      6660812 :   if (operands.empty())
      56      3922619 :     return intermediateResult == expectedResult;
      57              : 
      58      2738193 :   std::span<uint64_t const> const tail{std::next(operands.begin()), operands.end()};
      59      2738193 :   return isValidPt2(expectedResult, intermediateResult * operands.front(), tail) ||
      60      2738193 :          isValidPt2(expectedResult, intermediateResult + operands.front(), tail) ||
      61      2738193 :          isValidPt2(expectedResult, concat(intermediateResult, operands.front()), tail);
      62      6660812 : }
      63              : 
      64              : } // namespace
      65              : 
      66            1 : template <> size_t part1<2024, 7>(std::string_view const input) {
      67            1 :   std::vector<Calibration> calibrations = parse(input);
      68              : 
      69            1 :   uint64_t result = 0;
      70          850 :   for (auto &c : calibrations) {
      71          850 :     if (isValidPt1(c.result, c.operands.front(), {std::next(c.operands.begin()), c.operands.end()}))
      72          252 :       result += c.result;
      73          850 :   }
      74            1 :   return result;
      75            1 : }
      76              : 
      77            1 : template <> size_t part2<2024, 7>(std::string_view const input) {
      78            1 :   std::vector<Calibration> calibrations = parse(input);
      79              : 
      80            1 :   uint64_t result = 0;
      81          850 :   for (auto &c : calibrations) {
      82          850 :     if (isValidPt2(c.result, c.operands.front(), {std::next(c.operands.begin()), c.operands.end()}))
      83          432 :       result += c.result;
      84          850 :   }
      85            1 :   return result;
      86            1 : }