Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Grid2d.h"
       4              : #include "LinewiseInput.h"
       5              : 
       6              : #include <algorithm>
       7              : #include <ranges>
       8              : #include <stack>
       9              : #include <string>
      10              : 
      11              : namespace {
      12              : std::array<Vec2<int>, 4u> constexpr dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      13              : } // namespace
      14              : 
      15            1 : template <> std::string solvePart1<2024, 10>(std::string_view const input) {
      16            1 :   Grid2d<char> map = LinewiseInput(input).makeCharGrid2dWithGhostLayers(1, '.');
      17              : 
      18            1 :   uint64_t cnt = 0;
      19            1 :   std::stack<Grid2d<char>::Coord> stack;
      20          265 :   for (auto const &trailhead : map.findAll('0')) {
      21          265 :     std::unordered_set<Grid2d<char>::Coord> trailends;
      22          265 :     stack.push(trailhead);
      23         7464 :     while (!stack.empty()) {
      24         7199 :       auto c = stack.top();
      25         7199 :       stack.pop();
      26         7199 :       if (map[c] == '9') {
      27         1380 :         trailends.insert(c);
      28         5819 :       } else {
      29        23276 :         for (auto const d : dirs) {
      30        23276 :           auto n = c + d;
      31        23276 :           if (map[n] == map[c] + 1) {
      32         6934 :             stack.push(n);
      33         6934 :           }
      34        23276 :         }
      35         5819 :       }
      36         7199 :     }
      37          265 :     cnt += trailends.size();
      38          265 :   }
      39              : 
      40            1 :   return std::to_string(cnt);
      41            1 : }
      42              : 
      43            1 : template <> std::string solvePart2<2024, 10>(std::string_view const input) {
      44            1 :   Grid2d<char> map = LinewiseInput(input).makeCharGrid2dWithGhostLayers(1, '.');
      45              : 
      46            1 :   uint64_t cnt = 0;
      47            1 :   std::stack<Grid2d<char>::Coord> stack;
      48          265 :   for (auto const &trailhead : map.findAll('0')) {
      49          265 :     stack.push(trailhead);
      50         7464 :     while (!stack.empty()) {
      51         7199 :       auto c = stack.top();
      52         7199 :       stack.pop();
      53         7199 :       if (map[c] == '9') {
      54         1380 :         ++cnt;
      55         5819 :       } else {
      56        23276 :         for (auto const d : dirs) {
      57        23276 :           auto n = c + d;
      58        23276 :           if (map[n] == map[c] + 1) {
      59         6934 :             stack.push(n);
      60         6934 :           }
      61        23276 :         }
      62         5819 :       }
      63         7199 :     }
      64          265 :   }
      65              : 
      66            1 :   return std::to_string(cnt);
      67            1 : }