Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "LinewiseInput.h"
       3              : #include "PuzzleImpl.h"
       4              : #include "Vector.h"
       5              : 
       6              : #include <libassert/assert.hpp>
       7              : 
       8              : #include <algorithm>
       9              : #include <string>
      10              : #include <string_view>
      11              : 
      12              : namespace {
      13              : 
      14              : using Grid = Grid2d<char>;
      15              : using IndexType = Grid::IndexType;
      16              : using Coord = Grid::Coord;
      17              : 
      18              : class CoordMapping {
      19              : public:
      20            2 :   CoordMapping(Grid const &grid, IndexType const spacing) {
      21            2 :     std::vector<bool> emptyLine(grid.ySize(), true);
      22            2 :     std::vector<bool> emptyColumn(grid.xSize(), true);
      23          282 :     for (IndexType y = 0; y < grid.ySize(); ++y)
      24        39480 :       for (IndexType x = 0; x < grid.xSize(); ++x) {
      25        39200 :         if (grid[x, y] == '#') {
      26          866 :           emptyLine[y] = false;
      27          866 :           emptyColumn[x] = false;
      28          866 :         }
      29        39200 :       }
      30              : 
      31          282 :     for (int x = 0, mappedX = 0; x < grid.xSize(); ++x) {
      32          280 :       _xMapping.push_back(mappedX);
      33          280 :       if (emptyColumn[x])
      34           26 :         mappedX += spacing;
      35          254 :       else
      36          254 :         ++mappedX;
      37          280 :     }
      38          282 :     for (int y = 0, mappedY = 0; y < grid.ySize(); ++y) {
      39          280 :       _yMapping.push_back(mappedY);
      40          280 :       if (emptyLine[y])
      41           14 :         mappedY += spacing;
      42          266 :       else
      43          266 :         ++mappedY;
      44          280 :     }
      45            2 :   }
      46          866 :   [[nodiscard]] Coord operator()(Coord const &c) const {
      47          866 :     return {_xMapping[c.x()], _yMapping[c.y()]};
      48          866 :   }
      49              : 
      50              : private:
      51              :   std::vector<IndexType> _xMapping;
      52              :   std::vector<IndexType> _yMapping;
      53              : };
      54              : 
      55              : } // namespace
      56              : 
      57            1 : template <> std::string solvePart1<2023, 11>(std::string_view const input) {
      58            1 :   LinewiseInput lines(input);
      59            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
      60              : 
      61            1 :   CoordMapping const mapping(grid, 2);
      62            1 :   std::vector<Coord> galaxies = grid.findAll('#');
      63            1 :   std::ranges::transform(galaxies, galaxies.begin(), mapping);
      64              : 
      65            1 :   int64_t sum = 0;
      66          434 :   for (auto it = galaxies.begin(); it != galaxies.end(); ++it)
      67        93961 :     for (auto it2 = std::next(it); it2 != galaxies.end(); ++it2)
      68        93528 :       sum += std::abs(it->x() - it2->x()) + std::abs(it->y() - it2->y());
      69              : 
      70            1 :   return std::to_string(sum);
      71            1 : }
      72              : 
      73            1 : template <> std::string solvePart2<2023, 11>(std::string_view const input) {
      74            1 :   LinewiseInput lines(input);
      75            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
      76            1 :   CoordMapping const mapping(grid, 1000000);
      77            1 :   std::vector<Coord> galaxies = grid.findAll('#');
      78            1 :   std::ranges::transform(galaxies, galaxies.begin(), mapping);
      79              : 
      80            1 :   int64_t sum = 0;
      81          434 :   for (auto it = galaxies.begin(); it != galaxies.end(); ++it)
      82        93961 :     for (auto it2 = std::next(it); it2 != galaxies.end(); ++it2)
      83        93528 :       sum += std::abs(it->x() - it2->x()) + std::abs(it->y() - it2->y());
      84              : 
      85            1 :   return std::to_string(sum);
      86            1 : }