Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "IntegerCast.h"
       4              : #include "Parsing.h"
       5              : 
       6              : #include <charconv>
       7              : #include <re2/re2.h>
       8              : 
       9              : #include <string_view>
      10              : 
      11              : #include <vector>
      12              : 
      13              : namespace {
      14              : 
      15              : struct Range {
      16            0 :   [[nodiscard]] bool contains(uint64_t x) const { return x >= from && x <= to; }
      17              : 
      18              :   uint64_t from;
      19              :   uint64_t to;
      20              : };
      21              : 
      22            2 : std::vector<Range> parseRanges(std::string_view const input) {
      23            2 :   std::vector<std::string_view> rangeStrings = split(input);
      24            2 :   std::vector<Range> result;
      25            2 :   result.reserve(rangeStrings.size());
      26            2 :   RE2 re(R"((\d+)-(\d+))");
      27            2 :   uint64_t from = 0;
      28            2 :   uint64_t to = 0;
      29           60 :   for (std::string_view const line : rangeStrings) {
      30           60 :     ASSERT(RE2::FullMatch(line, re, &from, &to));
      31           60 :     result.emplace_back(from, to);
      32           60 :   }
      33            2 :   return result;
      34            2 : }
      35              : 
      36      2070328 : bool isInvalidPart1(uint64_t const x) {
      37      2070328 :   std::array<char, std::numeric_limits<uint64_t>::digits10> buf{};
      38      2070328 :   std::to_chars_result res = std::to_chars(buf.begin(), buf.end(), x);
      39      2070328 :   ASSERT(res.ec == std::errc());
      40      2070328 :   std::string_view const sv{buf.data(), integerCast<size_t>(res.ptr - buf.data())};
      41      2070328 :   std::string_view const firstPart(sv.substr(0, sv.size() / 2));
      42      2070328 :   std::string_view const secondPart(sv.substr(sv.size() / 2));
      43      2070328 :   return firstPart == secondPart;
      44      2070328 : }
      45              : 
      46      2070328 : bool isInvalidPart2(uint64_t const x) {
      47      2070328 :   std::array<char, std::numeric_limits<uint64_t>::digits10> buf{};
      48      2070328 :   std::to_chars_result res = std::to_chars(buf.begin(), buf.end(), x);
      49      2070328 :   ASSERT(res.ec == std::errc());
      50      2070328 :   std::string_view const sv{buf.data(), integerCast<size_t>(res.ptr - buf.data())};
      51      9586586 :   for(size_t subLen = 1; subLen <= sv.size() / 2; ++subLen)
      52      7516881 :   {
      53      7516881 :     if(sv.size() % subLen != 0)
      54      2651858 :       continue;
      55      4865023 :     std::string_view const firstSubStr(sv.substr(0, subLen));
      56      5503026 :     for(size_t pos = subLen; pos < sv.size(); pos += subLen)
      57      5503026 :     {
      58      5503026 :       std::string_view const nextSubStr(sv.substr(pos, subLen));
      59      5503026 :       if(firstSubStr != nextSubStr)
      60      4864400 :         break;
      61       638626 :       if(pos + subLen == sv.size())
      62          623 :         return true;
      63       638626 :     }
      64      4865023 :   }
      65      2069705 :   return false;
      66      2070328 : }
      67              : 
      68              : } // namespace
      69              : 
      70            1 : template <> std::string solvePart1<2025, 2>(std::string_view const input) {
      71            1 :   std::vector<Range> ranges = parseRanges(input);
      72            1 :   uint64_t sum = 0;
      73            1 :   for(auto const & r : ranges)
      74           30 :   {
      75      2070358 :     for(uint64_t i = r.from; i <= r.to; ++i)
      76      2070328 :     {
      77      2070328 :       if(isInvalidPart1(i))
      78          565 :       {
      79          565 :         sum += i;
      80          565 :       }
      81      2070328 :     }
      82           30 :   }
      83            1 :   return std::to_string(sum);
      84            1 : }
      85              : 
      86            1 : template <> std::string solvePart2<2025, 2>(std::string_view const input) {
      87            1 :   std::vector<Range> ranges = parseRanges(input);
      88            1 :   uint64_t sum = 0;
      89            1 :   for(auto const & r : ranges)
      90           30 :   {
      91      2070358 :     for(uint64_t i = r.from; i <= r.to; ++i)
      92      2070328 :     {
      93      2070328 :       if(isInvalidPart2(i))
      94          623 :       {
      95          623 :         sum += i;
      96          623 :       }
      97      2070328 :     }
      98           30 :   }
      99            1 :   return std::to_string(sum);
     100            1 : }