Line data    Source code

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