1 files changed, 157 insertions, 0 deletions

diff --git a/src/day22.cpp b/src/day22.cpp
new file mode 100644
index 0000000..1afb994
--- /dev/null
+++ b/src/day22.cpp
@@ -0,0 +1,157 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <string>
+#include <vector>
+using namespace std;
+
+struct piece {
+        int x1, y1, z1;
+        int x2, y2, z2;
+};
+
+vector<piece>
+read_file(string_view filename)
+{
+        static const regex pattern{ R"((\d+),(\d+),(\d+)~(\d+),(\d+),(\d+))" };
+
+        fstream       input{ filename };
+        vector<piece> data;
+
+        for ( string line; getline(input, line); ) {
+                smatch matches;
+                if ( regex_search(line, matches, pattern) ) {
+                        data.emplace_back(piece{
+                            stoi(matches[1]),
+                            stoi(matches[2]),
+                            stoi(matches[3]),
+                            stoi(matches[4]),
+                            stoi(matches[5]),
+                            stoi(matches[6]) });
+                }
+        }
+        sort(data.begin(), data.end(), [](const auto& lhs, const auto& rhs) { return lhs.z1 < rhs.z1; });
+
+        return data;
+}
+
+void
+part1(vector<piece> puzzle)
+{
+        map<int, map<int, int>> grid;
+
+        map<size_t, vector<size_t>> supported_by;
+        map<size_t, vector<size_t>> supports;
+
+        for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
+                auto& piece = puzzle[idx];
+
+                int max_z = 0;
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                max_z = max(max_z, grid[x][y]);
+                        }
+                }
+
+                auto height = piece.z2 - piece.z1 + 1;
+
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                grid[x][y] = max_z + height;
+                        }
+                }
+
+                piece.z1 = max_z + 1;
+                piece.z2 = max_z + height;
+
+                for ( size_t idx2 = idx; idx2-- > 0; ) {
+                        if ( piece.x1 > puzzle[idx2].x2 || puzzle[idx2].x1 > piece.x2 ) {
+                                continue;
+                        }
+                        if ( piece.y1 > puzzle[idx2].y2 || puzzle[idx2].y1 > piece.y2 ) {
+                                continue;
+                        }
+                        if ( puzzle[idx].z1 == puzzle[idx2].z2 + 1 ) {
+                                supports[idx2].emplace_back(idx);
+                                supported_by[idx].emplace_back(idx2);
+                        }
+                }
+        }
+
+        long number = 0;
+        for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
+                if ( all_of(supports[idx].begin(), supports[idx].end(), [&](const auto& idx2) { return supported_by[idx2].size() > 1; }) ) {
+                        ++number;
+                }
+        }
+        cout << number << endl;
+}
+
+void
+part2(vector<piece> puzzle)
+{
+        map<int, map<int, int>> grid;
+
+        for ( auto& piece: puzzle ) {
+                int max_z = 0;
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                max_z = max(max_z, grid[x][y]);
+                        }
+                }
+
+                auto height = piece.z2 - piece.z1 + 1;
+
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                grid[x][y] = max_z + height;
+                        }
+                }
+
+                piece.z1 = max_z + 1;
+                piece.z2 = max_z + height;
+        }
+
+        int num = 0;
+        for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
+                map<int, map<int, int>> grid;
+
+                for ( size_t idx2 = 0; idx2 != puzzle.size(); ++idx2 ) {
+                        if ( idx == idx2 ) {
+                                continue;
+                        }
+
+                        const auto& piece = puzzle[idx2];
+
+                        int max_z = 0;
+                        for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                                for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                        max_z = max(max_z, grid[x][y]);
+                                }
+                        }
+
+                        auto height = piece.z2 - piece.z1 + 1;
+
+                        for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                                for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                        grid[x][y] = max_z + height;
+                                }
+                        }
+
+                        if ( piece.z1 != max_z + 1 ) {
+                                ++num;
+                        }
+                }
+        }
+        cout << num << endl;
+}
+
+int
+main()
+{
+        const auto puzzle = read_file("data/day22.txt");
+        part1(puzzle);
+        part2(puzzle);
+}