Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "IntegerCast.h"
       4              : #include "Views.h"
       5              : 
       6              : #include <boost/functional/hash.hpp>
       7              : 
       8              : #include <algorithm>
       9              : #include <string_view>
      10              : #include <unordered_map>
      11              : 
      12              : namespace {
      13              : 
      14              : using ServerRack = std::unordered_multimap<std::string_view, std::string_view>;
      15              : using PathCountCache =
      16              :     std::unordered_map<std::pair<std::string_view, std::string_view>, uint64_t,
      17              :                        boost::hash<std::pair<std::string_view, std::string_view>>>;
      18              : 
      19            2 : ServerRack parseInput(std::string_view const input) {
      20            2 :   ServerRack result;
      21         1224 :   for (auto const line : input | views::splitLines) {
      22         1224 :     auto it = std::ranges::find(line, ':');
      23         1224 :     DEBUG_ASSERT(it != line.end());
      24         1224 :     std::string_view const key{line.begin(), it};
      25         4550 :     for (it = std::next(it, 2); it < line.end(); ++it) {
      26         3326 :       auto startIt = it;
      27         3326 :       it = std::find(startIt, line.end(), ' ');
      28         3326 :       result.emplace(std::piecewise_construct, std::forward_as_tuple(key),
      29         3326 :                      std::forward_as_tuple(startIt, it));
      30         3326 :     }
      31         1224 :   }
      32            2 :   return result;
      33            2 : }
      34              : 
      35              : uint64_t countPaths(std::string_view const from, std::string_view const to,
      36         4668 :                     ServerRack const &serverRack, PathCountCache &cache) {
      37         4668 :   if (from == to)
      38           52 :     return 1;
      39              : 
      40         4616 :   auto it = cache.find({from, to});
      41         4616 :   if (it != cache.end())
      42         2862 :     return it->second;
      43              : 
      44         1754 :   uint64_t pathCount = 0;
      45              : 
      46         1754 :   auto const [begin, end] = serverRack.equal_range(from);
      47              : 
      48         6415 :   for (auto it = begin; it != end; ++it) {
      49         4661 :     pathCount += countPaths(it->second, to, serverRack, cache);
      50         4661 :   }
      51              : 
      52         1754 :   cache.emplace(std::piecewise_construct, std::forward_as_tuple(from, to),
      53         1754 :                 std::forward_as_tuple(pathCount));
      54         1754 :   return pathCount;
      55         4616 : }
      56              : 
      57              : } // namespace
      58              : 
      59            1 : template <> std::string solvePart1<2025, 11>(std::string_view const input) {
      60            1 :   ServerRack const serverRack = parseInput(input);
      61            1 :   PathCountCache cache;
      62              : 
      63            1 :   return std::to_string(countPaths("you", "out", serverRack, cache));
      64            1 : }
      65              : 
      66            1 : template <> std::string solvePart2<2025, 11>(std::string_view const input) {
      67            1 :   ServerRack const serverRack = parseInput(input);
      68            1 :   PathCountCache cache;
      69              : 
      70            6 :   auto cp = [&](std::string_view const from, std::string_view const to) {
      71            6 :     return countPaths(from, to, serverRack, cache);
      72            6 :   };
      73              : 
      74            1 :   return std::to_string(cp("svr", "dac") * cp("dac", "fft") * cp("fft", "out") +
      75            1 :                         cp("svr", "fft") * cp("fft", "dac") * cp("dac", "out"));
      76            1 : }