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>
      14              : #include <string_view>
      15              : 
      16              : namespace {
      17              : 
      18              : using GridView = Grid2dSpan<char>;
      19              : using VisitedGridView = Grid2dSpan<uint8_t>;
      20              : using Coord = GridView::Coord;
      21              : 
      22              : enum Dir : uint8_t { N = 0, E = 1, S = 2, W = 3 };
      23              : constexpr std::array<Coord, 4u> stencil = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      24              : 
      25          441 : Grid2d<uint8_t> makeVisitedGrid(int xSize, int ySize) {
      26          441 :   Grid2d<uint8_t> visited(xSize, ySize, 0b1111, 1);
      27        48950 :   for (int y = 0; y < visited.ySize(); ++y)
      28      5377786 :     for (int x = 0; x < visited.xSize(); ++x)
      29      5329277 :       visited[x, y] = 0;
      30          441 :   return visited;
      31          441 : }
      32              : 
      33          441 : size_t walkGrid(GridView const g, Coord startPos, Dir startDir) {
      34          441 :   Grid2d<uint8_t> visited = makeVisitedGrid(g.xSize(), g.ySize());
      35          441 :   std::stack<std::pair<Coord, Dir>> startPoints;
      36          441 :   startPoints.emplace(startPos, startDir);
      37              : 
      38        75000 :   while (!startPoints.empty()) {
      39        75000 :     auto [c, d] = startPoints.top();
      40        75000 :     startPoints.pop();
      41              : 
      42      3047943 :     while ((visited[c] & 1u << d) == 0u) {
      43      2977205 :       visited[c] |= 1u << d;
      44              : 
      45      2977205 :       switch (g[c]) {
      46      2673436 :       case '.':
      47      2673436 :         break;
      48        69017 :       case '|':
      49        69017 :         switch (d) {
      50        16279 :         case N:
      51        33136 :         case S:
      52        33136 :           break;
      53        16813 :         case E:
      54        35885 :         case W:
      55        35885 :           d = N;
      56        35885 :           startPoints.emplace(c + stencil[S], S);
      57        35885 :           break;
      58            0 :         default:
      59            0 :           UNREACHABLE();
      60        69017 :         }
      61        69019 :         break;
      62        76609 :       case '-':
      63        76609 :         switch (d) {
      64        18573 :         case N:
      65        38679 :         case S:
      66        38679 :           d = E;
      67        38679 :           startPoints.emplace(c + stencil[W], W);
      68        38679 :           break;
      69        19602 :         case E:
      70        37930 :         case W:
      71        37930 :           break;
      72            0 :         default:
      73            0 :           UNREACHABLE();
      74        76609 :         }
      75        76600 :         break;
      76        85759 :       case '/':
      77        85759 :         switch (d) {
      78        21649 :         case N:
      79        21649 :           d = E;
      80        21649 :           break;
      81        20607 :         case S:
      82        20607 :           d = W;
      83        20607 :           break;
      84        22398 :         case E:
      85        22398 :           d = N;
      86        22398 :           break;
      87        21106 :         case W:
      88        21106 :           d = S;
      89        21106 :           break;
      90            0 :         default:
      91            0 :           UNREACHABLE();
      92        85759 :         }
      93        85744 :         break;
      94        85744 :       case '\\':
      95        70706 :         switch (d) {
      96        17794 :         case N:
      97        17794 :           d = W;
      98        17794 :           break;
      99        17293 :         case S:
     100        17293 :           d = E;
     101        17293 :           break;
     102        18321 :         case E:
     103        18321 :           d = S;
     104        18321 :           break;
     105        17300 :         case W:
     106        17300 :           d = N;
     107        17300 :           break;
     108            0 :         default:
     109            0 :           UNREACHABLE();
     110        70706 :         }
     111        70698 :         break;
     112        70698 :       default:
     113            0 :         UNREACHABLE();
     114      2977205 :       }
     115      2972943 :       c += stencil[d];
     116      2972943 :     }
     117        75000 :   }
     118  >1844*10^16 :   return visited.count_if([](auto const &bits) { return bits != 0; });
     119          441 : }
     120              : 
     121              : } // namespace
     122              : 
     123            1 : template <> std::string solvePart1<2023, 16>(std::string_view const input) {
     124            1 :   LinewiseInput lines(input);
     125            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
     126              : 
     127            1 :   return std::to_string(walkGrid(grid, {0, grid.ySize() - 1}, E));
     128            1 : }
     129              : 
     130            1 : template <> std::string solvePart2<2023, 16>(std::string_view const input) {
     131            1 :   LinewiseInput lines(input);
     132            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
     133              : 
     134            1 :   std::vector<std::pair<Coord, Dir>> startPoints;
     135            1 :   startPoints.reserve(2 * grid.xSize() + 2 * grid.ySize());
     136              : 
     137          111 :   for (int y = 0; y < grid.ySize(); ++y) {
     138          110 :     startPoints.emplace_back(Coord{0, y}, E);
     139          110 :     startPoints.emplace_back(Coord{grid.xSize() - 1, y}, W);
     140          110 :   }
     141          111 :   for (int x = 0; x < grid.xSize(); ++x) {
     142          110 :     startPoints.emplace_back(Coord{x, 0}, N);
     143          110 :     startPoints.emplace_back(Coord{x, grid.ySize() - 1}, S);
     144          110 :   }
     145              : 
     146            1 :   return std::to_string(std::transform_reduce(
     147            1 :       std::execution::par, startPoints.begin(), startPoints.end(), size_t(0),
     148          440 :       [](size_t lhs, size_t rhs) { return std::max(lhs, rhs); },
     149          440 :       [&grid](auto const &startPos) { return walkGrid(grid, startPos.first, startPos.second); }));
     150            1 : }