1 files 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;
                         }