Day 08 - Playground

Language: Rust

Problem https://adventofcode.com/2025/day/8

This one finally felt like my territory.

The story is cute, but the math is straightforward. You’re given points in $\mathbb{R}^3$, you define a complete weighted graph on them, and then you keep adding edges in increasing weight order while tracking connected components.

Formally:

• Points: $p_i = (x_i, y_i, z_i)$
• Complete graph $G = (V, E)$ with $V = \{0,\dots, n - 1\}$

Edge weight:

$w(i, j) = ||p_i - p_j||_2 = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2}$

Then everything becomes “sort edges by $w$ and union components.

Part 1: Part 1 asks you to take the $K$ shortest edges (in the real input $K = 1000$, in the sample it’s 10), union their endpoints, then look at the connected component sizes and multiply the top three.

What I liked here is that it looks like an MST problem, but it’s slightly different, because you are not stopping at $n - 1$ edges, and you don’t care about the final tree weight. You only care about the partition of $V$ after adding the first $K$ edges.

Still, the tool is the same as Kruskal, I sorted the edges by weight and use DSU.

My steps:

1. Parse points $p_i$
2. Compute all pairwise distances $w(i, j)$ for $i < j$
3. Sort edges ascending by distance
4. Initialize the Union-Find with $n$ singleton sets
5. Union endpoints for the first $K$ edges
6. Extract component sizes and multiply top 3

The key “Kruskal-like” part is:

for edge in edges.iter().take(limit) {
    uf.union(edge.i, edge.j);
}

After that, component extraction is just finding roots and counting sizes.

Part 2: Part 2 is to keep applying Kruskal unions until the graph becomes connected, and then use the last successful union edge to compute the requested output.

The mathematical process is:

• Start with $n$ components
• Each successful union reduces the number of components by 1
• The first time I reach 1 component, the current edge is the “final merge”

So instead of building an adjacency list or running graph traversal, I tracked:

$c_0 = n, c \leftarrow c - 1$ for each successful union

Stop when $c = 1$

That’s the part I initially overcomplicated in my head. I was expecting graph stuff, but DSU already is the graph connectivity tracker.

It looks something like this:

let mut components = n;

for edge in edges {
    if uf.union(edge.i, edge.j) {
        components -= 1;
        if components == 1 {
            let x1 = points[edge.i][0] as usize;
            let x2 = points[edge.j][0] as usize;
            return (x1 * x2).to_string()
        }
    }
}

The stopping condition is purely combinatorial.

Final thoughts This day was mostly about spotting the structure early. Once it clicked that this is just a complete Euclidean graph, the solution naturally became Kruskal with a DSU.

Part 1 stops after a fixed number of shortest edges, while Part 2 continues until everything merges into one component. Same idea, different stopping rule.

Pairwise distances are quadratic in theory, but the input is small enough that brute force plus sorting is fine,

Solution: https://github.com/Elyrial/AdventOfCode/blob/main/src/solutions/year2025/day08.rs

No C writeup yet.