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              : #include <ranges>
       8              : #include <re2/re2.h>
       9              : 
      10              : #include <algorithm>
      11              : #include <string>
      12              : #include <string_view>
      13              : #include <vector>
      14              : 
      15              : namespace rng = std::ranges;
      16              : 
      17              : namespace {
      18              : 
      19              : class Brick {
      20              : public:
      21         2910 :   Brick(std::string_view const str) {
      22         2910 :     static RE2 const pattern = R"((\d+),(\d+),(\d+)~(\d+),(\d+),(\d+))";
      23         2910 :     ASSUME(RE2::FullMatch(str, pattern, &_start.x(), &_start.y(), &_start.z(), &_end.x(), &_end.y(),
      24         2910 :                           &_end.z()));
      25              : 
      26         2910 :     ASSUME(_start.x() <= _end.x());
      27         2910 :     ASSUME(_start.y() <= _end.y());
      28         2910 :     ASSUME(_start.z() <= _end.z());
      29         2910 :   }
      30              : 
      31      4386594 :   [[nodiscard]] Vec3<int> const &start() const { return _start; }
      32      4354926 :   [[nodiscard]] Vec3<int> const &end() const { return _end; }
      33              : 
      34         2910 :   void dropToLvl(int const lvl) {
      35         2910 :     int d = _start.z() - lvl;
      36         2910 :     _start.z() -= d;
      37         2910 :     _end.z() -= d;
      38         2910 :   }
      39              : 
      40              : private:
      41              :   Vec3<int> _start;
      42              :   Vec3<int> _end;
      43              : };
      44              : 
      45            2 : void settleBricks(std::vector<Brick> &bricks) {
      46            2 :   Vec3<int> min = bricks.front().start();
      47            2 :   Vec3<int> max = bricks.front().end();
      48         2910 :   for (Brick const &b : bricks) {
      49         2910 :     min.x() = std::min(min.x(), b.start().x());
      50         2910 :     min.y() = std::min(min.y(), b.start().y());
      51         2910 :     min.z() = std::min(min.z(), b.start().z());
      52         2910 :     max.x() = std::max(max.x(), b.end().x());
      53         2910 :     max.y() = std::max(max.y(), b.end().y());
      54         2910 :     max.z() = std::max(max.z(), b.end().z());
      55         2910 :   }
      56              : 
      57            2 :   ASSUME(min.x() >= 0);
      58            2 :   ASSUME(min.y() >= 0);
      59              : 
      60            2 :   Grid2d<int> heightMap(max.x() + 1, max.y() + 1, 1);
      61              : 
      62        67132 :   std::ranges::sort(bricks, std::ranges::less{}, [](Brick const &b) { return b.start().z(); });
      63              : 
      64         2910 :   for (Brick &b : bricks) {
      65         2910 :     int maxHeight = 0;
      66         8480 :     for (int y = b.start().y(); y <= b.end().y(); ++y)
      67        13678 :       for (int x = b.start().x(); x <= b.end().x(); ++x)
      68         8108 :         maxHeight = std::max(heightMap[x, y], maxHeight);
      69         2910 :     b.dropToLvl(maxHeight + 1);
      70         8480 :     for (int y = b.start().y(); y <= b.end().y(); ++y)
      71        13678 :       for (int x = b.start().x(); x <= b.end().x(); ++x)
      72         8108 :         heightMap[x, y] = b.end().z();
      73         2910 :   }
      74            2 : }
      75              : 
      76              : class SupportInfo {
      77              : public:
      78              :   SupportInfo(std::vector<Brick> const &bricks)
      79            2 :       : _supports(bricks.size()), _isSupportedBy(bricks.size()) {
      80         2912 :     for (size_t i = 0; i < bricks.size(); ++i)
      81      4236960 :       for (size_t j = 0; j < bricks.size(); ++j) {
      82      4234050 :         if (bricks[i].end().z() + 1 != bricks[j].start().z())
      83      4206546 :           continue;
      84        27504 :         if (bricks[i].end().x() < bricks[j].start().x() ||
      85        27504 :             bricks[i].start().x() > bricks[j].end().x())
      86        19086 :           continue;
      87         8418 :         if (bricks[i].end().y() < bricks[j].start().y() ||
      88         8418 :             bricks[i].start().y() > bricks[j].end().y())
      89         5274 :           continue;
      90         3144 :         _supports[i].insert(j);
      91         3144 :         _isSupportedBy[j].insert(i);
      92         3144 :       }
      93            2 :   }
      94              : 
      95         1455 :   bool safeToDisentegrate(size_t const idx) {
      96         1455 :     return rng::all_of(_supports[idx],
      97         1455 :                        [this](size_t const i) { return _isSupportedBy[i].size() > 1u; });
      98         1455 :   }
      99              : 
     100         1455 :   size_t numFallingBricks(size_t const brickIdx) {
     101         1455 :     std::set<size_t> fallingBricks;
     102         1455 :     fallingBricks.insert(brickIdx);
     103         1455 :     for (size_t const i : _supports[brickIdx])
     104         1572 :       addFallingBricks(i, fallingBricks);
     105              : 
     106         1455 :     return fallingBricks.size() - 1u;
     107         1455 :   }
     108              : 
     109              : private:
     110        78255 :   void addFallingBricks(size_t brickIdx, std::set<size_t> &fallingBricks) {
     111        78255 :     if (fallingBricks.contains(brickIdx) || !rng::includes(fallingBricks, _isSupportedBy[brickIdx]))
     112         7253 :       return;
     113        71002 :     fallingBricks.insert(brickIdx);
     114        71002 :     for (size_t const i : _supports[brickIdx])
     115        76683 :       addFallingBricks(i, fallingBricks);
     116        71002 :   }
     117              : 
     118              :   std::vector<std::set<size_t>> _supports;
     119              :   std::vector<std::set<size_t>> _isSupportedBy;
     120              : };
     121              : 
     122              : } // namespace
     123              : 
     124            1 : template <> std::string solvePart1<2023, 22>(std::string_view const input) {
     125            1 :   LinewiseInput lines(input);
     126            1 :   std::vector<Brick> bricks(lines.begin(), lines.end());
     127            1 :   settleBricks(bricks);
     128            1 :   SupportInfo si(bricks);
     129              : 
     130            1 :   return std::to_string(rng::count_if(rng::views::iota(0u, bricks.size()),
     131         1455 :                                       [&](size_t const i) { return si.safeToDisentegrate(i); }));
     132            1 : }
     133              : 
     134            1 : template <> std::string solvePart2<2023, 22>(std::string_view const input) {
     135            1 :   LinewiseInput lines(input);
     136            1 :   std::vector<Brick> bricks(lines.begin(), lines.end());
     137            1 :   settleBricks(bricks);
     138            1 :   SupportInfo si(bricks);
     139              : 
     140            1 :   return std::to_string(rng::fold_left(
     141            1 :       rng::views::iota(0u, bricks.size()) |
     142         1455 :           rng::views::transform([&](size_t const i) { return si.numFallingBricks(i); }),
     143            1 :       0u, std::plus<>()));
     144            1 : }