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