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