From 5f41cc49734c7d1ef304be37b60e19349b314193 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Mon, 8 Dec 2025 23:58:23 +0100
Subject: aoc 2025, day 8, cleanup

---
 2025/src/day08.cpp | 83 ++++++++++++++++++++++++++++++------------------------
 1 file changed, 46 insertions(+), 37 deletions(-)

diff --git a/2025/src/day08.cpp b/2025/src/day08.cpp
index 7a3c3b1..6fa3cd6 100644
--- a/2025/src/day08.cpp
+++ b/2025/src/day08.cpp
@@ -2,7 +2,6 @@
 #include <filesystem>
 #include <fstream>
 #include <iostream>
-#include <map>
 #include <tuple>
 #include <vector>
 
@@ -14,6 +13,7 @@ class UnionFind {
 public:
 	explicit UnionFind(size_t size)
 	    : parent_(size)
+	    , size_(size, 1)
 	{
 		for ( size_t i = 0; i != size; ++i ) {
 			parent_[i] = i;
@@ -33,18 +33,39 @@ public:
 		a = find(a);
 		b = find(b);
 
-		if ( a != b ) {
-			parent_[b] = a;
-			return true;
+		if ( a == b ) {
+			return false;
 		}
-		return false;
+
+		if ( size_[a] < size_[b] ) {
+			swap(a, b);
+		}
+
+		parent_[b] = a;
+		size_[a] += size_[b];
+
+		return true;
+	}
+
+	[[nodiscard]]
+	vector<size_t> get_component_sizes() const
+	{
+		vector<size_t> sizes;
+		for ( size_t i = 0; i != parent_.size(); ++i ) {
+			if ( parent_[i] == i ) {
+				sizes.emplace_back(size_[i]);
+			}
+		}
+		return sizes;
 	}
 
 private:
 	vector<size_t> parent_;
+	vector<size_t> size_;
 };
 
-using Pos = tuple<long, long, long>;
+using Pos  = tuple<long, long, long>;       // (x, y, z)
+using Dist = tuple<double, size_t, size_t>; // (Distanz, Von, Nach)
 
 vector<Pos>
 read_file(const filesystem::path& filename)
@@ -74,11 +95,9 @@ get_distance(const Pos& pos1, const Pos& pos2)
 	return hypot(x1 - x2, y1 - y2, z1 - z2);
 }
 
-void
-part1(const vector<Pos>& list)
+vector<Dist>
+get_distances(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 ) {
@@ -90,28 +109,26 @@ part1(const vector<Pos>& list)
 	// ... und nach Distanz sortieren
 	ranges::sort(dists);
 
+	return dists;
+}
+
+void
+part1(const vector<Pos>& list)
+{
+	const auto dists = get_distances(list);
+
 	UnionFind unionFind(list.size());
 
-	// die kürzesten 1000 Elemente verbinden
+	// die nächsten 1000 Paare verbinden
 	for ( size_t i = 0; i != 1000; ++i ) {
 		const auto [dist, a, b] = dists[i];
 		unionFind.unite(a, b);
 	}
 
-	// die Längen der Verbindungen zählen
-	map<size_t, size_t> compSizes;
-	for ( size_t i = 0; i != list.size(); ++i ) {
-		compSizes[unionFind.find(i)]++;
-	}
-
-	// Größen finden
-	vector<size_t> sizes;
-	for ( const auto& [root, size]: compSizes ) {
-		sizes.emplace_back(size);
-	}
+	auto sizes = unionFind.get_component_sizes();
 
 	// Sortieren
-	ranges::sort(sizes, greater<>());
+	nth_element(sizes.begin(), sizes.begin() + 3, sizes.end(), greater<>());
 
 	cout << "Part 1: " << sizes[0] * sizes[1] * sizes[2] << '\n';
 }
@@ -119,25 +136,17 @@ part1(const vector<Pos>& list)
 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);
+	const auto dists = get_distances(list);
 
 	UnionFind unionFind(list.size());
 
-	size_t count = 1;
+	// Alle Paare verbinden ...
+	size_t unions = 0;
 	for ( auto [dist, a, b]: dists ) {
 		if ( unionFind.unite(a, b) ) {
-			if ( ++count == list.size() ) {
+			// ... beim Letzten abbrechen
+			++unions;
+			if ( unions == list.size() - 1 ) {
 				cout << "Part 2: " << get<0>(list[a]) * get<0>(list[b]) << '\n';
 				return;
 			}
-- 
cgit v1.3