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