Advent of Code 2025 Day 8

Day 8: Playground

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

You are standing in a large playground the elves are decorating with lights. The already put up junction boxes, but they aren’t powered yet.

The input for today is a list of all the junction box locations in 3D space.

An example input looks like this:

162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689

Each line is an X,Y,Z coordinate, so the box on the first line is located at X=162, Y=817, Z=812.

The elves want to focus on connecting pairs of boxes (by using lights) that are as close together as possible (using staight-line distance).

Connecting boxes together makes them part of the same circuit, which means elctricity can flow between them, and the lights … well, light up.

Parsing

What did you say? Represent a point in 3D space? Point! The parsed input is a list of Points.

#[derive(Debug, Clone, Copy, Hash, Eq, Ord, PartialEq, PartialOrd)]
struct Point {
    x: usize,
    y: usize,
    z: usize,
}

fn parse(input: &str) -> Vec<Point> {
    input
        .lines()
        .map(|line| {
            let mut parts = line.split(',');
            Point {
                x: parts.next().unwrap().parse().unwrap(),
                y: parts.next().unwrap().parse().unwrap(),
                z: parts.next().unwrap().parse().unwrap(),
            }
        })
        .collect()
}

Part 1

Connect 1000 pairs of junction boxes.
The question asks what number you get when you multiply the sizes of the 3 largest circuits.

This is a disjoint set union problem! Before coding today, I read a great resource that explains what that is, how you code one, and even how you optimize one for speed.

Helpers

First, a helper to calculate distances, and one to sort the points by it.

use itertools::Itertools;

impl Point {
    fn dist_squared(&self, other: &Point) -> usize {
        self.x.abs_diff(other.x).pow(2)
            + self.y.abs_diff(other.y).pow(2)
            + self.z.abs_diff(other.z).pow(2)
    }
}

fn get_sorted_pairs(points: &[Point]) -> Vec<(usize, usize)> {
    (0..points.len())
        .tuple_combinations()
        .sorted_by_key(|&(a, b)| points[a].dist_squared(&points[b]))
        .collect()
}

Next, some functions to help implement that Disjoint Set Union.

fn find(parents: &mut [usize], id: usize) -> usize {
    if id != parents[id] {
        parents[id] = find(parents, parents[id]);
    }
    parents[id]
}

fn merge(parents: &mut [usize], a: usize, b: usize) {
    let a_root = find(parents, a);
    let b_root = find(parents, b);
    if a_root != b_root {
        parents[b_root] = a_root;
    }
}

First, I merge the first 1000 pairs.

At the end I calculate the size of each root in the set union, and calculate the product of the 3 largest ones.

fn part_1(input: &str) -> usize {
    let points = parse(input);
    let pairs = get_sorted_pairs(&points);

    // vec where parent of an index is its value
    let mut parents: Vec<usize> = (0..points.len()).collect();

    for &(a, b) in pairs.iter().take(1_000) {
        merge(&mut parents, a, b);
    }

    let mut sizes = vec![0; points.len()];
    for id in 0..points.len() {
        let root_id = find(&mut parents, id);
        sizes[root_id] += 1;
    }

    sizes.iter().sorted().rev().take(3).product()
}

Part 2

You’ll need to keep connecting junction boxes with strings of lights until every box is in the same circuit.

The question asks what number you get when you multiply the x coordinate for the last pair of boxes you connect.

If a pair isn’t already in the same circuit, I connect the 2 boxes. I stop the loop and return the answer once every box is connected.

fn part_2(input: &str) -> usize {
    let points = parse(input);
    let pairs = get_sorted_pairs(&points);

    let mut parents: Vec<usize> = (0..points.len()).collect();
    let mut count = 0;

    for (a, b) in pairs {
        if find(&mut parents, a) != find(&mut parents, b) {
            count += 1;
            if count == points.len() - 1 {
                return points[a].x * points[b].x;
            }
            merge(&mut parents, a, b);
        }
    }

    panic!("no solution")
}

Final code

1
use itertools::Itertools;
2

3
struct Point {
4
    x: usize,
5
    y: usize,
6
    z: usize,
7
}
8

9
impl Point {
10
    fn dist_squared(&self, other: &Point) -> usize {
11
        self.x.abs_diff(other.x).pow(2)
12
            + self.y.abs_diff(other.y).pow(2)
13
            + self.z.abs_diff(other.z).pow(2)
14
    }
15
}
16

17
fn parse(input: &str) -> Vec<Point> {
18
    input
19
        .lines()
20
        .map(|line| {
21
            let mut parts = line.split(',');
22
            Point {
23
                x: parts.next().unwrap().parse().unwrap(),
24
                y: parts.next().unwrap().parse().unwrap(),
25
                z: parts.next().unwrap().parse().unwrap(),
26
            }
27
        })
28
        .collect()
29
}
30

31
fn get_sorted_pairs(points: &[Point]) -> Vec<(usize, usize)> {
32
    (0..points.len())
33
        .tuple_combinations()
34
        .sorted_by_key(|&(a, b)| points[a].dist_squared(&points[b]))
35
        .collect()
36
}
37

38
pub fn part_1(input: &str) -> usize {
39
    let points = parse(input);
40
    let pairs = get_sorted_pairs(&points);
41

42
    let mut parents: Vec<usize> = (0..points.len()).collect();
43

44
    for &(a, b) in pairs.iter().take(1_000) {
45
        merge(&mut parents, a, b);
46
    }
47

48
    let mut sizes = vec![0; points.len()];
49
    for id in 0..points.len() {
50
        let root_id = find(&mut parents, id);
51
        sizes[root_id] += 1;
52
    }
53

54
    sizes.iter().sorted().rev().take(3).product()
55
}
56

57
fn find(parents: &mut [usize], id: usize) -> usize {
58
    if id != parents[id] {
59
        parents[id] = find(parents, parents[id]);
60
    }
61
    parents[id]
62
}
63

64
fn merge(parents: &mut [usize], a: usize, b: usize) {
65
    let a_root = find(parents, a);
66
    let b_root = find(parents, b);
67
    if a_root != b_root {
68
        parents[b_root] = a_root;
69
    }
70
}
71

72
pub fn part_2(input: &str) -> usize {
73
    let points = parse(input);
74
    let pairs = get_sorted_pairs(&points);
75

76
    let mut parents: Vec<usize> = (0..points.len()).collect();
77
    let mut count = 0;
78

79
    for (a, b) in pairs {
80
        if find(&mut parents, a) != find(&mut parents, b) {
81
            count += 1;
82
            if count == points.len() - 1 {
83
                return points[a].x * points[b].x;
84
            }
85
            merge(&mut parents, a, b);
86
        }
87
    }
88

89
    panic!("no solution")
90
}

Date

Tagged

Part of series

Older post

Newer post