Advent of Code 2025 - Day 8

Day 8: Playground

Useful Links

‹

Concepts and Packages Demonstrated

BFS (Shortest Paths)Combinations NamedTuple List Comprehensions Kruskal's Algorithm (Wikipedia)

Problem Intro

Today we’re in a “Playground” of electrical junction boxes in 3D space. The Elves want to connect them up.

Our input is the 3D coordinates of the junction boxes. It looks like this:

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

When junction boxes are connected, they form a circuit. We need to connect the junction boxes that are closest to each other, using straight line distance.

So the core theme today is Graph Theory, specifically finding connected components and building a Minimum Spanning Tree (MST).

Part 1

What is the product of the sizes of the three largest circuits?

The Elves want us to connect the n pairs of junction boxes that are closest to each other.

Data Structures

First off, I’m using a NamedTuple to represent our junction boxes. Why? Because box.x is much more readable than box[0], especially when calculating distances. And it’s really fast.

class Box(NamedTuple):
    """ The location of a Junction Box in 3D space """
    x: int
    y: int
    z: int

We can create these easily using a list comprehension and the splat * operator. The splat operator “unpacks” the list of coordinates produced by map into individual arguments x, y, z for the Box constructor.

# point.split(',') -> ['1', '2', '3']
# map(int, ...) -> (1, 2, 3)
# Box(*(1, 2, 3)) -> Box(1, 2, 3)
boxes = [Box(*map(int, point.split(","))) for point in data]

Approach Overview

Here’s my overall plan:

Create a function that finds euclidean distance between two points
Get the distances for all pairs using itertools.combinations.
Sort the connections by distance and take the n shortest
Build an adjacency dictionary from these shortest connections - these are our connected boxes
Use BFS for all boxes, to build a list of circuits, leveraging our adjacency dictionary
Sort the circuits by size; largest first
Return the product of the sizes of the three largest circuits

Getting Distances

To find the distances between all pairs, I’m using itertools.combinations. This gives us every unique pair without duplicates. We then sort these connections by Euclidean distance.

I’m using a lambda function as the sort key. This anonymous function takes a pair of boxes x (which is a tuple (box1, box2)), calculates the distance between them, and uses that value for sorting.

# x is a tuple of (box1, box2)
connections.sort(key=lambda x: get_distance(x[0], x[1]))

Building the Graph: BFS for Connected Components

For Part 1, we connect the top 1000 closest pairs. This creates a graph where some boxes are connected to others, forming “circuits” (or connected components).

I used an Adjacency List (a dictionary mapping each box to a list of its neighbors) to represent these connections.

adj_dict = {box: [] for box in boxes}
for box1, box2 in connections[:num_shortest_connections]:
    adj_dict[box1].append(box2)
    adj_dict[box2].append(box1)

Then, to find the distinct circuits, I used a Breadth-First Search (BFS). We iterate through every box: if we haven’t visited it yet, it must be the start of a new circuit. We then flood-fill out from there to find every other box in that circuit.

visited = set()
circuits = [] 

for box in boxes:
    if box in visited:
        continue
        
    # Start a new circuit
    circuit = set() 
    queue = deque([box]) # BFS queue
    visited.add(box)
    
    while queue:
        current = queue.popleft()
        circuit.add(current)
        
        for neighbor in adj_dict[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    circuits.append(circuit)

Finally, we simply sort the list of circuits by length and multiply the top three. Nice!

Part 2

What is the product of the x coordinates of the two boxes that, when connected, reduce the number of circuits to 1?

For Part 2, we need to keep adding connections (shortest first) until the entire graph becomes a single connected component. We need to identify the last pair of boxes that resulted in this single circuit. Then, return the product of the x coordinates of these two boxes, as required by the puzzle.

Evolution of the Solution

My first thought was: “Can I just reuse the adjacency list from Part 1?”

However, Part 2 requires us to add connections one by one (shortest first) and check after every single connection if the graph successfully become one single circuit.

We can’t just connect all wires at once (like in Part 1), because we need to stop at the exact moment the graph becomes fully connected to identify the specific pair of boxes responsible.
If we used the Part 1 approach (add wire -> run full BFS), we would be re-scanning the entire graph thousands of times. That’s O(Edges * Nodes), which is incredibly inefficient.

So, I switched to the perfect tool for dynamic connectivity: Union-Find (also known as Disjoint Set Union or DSU). It allows us to merge sets and check connectivity in nearly constant time.

The CircuitNetwork Class

I implemented a CircuitNetwork class to manage our disjoint sets.

make_set (init): Initially, every box is its own leader. count = len(boxes).
find: Follows the chain of leaders up to the root. I included path compression, which makes subsequent lookups nearly instantaneous.
union: Connects two sets. If they were already connected, do nothing. If they were separate, make one the leader of the other and decrement our circuit count.

Here is the implementation:

class CircuitNetwork:
    """ Manages the set of disjoint circuits using Union-Find """
    def __init__(self, boxes):
        self.circuit_leader = {box: box for box in boxes}
        self.circuit_count = len(boxes)

    def find(self, box):
        """ Find the representative leader, with path compression """
        if self.circuit_leader[box] != box:
            self.circuit_leader[box] = self.find(self.circuit_leader[box])
        return self.circuit_leader[box]

    def union(self, box1, box2):
        """ Merge two circuits. Returns True if a merge happened. """
        leader1 = self.find(box1)
        leader2 = self.find(box2)

        if leader1 != leader2:
            self.circuit_leader[leader1] = leader2
            self.circuit_count -= 1
            return True 
        return False 

Kruskal’s Algorithm

This is essentially Kruskal’s Algorithm for finding a Minimum Spanning Tree! We iterate through our pre-sorted list of connections (edges) and apply union. The moment circuit_count drops to 1, we know we’ve found the final necessary connection.

uf = CircuitNetwork(boxes)

for box1, box2 in connections:
    if uf.union(box1, box2): # Connect them
        # If this connection reduced the number of circuits to 1, we are done
        if uf.circuit_count == 1:
            return box1.x * box2.x

Results

This approach is blazing fast because we don’t rebuild the graph; we just incrementally update our knowledge of the sets.

The final output looks something like:

Part 1 soln=12345
Part 2 soln=9876543210

The whole thing runs in about 0.2 seconds.

Bonus: Visualization

I couldn’t just solve this with a script and move on. Not when we have 3D coordinates! I had to see these circuits building themselves.

So I whipped up a Python script using matplotlib’s 3D plotting capabilities. It’s not just a pretty picture; it’s a direct visual debug of the Kruskal’s algorithm running in real-time.

How it Works

I built a CircuitVisualiser class that hooks into the main simulation loop. Every time my Union-Find data structure merges two sets, it fires an event to the visualiser.

To make it really pop, I implemented a dynamic colouring system using the cm.hot colormap:

Unconnected Boxes start as Dodger Blue.
Connected Boxes transition through a heat map.
Crucially, I made the colours persistent. Once a box joins the network, it locks in its colour based on when it connected.
- Red: Early connections (Old).
- Orange/Yellow: Mid-game connections.
- White: The final connections that bridge the gap (New).

This creates a visual timeline of the algorithm’s progress. You can literally see the “heat” of the activity moving through the cloud of points. Very satisfying!

‹