A Statistically Good Solution to Advent of Code 2025/08

Advent of Code 2025/08: Playground

This day’s problem reduces nicely to finding the Minimum Spanning Tree (MST), where the weight of a given edge $\left(𝑢,𝑣\right)$ is its Euclidean length $\Vert 𝑢-𝑣\Vert$.

Unfortunately, the specific features of the MST required to solve the problem restrict us to using Kruskal’s algorithm, so an $\mathrm{𝒪︀}\left(|𝐸|log|𝑉|\right)$ solution is the best we can do.

The Proper Solution

To solve this problem in the general case, one must consider each of the $\left(\genfrac{}{}{0ex}{}{𝑛}{2}\right)$ Euclidean distances between the points provided. It is possible to do this somewhat efficiently, but it still limits performance.

If an oracle could tell us the longest edge in the MST, we could ignore any edges longer than that and dramatically reduce the amount of computation we have to perform.

So… can we do that?

A Statistical Approach

Assumptions

Having a quick look at the input, we can see that the points lie roughly uniformly in an approximate cube with side length $100000$. For my input, the actual dimensions are $\left(99859,99496,99777\right)$. To be on the safe side, we’ll pick the longest side length as the side length of the cube.

Prior Results

Dette and Henze [1] showed that the random variable ${𝐷}_{𝑛}$, representing the length of the longest edge in the nearest-neighbour graph on $𝑛$ points in the unit $𝑑$-cube, follows the limit law

where $\mathrm{𝒢︀}$ is the Gumbel distribution.

In other words, that function of ${𝐷}_{𝑛}$ converges to a particular probability distribution that we can more easily analyse.

Another important result is that of Penrose [2], who showed that as $𝑛⟶\infty$, $\mathbb{P}\left({𝐷}_{𝑛}={𝑀}_{𝑛}^{\prime }\right)⟶1$, where ${𝑀}_{𝑛}^{\prime }$ is the random variable representing the longest edge in the MST on the same set of points.

Using these results, we can begin to work towards a more concrete solution.

Derivation

Let

from above.

By Dette and Henze [1] and the CDF of the Gumbel distribution, we know

We want to solve for $𝑚$, given some $𝑛$ and $𝛿$ such that $\mathbb{P}\left({𝑀}_{𝑛}^{\prime }\le 𝑚\right)\ge 1-𝛿$.

So…

Substituting $𝑤$:

Solving for $𝑚$, we see:

Since we are looking for $\mathbb{P}\left({𝑀}_{𝑛}^{\prime }\le 𝑚\right)$, we can take the strictest bound on $𝑚$ and assign equality.

Interpretation

Recall the setup we outlined earlier: We have $𝑛$ random points, uniformly distributed in the unit cube ${\left[0,1\right]}^3$.

We’ve just shown that the longest edge in the MST on those points does not exceed $𝑚$ with confidence $1-𝛿$.

Since $𝑚$ increases only slowly with increased confidence levels, as shown by Figure 1, we can compute $𝑚$ with high confidence without incurring a huge computational cost.

Application to The Problem

We can now use this result to speed up our solution to the problem!

Finding the Cube

First, we must determine the size of the cube our points lie within. To do this, we iterate over every point and keep track of the smallest and largest values found for the $𝑥$, $𝑦$ and $𝑧$ components.

fn min_max(points: &[(u32, u32, u32)]) -> ((u32, u32, u32), (u32, u32, u32)) {
    points.iter().fold(
        ((u32::MAX, u32::MAX, u32::MAX), (u32::MIN, u32::MIN, u32::MIN)),
        |(min, max), p| {
            let min = (min.0.min(p.0), min.1.min(p.1), min.2.min(p.2));
            let max = (max.0.max(p.0), max.1.max(p.1), max.2.max(p.2));

            (min, max)
        },
    )
}

Then, we can pick the longest edge to use as the side length of our cube.

let point_extent = (
    point_max.0 - point_min.0,
    point_max.1 - point_min.1,
    point_max.2 - point_min.2,
);

let max_dim = point_extent.0.max(point_extent.1).max(point_extent.2);

There may be better ways of doing this, especially if you could guarantee that the points lie within a cube, but I doubt it matters in practice.

Using the Result

Calculating $𝑚$ with what we’ve found is quite easy:

const DELTA: f64 = 0.1;

// Obviously f64::cbrt() is not const. Why would it be?
// const K: f64 = 6.0 / std::f64::consts::PI.cbrt();
const K: f64 = 4.09670437953;

const K_ON_DELTA: f64 = K / DELTA;

// This obviously isn't const either.
// const LN_K_ON_DELTA: f64 = K_ON_DELTA.ln();
const LN_K_ON_DELTA: f64 = 3.71276793360;

fn expected_max_mst_edge_len(n: f64) -> f64 {
    let ln_n = n.ln();
    let num = 1.5 * LN_K_ON_DELTA + ln_n - ln_n.ln();
    let den = n * std::f64::consts::PI;
    (num / den).cbrt()
}

That function gives us $𝑚$ for a unit cube, but we want the equivalent value for our non-unit cube. Fortunately, we can simply scale the length by the side length we computed earlier.

let cutoff = expected_max_mst_edge_len(num_points as f64) * max_dim;

Now, any edges longer than cutoff can be completely ignored in our MST construction!

Benchmarks

Before: 485.74 µs
After: 297.41 µs

A 38.77% performance improvement! Not too bad.

Limitations

Since the threshold is only a statistical estimate, not a guarantee, this is not guaranteed to give the correct answer in every case. The most obvious degenerate case is having one point at $\left(0,0,0\right)$ and the remaining $𝑛-1$ points at $\left(𝑙,𝑙,𝑙\right)$.

If the points were placed with some known distribution, it may be possible to re-derive something similar to what Dette and Henze [1] show, but that would be extremely tedious.