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