Line data    Source code

       1              : #include "LinewiseInput.h"
       2              : #include "PuzzleImpl.h"
       3              : 
       4              : #include <re2/re2.h>
       5              : 
       6              : #include <libassert/assert.hpp>
       7              : 
       8              : #include <cmath>
       9              : #include <cstdint>
      10              : #include <numeric>
      11              : #include <string>
      12              : #include <vector>
      13              : 
      14              : namespace {
      15              : 
      16              : struct Race {
      17              :   uint64_t time = 0u;
      18              :   uint64_t distance = 0u;
      19              : };
      20              : 
      21            1 : std::vector<Race> parseRaces(std::string_view timeStr, std::string_view distanceStr) {
      22            1 :   static RE2 const timePattern = "Time: +";
      23            1 :   static RE2 const distancePattern = "Distance: +";
      24            1 :   static RE2 const numberPattern = R"((\d+) *)";
      25            1 :   ASSUME(RE2::Consume(&timeStr, timePattern));
      26            1 :   ASSUME(RE2::Consume(&distanceStr, distancePattern));
      27              : 
      28            1 :   std::vector<Race> races;
      29            1 :   uint64_t time = 0;
      30            1 :   uint64_t distance = 0;
      31            5 :   while (RE2::Consume(&timeStr, numberPattern, &time)) {
      32            4 :     ASSUME(RE2::Consume(&distanceStr, numberPattern, &distance));
      33            4 :     races.push_back(Race{.time = time, .distance = distance});
      34            4 :   }
      35            1 :   return races;
      36            1 : }
      37              : 
      38            1 : Race parseSingleRace(std::string timeStr, std::string distanceStr) {
      39            1 :   static RE2 const timePattern = R"(Time:(\d+))";
      40            1 :   static RE2 const distancePattern = R"(Distance:(\d+))";
      41              : 
      42            1 :   std::erase(timeStr, ' ');
      43            1 :   std::erase(distanceStr, ' ');
      44              : 
      45            1 :   Race race;
      46            1 :   ASSUME(RE2::FullMatch(timeStr, timePattern, &race.time));
      47            1 :   ASSUME(RE2::FullMatch(distanceStr, distancePattern, &race.distance));
      48              : 
      49            1 :   return race;
      50            1 : }
      51              : 
      52            5 : uint64_t numPossibleRaces(Race const &race) {
      53            5 :   double const b = -static_cast<double>(race.time);
      54            5 :   double const c = static_cast<double>(race.distance); // NOLINT
      55              : 
      56            5 :   double const sqrtTerm = std::sqrt(b * b - 4.0 * c);
      57            5 :   double const x1 = (-b - sqrtTerm) * 0.5;
      58            5 :   double const x2 = (-b + sqrtTerm) * 0.5;
      59              : 
      60            5 :   DEBUG_ASSERT(!std::isnan(x1));
      61            5 :   DEBUG_ASSERT(!std::isnan(x2));
      62              : 
      63            5 :   uint64_t minChargeTime = std::ceil(x1);
      64            5 :   uint64_t maxChargeTime = std::floor(x2);
      65              : 
      66            5 :   uint64_t const distanceTravelled = (race.time - minChargeTime) * minChargeTime;
      67            5 :   if (distanceTravelled == race.distance)
      68            0 :     ++minChargeTime;
      69              : 
      70            5 :   if (distanceTravelled == race.distance)
      71            0 :     --maxChargeTime;
      72              : 
      73            5 :   return maxChargeTime - minChargeTime + 1u;
      74            5 : }
      75              : 
      76              : } // namespace
      77              : 
      78            1 : template <> std::string solvePart1<2023, 6>(std::string_view const input) {
      79            1 :   LinewiseInput const lines(input);
      80              : 
      81            1 :   std::vector<Race> const races = parseRaces(lines[0], lines[1]);
      82              : 
      83            1 :   return std::to_string(std::transform_reduce(races.begin(), races.end(), uint64_t(1),
      84            1 :                                               std::multiplies<>(), numPossibleRaces));
      85            1 : }
      86              : 
      87            1 : template <> std::string solvePart2<2023, 6>(std::string_view const input) {
      88            1 :   LinewiseInput const lines(input);
      89              : 
      90            1 :   Race race = parseSingleRace(std::string(lines[0]), std::string(lines[1]));
      91              : 
      92            1 :   return std::to_string(numPossibleRaces(race));
      93            1 : }