From 3447cd58384cce987f6acd503a5202b3aa65c02d Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Mon, 8 Dec 2025 10:31:41 +0100
Subject: aoc 2025, day 8, part 1

---
 2025/src/day08.cpp | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 122 insertions(+)
 create mode 100644 2025/src/day08.cpp

diff --git a/2025/src/day08.cpp b/2025/src/day08.cpp
new file mode 100644
index 0000000..366d827
--- /dev/null
+++ b/2025/src/day08.cpp
@@ -0,0 +1,122 @@
+#include <cmath>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+class UnionFind {
+public:
+	explicit UnionFind(size_t size)
+	    : parent_(size)
+	{
+		for ( size_t i = 0; i != size; ++i ) {
+			parent_[i] = i;
+		}
+	}
+
+	size_t find(size_t n)
+	{
+		if ( parent_[n] != n ) {
+			parent_[n] = find(parent_[n]);
+		}
+		return parent_[n];
+	}
+
+	void unite(size_t a, size_t b)
+	{
+		a = find(a);
+		b = find(b);
+
+		parent_[b] = a;
+	}
+
+private:
+	vector<size_t> parent_;
+};
+
+using Pos = tuple<long, long, long>;
+
+vector<Pos>
+read_file(const filesystem::path& filename)
+{
+	ifstream file{ filename };
+
+	vector<Pos> list;
+
+	long x{};
+	long y{};
+	long z{};
+	char ch{};
+
+	while ( file >> x >> ch >> y >> ch >> z ) {
+		list.emplace_back(x, y, z);
+	}
+
+	return list;
+}
+
+double
+get_distance(const Pos& pos1, const Pos& pos2)
+{
+	const auto [x1, y1, z1] = pos1;
+	const auto [x2, y2, z2] = pos2;
+
+	return hypot(x1 - x2, y1 - y2, z1 - z2);
+}
+
+void
+part1(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());
+
+	// die kürzesten 1000 Elemente 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);
+	}
+
+	// Sortieren
+	ranges::sort(sizes, greater<>());
+
+	cout << "Part 1: " << sizes[0] * sizes[1] * sizes[2] << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+	auto data = read_file("data/day08.txt");
+	part1(data);
+}
-- 
cgit v1.3