Line data    Source code

       1              : #include "LinewiseInput.h"
       2              : #include "PuzzleImpl.h"
       3              : 
       4              : #include <libassert/assert.hpp>
       5              : #include <limits>
       6              : #include <re2/re2.h>
       7              : 
       8              : #include <algorithm>
       9              : #include <charconv>
      10              : #include <cstdint>
      11              : #include <numeric>
      12              : #include <string>
      13              : #include <string_view>
      14              : #include <tuple>
      15              : 
      16              : namespace {
      17              : 
      18              : struct Node {
      19              :   unsigned l = std::numeric_limits<unsigned>::max();
      20              :   unsigned r = std::numeric_limits<unsigned>::max();
      21              : };
      22              : 
      23         4717 : constexpr unsigned parseLocation(std::string_view const location) {
      24         4717 :   DEBUG_ASSERT(location.size() == 3u);
      25         4717 :   return ((location[0] - 'A') << 10u) + ((location[1] - 'A') << 5u) + (location[2] - 'A');
      26         4717 : }
      27              : 
      28         1572 : bool isStartingLocation(unsigned loc) {
      29         1572 :   constexpr unsigned mask = (1u << 5u) - 1u;
      30         1572 :   return (loc & mask) == 0;
      31         1572 : }
      32              : 
      33       218293 : bool isGoalLocation(unsigned loc) {
      34       218293 :   constexpr unsigned mask = (1u << 5u) - 1u;
      35       218293 :   return (loc & mask) == 'Z' - 'A';
      36       218293 : }
      37              : 
      38            0 : [[maybe_unused]] std::string printLocation(unsigned loc) {
      39            0 :   std::string result;
      40            0 :   result.resize(3u);
      41            0 : 
      42            0 :   constexpr unsigned mask = (1u << 5u) - 1u;
      43            0 :   result[0] = static_cast<char>('A' + (loc >> 10u));
      44            0 :   result[1] = static_cast<char>('A' + ((loc >> 5u) & mask));
      45            0 :   result[2] = static_cast<char>('A' + (loc & mask));
      46            0 :   return result;
      47            0 : }
      48              : 
      49            2 : std::tuple<std::vector<Node>, std::vector<unsigned>> parseNodes(auto begin, auto end) {
      50            2 :   static RE2 const nodePattern(R"(([A-Z]{3}) = \(([A-Z]{3}), ([A-Z]{3})\))");
      51              : 
      52            2 :   std::vector<Node> map(1u << 15);
      53            2 :   std::vector<unsigned> startingLocations;
      54            2 :   std::string_view cur, l, r;
      55         1574 :   while (begin != end) {
      56         1572 :     ASSUME(RE2::FullMatch(*begin++, nodePattern, &cur, &l, &r));
      57         1572 :     unsigned loc = parseLocation(cur);
      58         1572 :     DEBUG_ASSERT(loc < map.size());
      59         1572 :     map[loc] = Node{.l = parseLocation(l), .r = parseLocation(r)};
      60         1572 :     if (isStartingLocation(loc))
      61           12 :       startingLocations.push_back(loc);
      62         1572 :   }
      63              : 
      64            2 :   return {map, startingLocations};
      65            2 : }
      66              : 
      67              : } // namespace
      68              : 
      69            1 : template <> std::string solvePart1<2023, 8>(std::string_view const input) {
      70            1 :   LinewiseInput const lines(input);
      71            1 :   std::string_view const path = lines[0];
      72            1 :   auto [nodes, locations] = parseNodes(std::next(lines.begin(), 2), lines.end());
      73              : 
      74            1 :   unsigned constexpr goal = parseLocation("ZZZ");
      75            1 :   unsigned location = parseLocation("AAA");
      76              : 
      77            1 :   uint64_t ctr = 0;
      78           48 :   while (location != goal) {
      79        12408 :     for (auto it = path.begin(); it != path.end() && !isGoalLocation(location); ++it) {
      80        12361 :       location = *it == 'L' ? nodes[location].l : nodes[location].r;
      81        12361 :       ++ctr;
      82        12361 :     }
      83           47 :   }
      84            1 :   return std::to_string(ctr);
      85            1 : }
      86              : 
      87            1 : template <> std::string solvePart2<2023, 8>(std::string_view const input) {
      88            1 :   LinewiseInput const lines(input);
      89              : 
      90            1 :   std::string_view const path = lines[0];
      91            1 :   auto [nodes, locations] = parseNodes(std::next(lines.begin(), 2), lines.end());
      92              : 
      93            1 :   std::vector<uint64_t> counters(locations.size());
      94              : 
      95            7 :   for (size_t i = 0; i < locations.size(); ++i) {
      96            6 :     unsigned location = locations[i];
      97            6 :     uint64_t &ctr = counters[i];
      98          396 :     while (!isGoalLocation(location))
      99       102960 :       for (auto it = path.begin(); it != path.end() && !isGoalLocation(location); ++it) {
     100       102570 :         location = *it == 'L' ? nodes[location].l : nodes[location].r;
     101       102570 :         ++ctr;
     102       102570 :       }
     103            6 :   }
     104              : 
     105            6 :   auto countSteps = [&nodes, &path](unsigned location) {
     106            6 :     uint64_t ctr = 0u;
     107          396 :     while (!isGoalLocation(location))
     108       102960 :       for (auto it = path.begin(); it != path.end() && !isGoalLocation(location); ++it) {
     109       102570 :         location = *it == 'L' ? nodes[location].l : nodes[location].r;
     110       102570 :         ++ctr;
     111       102570 :       }
     112            6 :     return ctr;
     113            6 :   };
     114              : 
     115            1 :   return std::to_string(std::transform_reduce(
     116            1 :       locations.begin(), locations.end(), size_t(1),
     117            6 :       [](uint64_t lhs, uint64_t rhs) { return std::lcm(lhs, rhs); }, countSteps));
     118            1 : }