Advent of Code 2025 - Day 8, in Kotlin - Playground • Todd Ginsberg

Today we’ll depend on a data structure called a Disjoint Set . We will use this to store the groups of points in a more efficient manner than maintaining a set of sets ourselves.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

Let’s write our DisjointSet class before we parse our data. It’s a lot of code, I’ll go over it below.


class DisjointSet<T> {
    private val parents: MutableMap<T, T> = mutableMapOf()
    private val counts: MutableMap<T, Int> = mutableMapOf()

    fun setSizes(): List<Int> = counts.values.toList()

    fun countSets(): Int = counts.size

    fun addAll(elements: Collection<T>) =
        elements.forEach { add(it) }

    fun add(element: T) {
        if(element !in parents) {
            parents[element] = element
            counts[element] = 1
        }
    }

    // Note: Assumes element is always present
    fun find(element: T): T =
        if(parents.getValue(element) == element) element
        else find(parents.getValue(element)).also {
            parents[element] = it
        }

    // Note: Assumes left and right are always present
    fun union(left: T, right: T) {
        val leftRoot = find(left)
        val rightRoot = find(right)

        if(leftRoot != rightRoot) {
            if(counts.getValue(leftRoot) < counts.getValue(rightRoot)) {
                parents[rightRoot] = leftRoot
                counts[leftRoot] = counts.getValue(leftRoot) + counts.getValue(rightRoot)
                counts.remove(rightRoot)
            } else {
                parents[leftRoot] = rightRoot
                counts[rightRoot] = counts.getValue(rightRoot) + counts.getValue(leftRoot)
                counts.remove(leftRoot)
            }
        }
    }
}

The main thing to note in this class is the parents map. For any given element, what is its parent element? When we add and element, it is its own parent. So if we add three separate elements and don’t do anything else, we’ll have 3 subsets of 1 element each. The counts map keeps track of the size of each subset.

When we find an element, we do so recursively, stopping when the target element is found in the parents map. Otherwise, we recurse and find the element’s parent instead. We also optimize this structure as we go.

The main and most interesting part of the Disjoint Set is the union function, which merges two subsets together. Basically, we find the root element (parent-most? is that a word?) for each element to union, figure out which one is smaller, and union it into the larger side. We also remove the counts for the subset we just merged, to keep that data structure tidier and easier to follow.

Another class we’ll need is a 3D version of our point class…


data class Point3D(val x: Int, val y: Int, val z: Int) {

    fun straightLineDistanceTo(other: Point3D): Double =
        sqrt(
            (other.x - x).toDouble().pow(2) +
            (other.y - y).toDouble().pow(2) +
            (other.z - z).toDouble().pow(2)
        )

    companion object {
        fun of(input: String): Point3D =
            input.split(",").let {
                Point3D(it[0].toInt(), it[1].toInt(), it[2].toInt())
            }
    }
}

It’s not as fully-featured as our Point2D class, as it only has what we need to solve today’s puzzle. Most notably, the straightLineDistanceTo function. It also has a class-level of function which does the parsing.

We’ll also need a data class to store each of the pairs of Point3D objects, and the distance between them. It implements Comparable so we can order the full list of them from closest to farthest.

// Day08

private data class PointPair(val a: Point3D, val b: Point3D) : Comparable<PointPair> {
    val distance: Double = a.straightLineDistanceTo(b)

    override fun compareTo(other: PointPair): Int =
        this.distance.compareTo(other.distance)
}

Now, after all that, we have enough to parse our input. The input itself is mapped directly to a List<Point3D>. Once we’ve parsed them, we add them all to a DisjointSet.

Next, we pair the points up, create a PointPair out of each pair of them, and add them all to a PriorityQueue. This takes the natural order of the PointPair as the ordering method, so if we poll() the closest queue, we will get the pair of points with the closest distance, in increasing order.


class Day08(input: List<String>) {

    private val points: List<Point3D> = input.map { Point3D.of(it) }

    private val disjointSet = DisjointSet<Point3D>().apply {
        addAll(points)
    }

    private val closest: PriorityQueue<PointPair> = PriorityQueue<PointPair>().apply {
        points.forEachIndexed { index, a ->
            points.drop(index + 1).forEach { b ->
                add(PointPair(a, b))
            }
        }
    }

}

After a much, much, larger than usual “Puzzle Input” section, we can go on to solve part 1!

⭐ Day 8, Part 1

The puzzle text can be found here.

Because the DisjointSet has everything we need, we can use it as-is to solve part 1. The example and the actual puzzle input require different numbers of connections, so we’ll take that value in, defaulting to 1,000.

We poll the closest PriorityQueue once for each of the connections we want to make. This gives us a PointPair which we can destructure into left and rigth parts. We use our disjointSet to union these sets together. Basically, the subset of all points that contains left and the subset of all points that contain right are now the same set.

// Day08

fun solvePart1(connections: Int = 1_000): Int {
    repeat(connections) {
        closest.poll().let { (left, right) ->
            disjointSet.union(left, right)
        }
    }

    return disjointSet
        .setSizes()
        .sortedDescending()
        .take(3)
        .reduce { a, b -> a * b }
}

Once the disjointSet has been unioned connections times, we can get the sized of the individual sets, order them by size descending, take 3 of them, and then use reduce to multiply them all together for our answer.

Star earned! Onward!

⭐ Day 8, Part 2

The puzzle text can be found here.

Once again, disjointSet has us covered. Our strategy here will be to keep unioning subsets together until we reduce all of the points to a single set. The very last pair of points is the one we are after (the farthest closest point, as it were).

To get to this, we’ll generate a sequence by polling the closest queue, which will return PointPair objects in increasing distance order. We union these pairs together and stop the sequence when we have a single set remaining. At that point the generateSequence function will return that last value, which we can use to answer part 2.

// Day08

fun solvePart2(): Long =
    generateSequence(closest.poll()) { (left, right) ->

        disjointSet.union(left, right)

        closest.poll().takeIf { disjointSet.countSets() > 1 }

    }.last()
     .let { (left, right) -> 
    	left.x.toLong() * right.x.toLong() 
    }

Note that if we keep the x values as Int, they’ll overflow (they did for me, at least), so we convert them to Long to get the actual answer.

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 8, Part 1

⭐ Day 8, Part 2

Further Reading