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