Advent of Code 2025 - Day 11, in Kotlin - Reactor • Todd Ginsberg

Today we’ll write our first Depth-First search algorithm of this year’s Advent of Code! I usually end up writing this at least once per year, and it’s a good algorithm to remember for job interviews and puzzle code.

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

Puzzle Input

Our input looks good as is, so let’s add each line to a Map<String, List<String>> where the key is the parent element and the value is the list of all child elements. We can do this directly with associate and some clever use of subStringBefore, substringAfter, and split. No separate function needed, I think this is simple enough to inline today.


class Day11(input: List<String>) {

    private val devices: Map<String, List<String>> = input.associate {
        it.substringBefore(":") to it.substringAfter(" ").split(" ")
    }

}

Associate is a good function to know, basically “Take these pairs and turn them into a Map”. Very handy!

⭐ Day 11, Part 1

The puzzle text can be found here.

Because the data we’re given forms a Directed Acyclic Graph (meaning: a graph with no loops), we can use a Depth-First Search to calculate our answer.

// In Day11

private fun dfs(
    source: String,
    target: String,
    memory: MutableMap<String, Long> = mutableMapOf()
): Long =
    if (source == target) 1L
    else memory.getOrPut(source) {
        devices[source]?.sumOf { next ->
            dfs(next, target, memory)
        } ?: 0
    }

Our dfs function takes a source (where we’re coming from), a target (where we want to end up), and a memory since we’ll visit the same places multiple times and we save a LOT of time if we store counts as we go.

The first step is to check and see if the source and target are the same. That tells us there is 1 way to get from source to target, so we return that. Otherwise, we check the memory for how many ways there were to get from source to target. This is where it gets a bit complicated. If memory does contain this value, we return it. If memory does not even know about source, it returns null from getOrPut and we treat this as 0 ways to get from source to target.

The last and most interesting case is if source has links to other systems, maybe one or more of them has a way to get to target. So we get the sumOf all the ways they could get to the target by recursively calling dfs again, with each of the next systems.

Eventually, this function will return with the number of valid ways to get from source to target.

All that’s left to do for part 1 is to call this function!

// In Day11

fun solvePart1(): Long =
    dfs("you", "out")

Star earned! Onward!

⭐ Day 11, Part 2

The puzzle text can be found here.

If we think about it, the puzzle is asking us to get from svr to out via both dac and fft. Since there are no loops in the puzzle data, that means we really want the following:

The number of ways to follow this path: svr -> dac -> fft -> out

plus

The number of ways to follow this path: svr -> fft -> dac -> out

For each path, we can use dfs to count the number of ways between each of the nodes I’ve highlighted in the path and multiply them together. For example, if there are 10 ways to get from svr to dac but no ways to get from dac to fft, then there are ultimately going to be no ways to get from svr to out.

Add both of these together and you’ll have the correct number of ways to get from svr to out via dac and fft!

// In Day11

fun solvePart2(): Long =
    (dfs("svr", "dac") * dfs("dac", "fft") * dfs("fft", "out")) +
    (dfs("svr", "fft") * dfs("fft", "dac") * dfs("dac", "out"))

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading