Day 08 - Playground

Language: Rust

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

Part 1: The input is a list of 3D coordinates. Connect the K shortest pairs by Euclidean distance, then multiply the sizes of the three largest resulting connected components.

Formally, given points $p_i = (x_i, y_i, z_i)$, the edge weight between two points is:

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

This looks like an MST problem but it’s slightly different. You’re not building a spanning tree, you’re just adding the first K edges in order and looking at the resulting partition. The tool is still the same though: sort edges by $w$ and union with DSU.

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

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

The input is small enough that brute force pairwise distances plus sorting is fine.

Part 2: Keep unioning edges in order until the entire graph becomes one connected component, then use the final merging edge to compute the answer.

Starting with $c_0 = n$ components, each successful union reduces the count by 1. Stop when $c = 1$:

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

I initially overcomplicated this in my head, expecting some graph traversal. But DSU is already tracking connectivity, so the stopping condition is purely combinatorial. Both parts are really the same idea with a different stopping rule: Part 1 stops after K edges, Part 2 stops when everything merges into one component.

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

No C writeup yet.