Advent of Code 2021 - Day 12, in Kotlin - Passage Pathing • Todd Ginsberg

In my day job I almost never write recursive functions. The work just doesn’t lend itself to them all that often. But I like them, and for problems like traversing a set of caves it seems (to me) like a natural way to solve the puzzle. I had fun with this puzzle, it was a nice way to calm back down and focus after a thrilling race to end the 2021 F1 season (Congratulations Max, I know you’re probably going to be starting on Advent of Code in the off season)!

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

Problem Input

Initially I struggled with how to represent our cave. I went down the path of defining a Cave class which had neighbors and some state on whether it had been visited or not. But I found the parsing clunky and ultimately didn’t really need the state because our path through the cave carried all the state we ended up needing. Therefore, let’s represent our cave as a Map<String, List<String>> where the key is the name of a cave and the value is the list of caves it connects to (its neighbors).

class Day12(input: List<String>) {

    private val caves: Map<String, List<String>> = parseInput(input)

    private fun parseInput(input: List<String>): Map<String, List<String>> =
        input
            .map { it.split("-") }
            .flatMap {
                listOf(
                    it.first() to it.last(),
                    it.last() to it.first()
                )
            }
            .groupBy({ it.first }, { it.second })
}

In order to properly map the cave, we need to know all the neighbors. Since our input only shows one side of a relationship “A connects to B”, we need to insert the other (“B connects to A”) because paths between two caves can be traversed in two directions. To do that, we’ll flatMap our List<List<String>> into a List<Pair<String,String>> where each Pair represents a valid combination of neighbors (A to B, and B to A). We’ll use the groupBy function which allows us to pass lambdas for both the key mapping and value mapping we need to do to get the Pair<String,String> down to a String in each case.

⭐ Day 12, Part 1

The puzzle text can be found here.

The real work in part one will be to generate unique paths through the cave, which we will do with a recursive function called traverse. Our traverse function will take a function as an argument called allowedToVisit. Because the logic for this takes place in part two, this allows us to reuse traverse for both parts, substituting this logic. The allowedToVisit function will receive two arguments: the name of the cave we want to visit and the path taken so far. Our traverse function also takes in the path taken so far (which we default to “start”).

If the traversal function detects that it has reached the “end” cave because it is the last cave in the path, we have reached the goal and can stop traversing. To do that, we’ll return the path wrapped in a list so the types line up (List<List<String>>). If we haven’t reached the goal, we want to take the path we have so far and try every valid neighbor of the step in the path. To do this, we get the neighbors of the last element in the path and filter to include anything we’re allowed to visit. This is done by calling our allowedToVisit function. To visit the neighbors we’re allowed to visit we’ll flatMap so the types line up and recursively call traverse with our allowedToVisit function and the path with the neighbor added to the end.

// In Day12

private fun traverse(
    allowedToVisit: (String, List<String>) -> Boolean,
    path: List<String> = listOf("start")
): List<List<String>> =
    if (path.last() == "end") listOf(path)
    else caves.getValue(path.last())
        .filter { allowedToVisit(it, path) }
        .flatMap {
            traverse(allowedToVisit, path + it)
        }

Note: We could have written traverse as an extension function on List<String> instead of explicitly passing the path in, but I didn’t like how it looked. If you find that more natural, go for it!

The rules for part one state that we can visit a neighboring cave as many times as we like if it has an uppercase name, otherwise we can only visit it once. We’ll write a function to represent that rule and call it part1VisitRule. We’ll check that the name is uppercase or the neighbor we want to visit is not on the path.

// In Day12

private fun part1VisitRule(name: String, path: List<String>): Boolean =
    name.isUpperCase() || name !in path

Although Kotlin has a function to test if a Char is uppercase or lowercase, it does not have the same function on String. Thankfully we can define our own extension function that tests if all of the characters are uppercase.

// In Day12

private fun String.isUpperCase(): Boolean = 
    all { it.isUpperCase() }

Now we can solve part one by passing a reference to our part1VisitRule function to traverse.

// In Day12

fun solvePart1(): Int =
    traverse(::part1VisitRule).size

Star earned! Onward!

⭐ Day 12, Part 2

The puzzle text can be found here.

Because we wrote part one the way we did, passing in an “am I allowed to visit this neighbor” function, we don’t have much to do for part two except implement that function.

// In Day12

private fun part2VisitRule(name: String, path: List<String>): Boolean =
    when {
        name.isUpperCase() -> true
        name == "start" -> false
        name !in path -> true
        else -> path
            .filterNot { it.isUpperCase() }
            .groupBy { it }
            .none { it.value.size == 2 }
    }

The visitation rules are quite a bit more complicated for part two. First, we’ll check if this is an uppercase neighbor and if it is, we’re allowed to visit it. We’ll take a bit of a shortcut with “start”, assuming we always start a traversal from the start, so we disallow it as a neighbor. The next simple case is if we haven’t visited the neighbor yet. Finally, we determine if there have been any lowercase nodes that have been visited twice. If so, we can visit it, otherwise we’ve already been through that part of the cave and can’t revisit it.

And now we can solve part two by passing traverse a reference to ourpart2VisitRule function:

// In Day12

fun solvePart2(): Int =
    traverse(::part2VisitRule).size

Star earned!

⭐ Day 12, Part 1

⭐ Day 12, Part 2

Further Reading