#minimumspanningtree — Public Fediverse posts

There are two kinds of people today: people that know Kruskal's algorithm and people who don't.

If you do, it's pretty simple. Calculate all the distances (you don't even need sqrt since you just need to compare them), sort the pairs by distance, and add them one-by-one to the working set. I used union find to keep track of the connected components as I added edges. Once you've added 1000 edges, get the three biggest connected components and multiply their sizes together for Part 1. Keep adding until the number of non-connected components reaches 1, and then multiply the X coordinates of the last edge you added for Part 2.

If you don't, you probably eventually did something similar but it was a lot more painful. 🙃

Not my fastest solution, but still just over 500ms on my laptop, and the complexity of reducing it wasn't worth it.

https://github.com/biesnecker/aoc-anyhow/blob/main/202508.py

#adventofcode #adventofcode2025 #python #minimumspanningtree #kruskalsalgorithm