aoc 2025, day 8, part 2

1 files changed, 36 insertions, 2 deletions

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);
 }