From 2e9d0706ec4cdfa7171dd079d497cd81ee03bd36 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Mon, 8 Dec 2025 12:43:10 +0100
Subject: aoc 2025, day 8, part 2

---
 2025/src/day08.cpp | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)

(limited to '2025')

diff --git a/2025/src/day08.cpp b/2025/src/day08.cpp
index 366d827..7a3c3b1 100644
--- a/2025/src/day08.cpp
+++ b/2025/src/day08.cpp
@@ -28,12 +28,16 @@ public:
 		return parent_[n];
 	}
 
-	void unite(size_t a, size_t b)
+	bool unite(size_t a, size_t b)
 	{
 		a = find(a);
 		b = find(b);
 
-		parent_[b] = a;
+		if ( a != b ) {
+			parent_[b] = a;
+			return true;
+		}
+		return false;
 	}
 
 private:
@@ -112,6 +116,35 @@ part1(const vector<Pos>& list)
 	cout << "Part 1: " << sizes[0] * sizes[1] * sizes[2] << '\n';
 }
 
+void
+part2(const vector<Pos>& list)
+{
+	using Dist = tuple<double, size_t, size_t>; // (Distanz, Von, Nach)
+
+	// Distanzen paarweise erfassen...
+	vector<Dist> dists;
+	for ( size_t i = 0; i != list.size(); ++i ) {
+		for ( size_t j = i + 1; j != list.size(); ++j ) {
+			dists.emplace_back(get_distance(list[i], list[j]), i, j);
+		}
+	}
+
+	// ... und nach Distanz sortieren
+	ranges::sort(dists);
+
+	UnionFind unionFind(list.size());
+
+	size_t count = 1;
+	for ( auto [dist, a, b]: dists ) {
+		if ( unionFind.unite(a, b) ) {
+			if ( ++count == list.size() ) {
+				cout << "Part 2: " << get<0>(list[a]) * get<0>(list[b]) << '\n';
+				return;
+			}
+		}
+	}
+}
+
 } // namespace
 
 int
@@ -119,4 +152,5 @@ main()
 {
 	auto data = read_file("data/day08.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3