From 56e890cec0a28c0a485212ccebfaf774235a79a2 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 3 Jan 2024 23:35:54 +0100
Subject: prepare for more puzzles ... :)

---
 2023/src/day22.cpp | 157 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 157 insertions(+)
 create mode 100644 2023/src/day22.cpp

(limited to '2023/src/day22.cpp')

diff --git a/2023/src/day22.cpp b/2023/src/day22.cpp
new file mode 100644
index 0000000..1afb994
--- /dev/null
+++ b/2023/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);
+}
-- 
cgit v1.3