Advent of Code 2023 - Day 25, in Kotlin - Snowverload • Todd Ginsberg

We’ve finally made it to the end of Advent of Code 2023! Today’s puzzle is an interesting implementation of what’s called a “minimum cut” algorithm. I haven’t ever implemented one of these before and had to do some research on which one to use. I had never heard of any of them but I did remember something about minimum cuts, somehow.

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

Strategy

There are a set of algorithms that can find the “minimum cut” of a graph. Meaning, what is the least number of edges we have to remove (“cut”) from a graph in order to split the graph into two parts. One of these, Karger’s Algorithm is what we’ll implement today to solve the puzzle.

Basically, Karger’s Algorithm is:

Create a graph.
While the graph has more than two nodes in it, pick a random node.
Pick one of the nodes that the first random node connects to.
Merge them together by removing the random nodes from the graph and adding a single new node to replace them.
Store a count of how many nodes were removed from the graph and replaced with this single node. Note that as we remove nodes that are combinations of other nodes, this number will grow to be the cumulative number of nodes removed.
Add all of the connections to the previously removed nodes to the new node.

At the end, we should have a graph with two nodes. Cutting all of the edges between these two nodes is a minimum cut (maybe, see below) and the counts we’ve stored for all of the new nodes should give us the total number of each “side” of the graph we’re about to cut.

Puzzle Input

Unusually, we’ll parse our input into a mutable data structure - a MutableMap<String,MutableList<String>>. The String key is the name of a node, and the MutableList<String> value is the list of nodes that the key connects to. The map and list are both mutable because Karger’s Algorithm needs us to make changes to the graph, which this map represents.

Because we may need to run the algorithm more than once with different random starting points, we will keep our input as a property, and parse it all over again every time we need it. We do this instead of having to clone the map and all of the lists within it. It' just easier to parse it fresh every time.

class Day25(private val input: List<String>) {

    private fun parseInput(input: List<String>): MutableMap<String, MutableList<String>> {
        val map = mutableMapOf<String, MutableList<String>>()
        input.forEach { row ->
            val sourceName = row.substringBefore(":")
            val source = map.getOrPut(sourceName) { mutableListOf() }
            row.substringAfter(":").trim().split(" ").forEach { connection ->
                source += connection
                map.getOrPut(connection) { mutableListOf() }.add(sourceName)
            }
        }
        return map
    }
}

⭐ Day 25, Part 1

The puzzle text can be found here.

In order to implement Karger’s Algorithm, we need to be able to merge two nodes together. That means removing a node from the graph, and changing all of the references to that node from all other nodes to a new node.

// In Day25

private fun MutableMap<String, MutableList<String>>.mergeNodes(oldNode: String, newNode: String) {
    remove(oldNode)?.forEach { target ->
        getValue(target).replaceAll { if (it == oldNode) newNode else it }
    }
}

The mergeNodes function removes the oldNode from the graph, and then looks at every node the oldNode linked to and finds any instance of oldNode in their connection lists and replaces them with newNode. We have to implement this with replaceAll or we get concurrent modification errors (we can’t iterate and modify the list at the same time unless we have a datatype that supports it).

Next, we need a way to combine two nodes into a new node. We’ll implement combineValues to do this.

// In Day25

private fun MutableMap<String, MutableList<String>>.combineValues(a: String, b: String, newNode: String) {
    this[newNode] = (this.getValue(a).filter { it != b } + this.getValue(b).filter { it != a }).toMutableList()
}

The newNode links to all of the nodes both the old a and b nodes linked to, except the old a and b nodes themselves.

Now we have enough to implement Karger’s Algorithm.

// In Day25

fun solvePart1(): Int {
    while (true) {
        val graph = parseInput(input)
        val counts = graph.keys.associateWith { 1 }.toMutableMap()

        while (graph.size > 2) {
            val a = graph.keys.random()
            val b = graph.getValue(a).random()
            val newNode = "$a-$b"

            counts[newNode] = (counts.remove(a) ?: 0) + (counts.remove(b) ?: 0)
            graph.combineValues(a, b, newNode)
            graph.mergeNodes(a, newNode)
            graph.mergeNodes(b, newNode)
        }

        val (nodeA, nodeB) = graph.keys.toList()
        if (graph.getValue(nodeA).size == 3) {
            return counts.getValue(nodeA) * counts.getValue(nodeB)
        }
    }
}

Karger’s Algorithm is what is commonly referred to as a “Monte Carlo” or “Randomized” algorithm, which is basically Computer Scientist talk for “if it doesn’t produce the answer you like, keep trying with different random conditions”. So we’ll wrap our whole implementation in a while(true) in order to loop until we like the answer.

The first thing to do is get a freshly parsed graph at the original conditions, and create a corresponding map of counts for each node. Each node currently only represents a single node, but this will change as we combine nodes.

While the graph has more than two nodes left, we randomly select an a node and a b node from the a node’s neighbors. The combination of these is the newNode. We update the counts of the newNode by adding the counts of the a and b nodes together and removing them from the count map. You can leave them in but this ran measurably faster for me when I removed them.

Next, we combine the a and b nodes into a newNode, and then merge the nodes.

At the end, we should have two nodes with three connections between them. This is the minimum cut to make to divide the graph into two parts. Take the counts of the only two remaining nodes in the graph and multiply them together and that’s our answer.

If, on the other hand, at the end we don’t have exactly two nodes with three connections, start all over again. Maybe the random generator will be kind to us and it’ll work next time!

Star earned! See you next year! Thanks for reading my Advent of Code 2023 posts. If you learned something, I’d love to hear from you!

⭐ Day 25, Part 1

Further Reading