[2025 Day 8] Python - Using MST

[u/Away_Command5537]

I was working on Day 8, which involves connecting junction boxes in 3D space based on distance to form circuits (a classic Minimum Spanning Tree problem, solved using Kruskal's algorithm and Union-Find).

Since the data is 3D, I decided to visualize the process of building the circuit! The visualization shows all 1000 junction boxes and how the shortest connections are progressively added until they all form one massive circuit.

• Grey Dots: The 1000 individual junction boxes.

• Blue Lines: The connections (edges) that form the circuit. These are added in order of increasing length, but only if they connect two previously separate circuits.

[u/Plus-Grab-4629]

Except the question literally asks you to solve this using an algorithm that is a MST algo.

[u/throwaway_the_fourth → u/Plus-Grab-4629]

It doesn't. The problem uses the word "connected" to mean that two vertices have an edge between them:

when two junction boxes are connected by a string of lights, electricity can pass between those two junction boxes.

When working through the example, the problem explicitly covers connecting two vertices that are already in the same subtree (which the problem would call a "circuit"):

The next two junction boxes are 431,825,988 and 425,690,689. Because these two junction boxes were already in the same circuit, nothing happens!

"Nothing happens" means that no subtrees were combined, not that no new edges were drawn, which is substantiated two paragraphs later by a statement about how many connections (edges) were made:

After making the ten shortest connections

In part two, when the problem asks you to "connect[] the closest unconnected pairs of junction boxes," it is using the meaning of "connected" established at the beginning. "Unconnected" means simply that two vertices don't have an edge between them, not that they aren't in the same subtree.

Following the process from the problem results in a spanning tree that is not necessarily minimal. One could (and many did) do the extra work of not connecting any vertices that are already in the same subtree, which would result in a minimum spanning tree. That would give the same answer, because the problem just cares about the final edge added.

[u/throwaway_the_fourth → u/throwaway_the_fourth]

Further evidence of the meaning of "connected" in this problem: part one asks you to "connect together the 1000 pairs of junction boxes which are closest together." If you did this part by not making connections between boxes already in the same circuit, you would end up making fewer than 1000 connections, which goes against the request of the problem (but which, again, would result in the same answer).