Advent of Code 2023 - Day 8, in Kotlin - Haunted Wasteland • Todd Ginsberg

It wouldn’t be Advent of Code without a puzzle whose runtime is so long you have to find a way to detect a cycle and do some math!

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

Puzzle Input

Today, list most days this year, we can take our puzzle input as a List<String>. We don’t need to define it as a property because we’ll parse what we need from it during initialization.

class Day08(input: List<String>) {

    private val instructions: String = input.first()
    private val routeMap: Map<String, Pair<String, String>> = parseRouteMap(input)

    private fun parseRouteMap(input: List<String>): Map<String, Pair<String, String>> =
        input
            .drop(2)
            .associate {
                it.substring(0..2) to (it.substring(7..9) to it.substring(12..14))
            }
}

We will store the instructions (the turns to make) as a simple String, which is the first row of input. Since we can index into String like it is an array, this will work fine for our purposes.

We will store the turn directions, the routeMap as Map<String,Pair<String,String>. I know that’s a lot so let’s break it down. The key, a String is the current route (AAA in the example). The value of the map is a Pair<String, String> where the first element of the pair represents where to go when turning left from the key (so, BBB in the example) and second represents where to go when turning right from the key (CCC in the example).

The parseRouteMap function depends on substring(Range) as the route names are all 3 characters long and spaced regularly. We could probably have written a nice simple regular expression to pick these out, but this works and I think is clear.

⭐ Day 8, Part 1

The puzzle text can be found here.

In order to solve part 1 we need to write a function that goes through the map of routes from AAA to ZZZ and counts the steps.

One note: In order to avoid having to refactor this function in the description for part 2, we’ll compromise and write it with part 2 in mind. I’m not spoiling too much to say that the start can be something other than AAA, so we’ll let the caller define what that is. And it turns out that any time we stop following a route, that route ends with Z, so we’ll make that change as well. Originally I had passed in a function to determine the end state but when I figured out that there is one shared condition between both parts 1 and 2, I made a compromise and hard coded it to look for route names that end with Z. I am open to the idea that this stroke of luck is localized entirely to my input, but I doubt it (I think all of the inputs probably have this property).

Let’s check out our countSteps function.

// In Day08

private fun countSteps(start: String): Int {
    var steps = 0
    var current = start
    while (!current.endsWith("Z")) {
        current = routeMap.getValue(current).let { route ->
            val instruction = instructions[steps++ % instructions.length]
            if (instruction == 'L') route.first
            else route.second
        }
    }
    return steps
}

As I mentioned, we want the caller to be able to tell us where to start our traversal, so we’ll take in the start point as an argument. We will set up two variables: steps to count how many steps we’ve taken, and current to indicate where we are on the route, which we initialize to start. Next, we loop until we are not at the end of a route, which we determine by looking to see if the current location ends with Z. If it does not, we need to calculate the next value for current.

To calculate the next value for current, we get the Pair<String,String> representing the next steps to take and call let on it which lets us do the rest of our calculation as a single functional chain. First, we look through our instructions and find what to do next. We can pretend instructions is infinitely long by taking the modulus of the current number of steps and the total number of instructions. That way we won’t run out of instructions and we won’t have to do any bounds checking ourselves. Note the ++ on the end of steps which increments after its value is used in the modulus calculation.

Once we have the instruction, we determine if we are going left or right and pick either the first or second value out of the routes pair, setting this value to current. At this point, we check to make sure we aren’t at the end and loop again if not. If we’ve reached the end, we return the number of steps taken.

All that’s left to do is run countSteps and tell it we are starting at location AAA.

// In Day08

fun solvePart1(): Int =
    countSteps("AAA")

Star earned! Onward!

⭐ Day 8, Part 2

The puzzle text can be found here.

The instructions state: “Repeat this process until all of the nodes you’re currently on end with Z”.

Which means, to me, to keep running these simultaneously until every one of them is at the end. A route doesn’t really end unless they ALL do. At the same time. So if we have three routes and two of them are at the end, the process doesn’t end because the third route isn’t at its end.

In order to illustrate our approach to part 2, let’s look at this hastily assembled text diagram. It represents three starting points through the routes, 22A, 33A, and 44A. In the diagram, we show the step counts and a + whenever we’ve looped (reached their natural end).

22A repeats every 2 steps, 33A repeats every 3 steps, and 44A repeats every 4 steps.


Route 22A = -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Route 33A = --+--+--+--+--+--+--+--+--+--+--+--+--+-
Route 44A = ---+---+---+---+---+---+---+---+---+---+
    Steps = 1234567891111111111222222222233333333334
                     0123456789012345678901234567890

When we plot out our routes, you can see that 22A and 33A line up with each other every 6th step. This means they both end at this point and repeat their cycles. 6, as it happens is the Least Common Multiple (LCM) of 2 and 3. Extending this further, if we look at when all three of these routes line up, the answer is 12, or the LCM of 2, 3, and 4.

Our strategy is going to be to run each route that ends with an A until it finds a Z and count the steps for each. Finding the LCM of all the steps from all the routes should give us our answer.

The formula to find the LCM of some numbers a and b is (a*b) / gcd(a, b) where GCD is the Greatest Common Divisor. It seems like we could probably reuse both the LCD and GCD functions again, so let’s define them in a file called Extensions.kt and make them extensions on Long. We could define them as lcd(a: Long, b: Long) as well, but I think the extensions look nice.

// In Extensions.kt

fun Long.lcm(other: Long): Long =
    (this * other) / this.gcd(other)

And gcd…

// In Extensions.kt

tailrec fun Long.gcd(other: Long): Long =
    if(other == 0L) this
    else other.gcd(this % other)

It turns out that gcd is a recursive function, meaning it is a function that calls itself until some base condition is met. We define this as tailrec which is a very minor optimization that we could easily have skipped. Basically, if you write a recursive function and the very last thing you do is make the recursive call (as opposed to making the recursive call and doing some math with the result for example), you can mark it as tailrec and Kotlin will unwind this into a loop. It is helpful when you potentially have a very deep recursion on your hands so you don’t run out of stack memory. In our case, we probably can’t pass in any values for Long that would cause this issue, but I figured I’d describe tailrec anyway.

Now that we have lcm and gcd written, we can write our solution to part 2:

// In Day08

fun solvePart2(): Long =
    routeMap.keys
        .filter { it.endsWith("A") }
        .map { countSteps(it).toLong() }
        .reduce { prev, next -> prev.lcm(next) }

We need to find all of the routes that end with A, so we’ll filter the keys of our routeMap to get them. Then, for each of those, we will call countSteps with the A-ending route name and convert the resulting Int into a Long (because our numbers are about to get very big). At this point we have a List<Long> where each element represents the number of steps each A-to-Z route takes. If we get the LCM of all these numbers, it will be our answer. We can do this with reduce, which feeds us each element from the List<Long> which we can use to call our newly written lcm extension.

Star earned! See you tomorrow!

⭐ Day 8, Part 1

⭐ Day 8, Part 2

Further Reading