Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "LinewiseInput.h"
       3              : #include "PuzzleImpl.h"
       4              : 
       5              : #include <algorithm>
       6              : #include <string>
       7              : 
       8              : namespace {
       9              : 
      10              : std::array<Vec2<int>, 4u> constexpr dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      11              : 
      12              : struct Guard {
      13              : 
      14      3091284 :   [[nodiscard]] Grid2d<char>::Coord next() const { return pos + dirs[dirIdx]; }
      15       102768 :   void turn() { dirIdx = (dirIdx + 1) % 4; }
      16      2973720 :   void move() { pos = pos + dirs[dirIdx]; }
      17              : 
      18              :   Grid2d<char>::Coord pos;
      19              :   int dirIdx;
      20              : };
      21              : 
      22      3076488 : void moveGuard(Guard &guard, Grid2d<char> const &grid) {
      23      3076488 :   if (grid[guard.next()] == '#')
      24       102768 :     guard.turn();
      25      2973720 :   else
      26      2973720 :     guard.move();
      27      3076488 : }
      28              : 
      29      3072736 : bool guardToPath(Grid2d<unsigned char> &path, Guard const &guard) {
      30      3072736 :   unsigned int const mask = 1 << guard.dirIdx;
      31      3072736 :   unsigned char &v = path[guard.pos];
      32      3072736 :   if ((v & mask) != 0u)
      33         1602 :     return false;
      34              : 
      35      3071134 :   v = v | mask;
      36      3071134 :   return true;
      37      3072736 : }
      38              : 
      39         4721 : bool pathHasCycle(Guard guard, Grid2d<char> const &grid, Grid2d<unsigned char> path) {
      40      3070501 :   for (; grid[guard.pos] != '*'; moveGuard(guard, grid)) {
      41      3067382 :     if (!guardToPath(path, guard))
      42         1602 :       return true;
      43      3067382 :   }
      44         3119 :   return false;
      45         4721 : }
      46              : 
      47              : } // namespace
      48              : 
      49            1 : template <> std::string solvePart1<2024, 6>(std::string_view const input) {
      50            1 :   LinewiseInput linewise(input);
      51            1 :   Grid2d<char> grid = linewise.makeCharGrid2dWithGhostLayers(1, '*');
      52              : 
      53         5355 :   for (Guard guard{.pos = grid.find('^'), .dirIdx = 0}; grid[guard.pos] != '*';
      54         5354 :        moveGuard(guard, grid)) {
      55         5354 :     grid[guard.pos] = 'X';
      56         5354 :   }
      57              : 
      58            1 :   return std::to_string(grid.count('X'));
      59            1 : }
      60              : 
      61            1 : template <> std::string solvePart2<2024, 6>(std::string_view const input) {
      62            1 :   LinewiseInput linewise(input);
      63            1 :   Grid2d<char> grid = linewise.makeCharGrid2dWithGhostLayers(1, '*');
      64            1 :   Grid2d<unsigned char> path(grid.xSize(), grid.ySize());
      65              : 
      66            1 :   int cnt = 0;
      67         5355 :   for (Guard guard{.pos = grid.find('^'), .dirIdx = 0}; grid[guard.pos] != '*';
      68         5354 :        moveGuard(guard, grid)) {
      69         5354 :     if (grid[guard.next()] == '.') {
      70         4721 :       grid[guard.next()] = '#';
      71         4721 :       if (pathHasCycle(guard, grid, path))
      72         1602 :         ++cnt;
      73         4721 :       grid[guard.next()] = '.';
      74         4721 :     }
      75         5354 :     guardToPath(path, guard);
      76         5354 :     grid[guard.pos] = 'X';
      77         5354 :   }
      78              : 
      79            1 :   return std::to_string(cnt);
      80            1 : }