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