Skip to content

Advent of Code 2025 Day 8: Playground

"""Advent of Code 2025: Day 8 - Playground

The key elements of this solution are:
1. Form the combinations of all pairs of junction boxes, with their distance
2. Use a set to represent a circuit, and store in a list

Since part 2 is a continuation of part 1, I use a generator function to yield the
answer for part 1, and then continue processing to yield the answer for part 2. The
condition for yielding part 1 is when 1,000 pairs of boxes have been connected. The
condition for yielding part 2 is when there is a single circuit, and there are no
remaining boxes to process.

There are four main cases to consider when connecting two junction boxes:
1. Both boxes already exist in separate circuits, merge the two circuits
2. Only box1 is in a circuit, add box2 to that circuit
3. Only box2 is in a circuit, add box1 to that circuit
4. Neither box is in a circuit, add the pair as a new circuit

NOTES: 1. I decided against using a heap, because a single sort for part 1 is clearer.
       2. We don't need the actual distance to rank, so we could skip the sqrt for
          extra speed, but why ruin a perfectly good distance function? :)"""

from advent import parse, ints, combinations, prod, dist


def solve_both_parts():
    remaining_boxes = set(parse(8, ints))
    closest_pairs = sorted(combinations(remaining_boxes, 2), key=lambda pair: dist(*pair))
    circuits = [{box for box in closest_pairs[0]}]

    for n, (box1, box2) in enumerate(closest_pairs, 1):
        remaining_boxes.discard(box1)
        remaining_boxes.discard(box2)
        circuit1 = next((c for c in circuits if box1 in c), None)
        circuit2 = next((c for c in circuits if box2 in c), None)

        if circuit1 and circuit2:
            if circuit1 == circuit2:
                pass  # boxes already in same circuit
            else:
                circuits.remove(circuit1)
                circuits.remove(circuit2)
                circuits.append(circuit1 | circuit2)
        elif circuit1:
            circuit1.add(box2)
        elif circuit2:
            circuit2.add(box1)
        else:
            circuits.append(set((box1, box2)))

        if n == 1000:
            yield prod(sorted([len(c) for c in circuits], reverse=True)[:3])
        elif not remaining_boxes and len(circuits) == 1:
            yield box1[0] * box2[0]
            return


assert list(solve_both_parts()) == [103488, 8759985540]

Day 8

Input Parsing

We're given a list of junction box 3D coordinates. We'll need two things - a set of boxes (to know when we've connected all of them at least once, for part 2), and a list of all combinations of 2 boxes in order of the distance between them.:

remaining_boxes = set(parse(8, ints))
closest_pairs = sorted(combinations(remaining_boxes, 2), key=lambda pair: dist(*pair))

Solution

We'll represent circuits with a set, and store them in a list, circuits. Since part 2 is just a continuation of part 1, we'll use a generator function to yield the two answers. We'll iterate over the junction box pairs in order of closeness, and do the following for each iteration:

  • Remove both boxes from the remaining_boxes set, to know when we've processed all of them
  • Retrieve the sets/circuits containing our two boxes, if they exist

  • Handle one of four possible cases:

    • If both boxes are already in different circuits, merge the two circuits into one
    • If only box1 is in a circuit, add box2 to that circuit
    • If only box2 is in a circuit, add box1 to that circuit
    • If neither box is in a circuit, add a new circuit of the two boxes

We have two termination conditions:

For part 1, we yield an answer when we've processed 1,000 pairs of boxes.

For part 2, we yield an answer (and exit the loop) when we've connected all the individual boxes at least once, and there is only a single circuit containing all of them.

Graph Version

I initially thought representing circuits with sets was the simplest idea, but after I created my solution, I noticed other people using a graph solution, so I was curious. It's definitely simpler than my original version!

"""Advent of Code 2025: Day 8 - Playground (using a graph)"""

from advent import parse, ints, combinations, dist, nx, prod


def solve_both_parts():
    boxes = set(parse(8, ints))
    G = nx.Graph()

    for n, (box1, box2) in enumerate(sorted(combinations(boxes, 2), key=lambda pair: dist(*pair)), 1):
        G.add_edge(box1, box2)
        boxes.discard(box1)
        boxes.discard(box2)

        if n == 1000:
            yield prod(sorted([len(s) for s in nx.connected_components(G)], reverse=True)[:3])
        elif not boxes and nx.is_connected(G):
            yield box1[0] * box2[0]
            return


assert list(solve_both_parts()) == [103488, 8759985540]

Disjoint Set / Union Find Version

I noticed a few people mentioning union find or disjoint set on reddit, so I looked into it. It does seem like a disjoint set solution matches today's problem the best. It's extremely similar to the graph version:

"""Advent of Code 2025: Day 8 - Playground (using union-find)"""

from advent import parse, ints, combinations, dist, nx, prod


def solve_both_parts():
    boxes = set(parse(8, ints))
    uf = nx.utils.UnionFind(boxes)

    for n, (box1, box2) in enumerate(sorted(combinations(boxes, 2), key=lambda pair: dist(*pair)), 1):
        uf.union(box1, box2)
        boxes.discard(box1)
        boxes.discard(box2)

        if n == 1000:
            yield prod(sorted([len(s) for s in uf.to_sets()], reverse=True)[:3])
        elif not boxes and len(list(uf.to_sets())) == 1:
            yield box1[0] * box2[0]
            return


assert list(solve_both_parts()) == [103488, 8759985540]

End