Problem

Read it here

tl;dr

You have junction boxes at 3D coordinates. Connect pairs of boxes that are closest together (by straight-line distance). When two boxes are connected, they’re in the same circuit.

Part 1: After making the 1000 shortest connections, multiply together the sizes of the three largest circuits.

Example:

162,817,812
57,618,57
906,360,560
...

Process:

1. Find the two closest boxes → connect them (now 1 circuit with 2 boxes, rest are isolated)
2. Find the next closest pair that aren’t already connected → connect them
3. Continue until you’ve made N connections
4. Count circuit sizes, multiply the top 3

Example result: After 10 connections, circuits are sizes [5, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1]. Top 3: 5 × 4 × 2 = 40

---

Part 2: Continue connecting until all boxes are in one circuit. Multiply the X coordinates of the last two boxes you connect.

Example: The connection that merges everything is between boxes at 216,146,977 and 117,168,530. Answer: 216 × 117 = 25272

---

My Solution (Handcrafted)

I recognized this as a Union-Find problem. My approach uses a HashMap<Coordinate, Coordinate> to store parent relationships.

Part 1

pub fn solve_1(filename: &str, connecting_pairs: usize) -> u128 {
    let coordinates = Self::read_input(filename);

    // Calculate all pairwise distances
    let mut distances: Vec<(Coordinate, Coordinate, u64)> = vec![];
    for i in 0..coordinates.len() {
        for j in i + 1..coordinates.len() {
            distances.push((
                coordinates[i],
                coordinates[j],
                coordinates[i].distance_to(&coordinates[j]),
            ));
        }
    }

    distances.sort_by_key(|(_, _, distance)| *distance);

    let mut circuits: HashMap<Coordinate, Coordinate> = HashMap::new();

    // Connect the first N pairs
    for (coordinate_a, coordinate_b, _) in distances.iter().take(connecting_pairs) {
        // Handle 4 cases: both new, A exists, B exists, both exist
        if Self::find_parent(&circuits, coordinate_a)
            != Self::find_parent(&circuits, coordinate_b) {
            Self::union(&mut circuits, coordinate_a, coordinate_b);
        }
    }

    // Count circuit sizes and multiply top 3
    // ...
}

Union-Find Implementation

My find_parent is recursive but doesn’t do path compression:

fn find_parent(
    circuits: &HashMap<Coordinate, Coordinate>,
    coordinate: &Coordinate,
) -> Coordinate {
    let parent = *circuits.get(coordinate).unwrap();
    if *coordinate == parent {
        return parent; // root
    }
    return Self::find_parent(circuits, &parent);
}

My union function is inefficient — it iterates through all nodes to update parents:

fn union(
    circuits: &mut HashMap<Coordinate, Coordinate>,
    coordinate_a: &Coordinate,
    coordinate_b: &Coordinate,
) {
    let a_root = Self::find_parent(circuits, coordinate_a);
    let b_root = Self::find_parent(circuits, coordinate_b);

    // O(n) - update all nodes in A's tree to point to B's root
    for (coordinate, _) in circuits.clone().into_iter() {
        if Self::find_parent(circuits, &coordinate) == a_root {
            circuits.insert(coordinate, b_root);
        }
    }
}

Part 2

Reuse Part 1 logic with a counter to track when all boxes are in one circuit:

let mut circuit_count = coordinates.len();

for (coordinate_a, coordinate_b, _) in distances.iter() {
    if /* connection merges two circuits */ {
        circuit_count -= 1;
        if circuit_count == 1 {
            return coordinate_a.x * coordinate_b.x;
        }
    }
}

---

Gemini’s Solution

Gemini implemented a proper Union-Find data structure with optimizations.

Union-Find Data Structure

struct UnionFind {
    parent: Vec<usize>,  // parent[i] = parent of node i
    size: Vec<usize>,    // size[i] = size of set containing i
    count: usize,         // number of disjoint sets
}

Path Compression

The find method uses path compression for O(α(n)) amortized time:

fn find(&mut self, i: usize) -> usize {
    if self.parent[i] == i {
        i
    } else {
        let root = self.find(self.parent[i]);
        self.parent[i] = root;  // Path compression!
        root
    }
}

Union by Size

Merges smaller set into larger set to keep trees balanced:

fn union(&mut self, i: usize, j: usize) -> bool {
    let root_i = self.find(i);
    let root_j = self.find(j);

    if root_i != root_j {
        if self.size[root_i] < self.size[root_j] {
            self.parent[root_i] = root_j;
            self.size[root_j] += self.size[root_i];
        } else {
            self.parent[root_j] = root_i;
            self.size[root_i] += self.size[root_j];
        }
        self.count -= 1;
        true
    } else {
        false
    }
}

Part 1 & Part 2

Both parts use the same structure — just different stopping conditions:

// Part 1: Connect first N pairs
for i in 0..limit {
    uf.union(u, v);
}

// Part 2: Connect until count == 1
for (_, u, v) in edges {
    if uf.union(u, v) && uf.count == 1 {
        return points[u].x * points[v].x;
    }
}

---

Comparison

Aspect	My Solution	Gemini’s Solution
Data structure	HashMap<Coordinate, Coordinate>	UnionFind struct with Vec
Find	Recursive, no path compression	Path compression (O(α(n)))
Union	O(n) - updates all nodes	O(α(n)) - union by size
Set tracking	Manual counter	Built-in count field
Key type	Coordinate (custom type)	usize (indices)

---

Reflection

I correctly identified this as a Union-Find problem, but my implementation was naive. The O(n) union operation is a major bottleneck — for 1000 connections, that’s potentially 1000 × 1000 = 1M operations.

Gemini’s solution uses the textbook optimizations:

• Path compression makes find nearly O(1)
• Union by size keeps trees balanced
• Built-in set counter eliminates manual tracking

The key insight: when you have indices (0..n), use a Vec instead of a HashMap. The UnionFind struct is a standard pattern worth memorizing.

Time spent: ~25 minutes