From 64a43bcf7657c612f2d7bb0099610d59bf2a7b97 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Tue, 26 Dec 2023 14:41:03 +0100
Subject: Lösungen für Tag 22, Teil 1
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 makefile      |  3 +-
 src/day22.cpp | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 100 insertions(+), 1 deletion(-)
 create mode 100644 src/day22.cpp

diff --git a/makefile b/makefile
index a54e3aa..b6b03e8 100644
--- a/makefile
+++ b/makefile
@@ -20,7 +20,8 @@ all: bin/day01 \
 	 bin/day18 \
 	 bin/day19 \
 	 bin/day20 \
-	 bin/day21
+	 bin/day21 \
+	 bin/day22
 
 bin:
 	mkdir $@
diff --git a/src/day22.cpp b/src/day22.cpp
new file mode 100644
index 0000000..0ac5faf
--- /dev/null
+++ b/src/day22.cpp
@@ -0,0 +1,98 @@
+#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()
+{
+	auto puzzle = read_file("data/day22.txt");
+
+	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& item) { return supported_by[item].size() > 1; }) ) {
+			++number;
+		}
+	}
+	cout << number << endl;
+}
+
+int
+main()
+{
+	part1();
+}
-- 
cgit v1.3