Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "LinewiseInput.h"
       3              : #include "PuzzleImpl.h"
       4              : 
       5              : #include <libassert/assert.hpp>
       6              : #include <re2/re2.h>
       7              : 
       8              : #include <algorithm>
       9              : #include <execution>
      10              : #include <iostream>
      11              : #include <numeric>
      12              : #include <stack>
      13              : #include <string_view>
      14              : 
      15              : namespace {
      16              : 
      17              : using GridView = Grid2dSpan<char>;
      18              : using VisitedGridView = Grid2dSpan<uint8_t>;
      19              : using Coord = GridView::Coord;
      20              : 
      21              : enum Dir : uint8_t { N = 0, E = 1, S = 2, W = 3 };
      22              : constexpr std::array<Coord, 4u> stencil = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      23              : 
      24          441 : Grid2d<uint8_t> makeVisitedGrid(int xSize, int ySize) {
      25          441 :   Grid2d<uint8_t> visited(xSize, ySize, 0b1111, 1);
      26        48947 :   for (int y = 0; y < visited.ySize(); ++y)
      27      5370638 :     for (int x = 0; x < visited.xSize(); ++x)
      28      5322132 :       visited[x, y] = 0;
      29          441 :   return visited;
      30          441 : }
      31              : 
      32          441 : size_t walkGrid(GridView const g, Coord startPos, Dir startDir) {
      33          441 :   Grid2d<uint8_t> visited = makeVisitedGrid(g.xSize(), g.ySize());
      34          441 :   std::stack<std::pair<Coord, Dir>> startPoints;
      35          441 :   startPoints.emplace(startPos, startDir);
      36              : 
      37        74998 :   while (!startPoints.empty()) {
      38        74998 :     auto [c, d] = startPoints.top();
      39        74998 :     startPoints.pop();
      40              : 
      41      3045188 :     while ((visited[c] & 1u << d) == 0u) {
      42      2977367 :       visited[c] |= 1u << d;
      43              : 
      44      2977367 :       switch (g[c]) {
      45      2671762 :       case '.':
      46      2671762 :         break;
      47        69013 :       case '|':
      48        69013 :         switch (d) {
      49        16279 :         case N:
      50        33135 :         case S:
      51        33135 :           break;
      52        16814 :         case E:
      53        35885 :         case W:
      54        35885 :           d = N;
      55        35885 :           startPoints.emplace(c + stencil[S], S);
      56        35885 :           break;
      57            0 :         default:
      58            0 :           UNREACHABLE();
      59        69013 :         }
      60        69015 :         break;
      61        76605 :       case '-':
      62        76605 :         switch (d) {
      63        18572 :         case N:
      64        38677 :         case S:
      65        38677 :           d = E;
      66        38677 :           startPoints.emplace(c + stencil[W], W);
      67        38677 :           break;
      68        19598 :         case E:
      69        37926 :         case W:
      70        37926 :           break;
      71            0 :         default:
      72            0 :           UNREACHABLE();
      73        76605 :         }
      74        76594 :         break;
      75        85762 :       case '/':
      76        85762 :         switch (d) {
      77        21650 :         case N:
      78        21650 :           d = E;
      79        21650 :           break;
      80        20609 :         case S:
      81        20609 :           d = W;
      82        20609 :           break;
      83        22398 :         case E:
      84        22398 :           d = N;
      85        22398 :           break;
      86        21104 :         case W:
      87        21104 :           d = S;
      88        21104 :           break;
      89            0 :         default:
      90            0 :           UNREACHABLE();
      91        85762 :         }
      92        85748 :         break;
      93        85748 :       case '\\':
      94        70707 :         switch (d) {
      95        17793 :         case N:
      96        17793 :           d = W;
      97        17793 :           break;
      98        17293 :         case S:
      99        17293 :           d = E;
     100        17293 :           break;
     101        18265 :         case E:
     102        18265 :           d = S;
     103        18265 :           break;
     104        17300 :         case W:
     105        17300 :           d = N;
     106        17300 :           break;
     107            0 :         default:
     108            0 :           UNREACHABLE();
     109        70707 :         }
     110        70702 :         break;
     111        70702 :       default:
     112            0 :         UNREACHABLE();
     113      2977367 :       }
     114      2970190 :       c += stencil[d];
     115      2970190 :     }
     116        74998 :   }
     117  >1844*10^16 :   return visited.count_if([](auto const &bits) { return bits != 0; });
     118          441 : }
     119              : 
     120              : } // namespace
     121              : 
     122            1 : template <> size_t part1<2023, 16>(std::string_view const input) {
     123            1 :   LinewiseInput lines(input);
     124            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
     125              : 
     126            1 :   return walkGrid(grid, {0, grid.ySize() - 1}, E);
     127            1 : }
     128              : 
     129            1 : template <> size_t part2<2023, 16>(std::string_view const input) {
     130            1 :   LinewiseInput lines(input);
     131            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
     132              : 
     133            1 :   std::vector<std::pair<Coord, Dir>> startPoints;
     134            1 :   startPoints.reserve(2 * grid.xSize() + 2 * grid.ySize());
     135              : 
     136          111 :   for (int y = 0; y < grid.ySize(); ++y) {
     137          110 :     startPoints.emplace_back(Coord{0, y}, E);
     138          110 :     startPoints.emplace_back(Coord{grid.xSize() - 1, y}, W);
     139          110 :   }
     140          111 :   for (int x = 0; x < grid.xSize(); ++x) {
     141          110 :     startPoints.emplace_back(Coord{x, 0}, N);
     142          110 :     startPoints.emplace_back(Coord{x, grid.ySize() - 1}, S);
     143          110 :   }
     144              : 
     145            1 :   return std::transform_reduce(
     146            1 :       std::execution::par, startPoints.begin(), startPoints.end(), size_t(0),
     147          440 :       [](size_t lhs, size_t rhs) { return std::max(lhs, rhs); },
     148          440 :       [&grid](auto const &startPos) { return walkGrid(grid, startPos.first, startPos.second); });
     149            1 : }