Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "IntegerCast.h"
       3              : #include "LinewiseInput.h"
       4              : #include "PuzzleImpl.h"
       5              : 
       6              : #include <libassert/assert.hpp>
       7              : 
       8              : #include <numeric>
       9              : #include <string>
      10              : #include <string_view>
      11              : 
      12              : namespace {
      13              : 
      14              : using Grid = Grid2dSpan<char>;
      15              : using Coord = Grid::Coord;
      16              : 
      17              : constexpr char ROUND_ROCK = 'O';
      18              : constexpr char CUBE_ROCK = '#';
      19              : constexpr char EMPTY_SPACE = '.';
      20              : 
      21          137 : void tiltNorth(Grid const &g) {
      22        13837 :   for (Coord x{0, g.ySize() - 1}; x.x() < g.xSize(); ++x.x()) {
      23       516232 :     for (x.y() = g.ySize() - 1; x.y() >= 0; --x.y()) {
      24       502532 :       if (g[x] != EMPTY_SPACE)
      25       104418 :         continue;
      26       398114 :       Coord xx = x;
      27      2281314 :       while (g[xx] == EMPTY_SPACE)
      28      1883200 :         --xx.y();
      29       398114 :       if (g[xx] == ROUND_ROCK) {
      30       207828 :         g[x] = ROUND_ROCK;
      31       207828 :         g[xx] = EMPTY_SPACE;
      32       207828 :       } else if (g[xx] == CUBE_ROCK) {
      33       190286 :         x.y() = xx.y();
      34       190286 :       }
      35       398114 :     }
      36        13700 :   }
      37          137 : }
      38              : 
      39          136 : void tiltSouth(Grid const &g) {
      40        13736 :   for (Coord x{0, 0}; x.x() < g.xSize(); ++x.x()) {
      41       513531 :     for (x.y() = 0; x.y() < g.ySize(); ++x.y()) {
      42       499931 :       if (g[x] != EMPTY_SPACE)
      43       106139 :         continue;
      44       393792 :       Coord xx = x;
      45      2262826 :       while (g[xx] == EMPTY_SPACE)
      46      1869034 :         ++xx.y();
      47       393792 :       if (g[xx] == ROUND_ROCK) {
      48       206420 :         g[x] = ROUND_ROCK;
      49       206420 :         g[xx] = EMPTY_SPACE;
      50       206420 :       } else if (g[xx] == CUBE_ROCK) {
      51       187372 :         x.y() = xx.y();
      52       187372 :       }
      53       393792 :     }
      54        13600 :   }
      55          136 : }
      56              : 
      57          136 : void tiltEast(Grid const &g) {
      58        13736 :   for (Coord x{g.xSize() - 1, 0}; x.y() < g.ySize(); ++x.y()) {
      59       512863 :     for (x.x() = g.xSize() - 1; x.x() >= 0; --x.x()) {
      60       499263 :       if (g[x] != EMPTY_SPACE)
      61        97173 :         continue;
      62       402090 :       Coord xx = x;
      63      2377948 :       while (g[xx] == EMPTY_SPACE)
      64      1975858 :         --xx.x();
      65       402090 :       if (g[xx] == ROUND_ROCK) {
      66       210414 :         g[x] = ROUND_ROCK;
      67       210414 :         g[xx] = EMPTY_SPACE;
      68       210414 :       } else if (g[xx] == CUBE_ROCK) {
      69       191676 :         x.x() = xx.x();
      70       191676 :       }
      71       402090 :     }
      72        13600 :   }
      73          136 : }
      74              : 
      75          136 : void tiltWest(Grid const &g) {
      76        13736 :   for (Coord x{0, 0}; x.y() < g.ySize(); ++x.y()) {
      77       513118 :     for (x.x() = 0; x.x() < g.xSize(); ++x.x()) {
      78       499518 :       if (g[x] != EMPTY_SPACE)
      79       101806 :         continue;
      80       397712 :       Coord xx = x;
      81      2369876 :       while (g[xx] == EMPTY_SPACE)
      82      1972164 :         ++xx.x();
      83       397712 :       if (g[xx] == ROUND_ROCK) {
      84       209666 :         g[x] = ROUND_ROCK;
      85       209666 :         g[xx] = EMPTY_SPACE;
      86       209666 :       } else if (g[xx] == CUBE_ROCK) {
      87       188046 :         x.x() = xx.x();
      88       188046 :       }
      89       397712 :     }
      90        13600 :   }
      91          136 : }
      92              : 
      93          136 : void cycle(Grid const &g) {
      94          136 :   tiltNorth(g);
      95          136 :   tiltWest(g);
      96          136 :   tiltSouth(g);
      97          136 :   tiltEast(g);
      98          136 : }
      99              : 
     100            2 : size_t calculateTotalLoad(Grid const &g) {
     101            2 :   std::vector<Coord> roundRocks = g.findAll(ROUND_ROCK);
     102              : 
     103            2 :   return std::transform_reduce(roundRocks.begin(), roundRocks.end(), size_t(0), std::plus<>(),
     104         3848 :                                [](Coord const c) { return integerCast<size_t>(c.y() + 1); });
     105            2 : }
     106              : 
     107              : } // namespace
     108              : 
     109            1 : template <> std::string solvePart1<2023, 14>(std::string_view const input) {
     110            1 :   LinewiseInput lines(input);
     111            1 :   Grid2d<char> grid = lines.makeCharGrid2dWithGhostLayers(1, CUBE_ROCK);
     112              : 
     113            1 :   tiltNorth(grid);
     114              : 
     115            1 :   return std::to_string(calculateTotalLoad(grid));
     116            1 : }
     117              : 
     118            1 : template <> std::string solvePart2<2023, 14>(std::string_view const input) {
     119            1 :   LinewiseInput lines(input);
     120            1 :   Grid2d<char> grid = lines.makeCharGrid2dWithGhostLayers(1, CUBE_ROCK);
     121              : 
     122            1 :   std::map<Grid2d<char>, size_t> previousCycles;
     123              : 
     124            1 :   constexpr size_t numCycles = 1000000000;
     125              : 
     126          136 :   for (size_t i = 0; i < numCycles; ++i) {
     127          136 :     if (auto it = previousCycles.find(grid); it != previousCycles.end()) {
     128            1 :       size_t const firstAppearance = it->second;
     129            1 :       size_t const cycleLength = i - firstAppearance;
     130            1 :       size_t const remainingCyclesToRun = (numCycles - firstAppearance) % cycleLength;
     131            2 :       for (size_t j = 0; j < remainingCyclesToRun; ++j) {
     132            1 :         cycle(grid);
     133            1 :       }
     134            1 :       break;
     135          135 :     } else {
     136          135 :       previousCycles.try_emplace(grid, i);
     137          135 :       cycle(grid);
     138          135 :     }
     139          136 :   }
     140            1 :   return std::to_string(calculateTotalLoad(grid));
     141            1 : }