# Advent of Code 2021 - Day 12, in Kotlin - Passage Pathing

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 12: 'Passage Pathing'

Posted on

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 our`part2VisitRule` function:

``````// In Day12

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

Star earned!