Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Grid2d.h"
       4              : #include "IntegerCast.h"
       5              : #include "LinewiseInput.h"
       6              : 
       7              : #include <algorithm>
       8              : #include <flat_set>
       9              : #include <string_view>
      10              : 
      11              : using Coord = Grid2d<char>::Coord;
      12              : 
      13            1 : template <> std::string solvePart1<2025, 7>(std::string_view const input) {
      14            1 :   LinewiseInput inputLines{input};
      15            1 :   Grid2d<char> gridOrig = inputLines.makeCharGrid2d();
      16            1 :   Grid2dSpan<char> grid = gridOrig.flipY();
      17            1 :   std::flat_set<int> xs0, xs1;
      18            1 :   auto cur = &xs0;
      19            1 :   auto next = &xs1;
      20            1 :   Coord startPos = grid.find('S');
      21            1 :   DEBUG_ASSERT(startPos.y() == 0);
      22            1 :   cur->insert(startPos.x());
      23            1 :   uint64_t ctr = 0;
      24          143 :   for (int y = 0; y < grid.ySize(); ++y) {
      25          142 :     next->clear();
      26         6024 :     for (auto const x : *cur) {
      27         6024 :       if (grid[x, y] != '^') {
      28         4313 :         next->insert(next->end(), x);
      29         4313 :       } else {
      30         1711 :         DEBUG_ASSERT(x > 0 && x + 1 < grid.xSize());
      31         1711 :         next->insert(next->end(), x - 1);
      32         1711 :         next->insert(next->end(), x + 1);
      33         1711 :         ++ctr;
      34         1711 :       }
      35         6024 :     }
      36          142 :     std::swap(cur, next);
      37          142 :   }
      38            1 :   return std::to_string(ctr);
      39            1 : }
      40              : 
      41            1 : template <> std::string solvePart2<2025, 7>(std::string_view const input) {
      42            1 :   LinewiseInput inputLines{input};
      43            1 :   Grid2d<char> gridOrig = inputLines.makeCharGrid2d();
      44            1 :   Grid2dSpan<char> grid = gridOrig.flipY();
      45            1 :   Grid2d<uint64_t> counts(grid.xSize(), grid.ySize() + 1, 0);
      46          142 :   for (int x = 0; x < grid.xSize(); ++x) {
      47          141 :     counts[x, grid.ySize()] = 1;
      48          141 :   }
      49          143 :   for (int y = grid.ySize() - 1; y >= 0; --y) {
      50        20164 :     for (int x = 0; x < grid.xSize(); ++x) {
      51        20022 :       if (grid[x, y] != '^') {
      52        18214 :         counts[x, y] = counts[x, y + 1];
      53        18214 :       } else {
      54              :         DEBUG_ASSERT(x > 0 && x + 1 < grid.xSize());
      55         1808 :         counts[x, y] = counts[x - 1, y + 1] + counts[x + 1, y + 1];
      56         1808 :       }
      57        20022 :     }
      58          142 :   }
      59            1 :   return std::to_string(counts[grid.find('S')]);
      60            1 : }