Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Grid2d.h"
       4              : #include "LinewiseInput.h"
       5              : 
       6              : #include <cassert>
       7              : #include <iostream>
       8              : #include <ranges>
       9              : #include <stack>
      10              : #include <string>
      11              : 
      12              : namespace {
      13              : 
      14              : std::array<Vec2<int>, 8u> constexpr dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      15              : 
      16              : } // namespace
      17              : 
      18            1 : template <> std::string solvePart1<2024, 12>(std::string_view const input) {
      19            1 :   Grid2d<char> map = LinewiseInput(input).makeCharGrid2dWithGhostLayers(1, '.');
      20            1 :   Grid2d<unsigned char> visited(map.xSize(), map.ySize(), 0);
      21            1 :   std::stack<Grid2d<char>::Coord> samePlantNeighbors;
      22              : 
      23            1 :   uint64_t sum = 0;
      24          141 :   for (Grid2d<char>::Coord x = {0, 0}; x.y() < map.ySize(); ++x.y())
      25        19740 :     for (x.x() = 0; x.x() < map.xSize(); ++x.x()) {
      26        19600 :       if (visited[x] == 1)
      27        19000 :         continue;
      28          600 :       char const curPlant = map[x];
      29          600 :       uint64_t area = 0;
      30          600 :       uint64_t perimeter = 0;
      31          600 :       samePlantNeighbors.push(x);
      32       141428 :       while (!samePlantNeighbors.empty()) {
      33       140828 :         auto xx = samePlantNeighbors.top();
      34       140828 :         samePlantNeighbors.pop();
      35       140828 :         if (visited[xx] == 1)
      36       121228 :           continue;
      37        19600 :         visited[xx] = 1;
      38        19600 :         ++area;
      39       156800 :         for (auto d : dirs) {
      40       156800 :           auto n = xx + d;
      41       156800 :           if (map[n] != curPlant)
      42        16572 :             ++perimeter;
      43       140228 :           else
      44       140228 :             samePlantNeighbors.push(n);
      45       156800 :         }
      46        19600 :       }
      47          600 :       sum += area * perimeter;
      48          600 :     }
      49              : 
      50            1 :   return std::to_string(sum);
      51            1 : }
      52              : 
      53            1 : template <> std::string solvePart2<2024, 12>(std::string_view const input) {
      54            1 :   Grid2d<char> map = LinewiseInput(input).makeCharGrid2dWithGhostLayers(1, '.');
      55            1 :   Grid2d<unsigned char> visited(map.xSize(), map.ySize(), 0);
      56            1 :   std::stack<Grid2d<char>::Coord> samePlantNeighbors;
      57              : 
      58            1 :   uint64_t sum = 0;
      59          141 :   for (Grid2d<char>::Coord x = {0, 0}; x.y() < map.ySize(); ++x.y())
      60        19740 :     for (x.x() = 0; x.x() < map.xSize(); ++x.x()) {
      61        19600 :       if (visited[x] == 1)
      62        19000 :         continue;
      63          600 :       char const curPlant = map[x];
      64          600 :       uint64_t area = 0;
      65          600 :       uint64_t corners = 0;
      66          600 :       samePlantNeighbors.push(x);
      67       141428 :       while (!samePlantNeighbors.empty()) {
      68       140828 :         auto xx = samePlantNeighbors.top();
      69       140828 :         samePlantNeighbors.pop();
      70       140828 :         if (visited[xx] == 1)
      71       121228 :           continue;
      72        19600 :         visited[xx] = 1;
      73        19600 :         ++area;
      74       176400 :         for (unsigned i = 0; i < dirs.size(); ++i) {
      75       156800 :           unsigned ii = (i + 1) % 4;
      76       156800 :           auto n = xx + dirs[i];
      77       156800 :           if (map[xx + dirs[i]] == curPlant) {
      78       140228 :             samePlantNeighbors.push(n);
      79       140228 :             if (map[xx + dirs[ii]] == curPlant && map[xx + dirs[i] + dirs[ii]] != curPlant)
      80         4067 :               ++corners; // inner corner
      81       140228 :           } else {
      82        16572 :             if (map[xx + dirs[ii]] != curPlant)
      83         6323 :               ++corners; // outer
      84        16572 :           }
      85       156800 :         }
      86        19600 :       }
      87          600 :       sum += area * corners;
      88          600 :     }
      89              : 
      90            1 :   return std::to_string(sum);
      91            1 : }