Line data    Source code

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