Line data    Source code

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