Advent of Code 2022 - Day 5, in Kotlin - Supply Stacks • Todd Ginsberg

The bulk of the work to solve today’s puzzle is in the parser section. If you wanted to save a lot of time and code, you could probably hard code the stacks of crates, but where’s the fun in that?

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

In years past, when writing code in Part Two where we had to make minor refactorings to the code we wrote in Part One, I’d walk us through the refactoring. Personally, I find that a bit hard to explain and it can get a bit confusing. This year, I’m just going to tell you in Part One why we are making a seemingly odd choice for a data structure or parameter and let you know that something about this changes in Part Two, but not exactly what. That way, if you don’t want spoilers you won’t know precisely what changes in Part Two, but when we get there we’ll have an easier time of it.

This applies to today’s puzzle solution.

Puzzle Input

At a high level we will take today’s puzzle input as a List<String> and have two functions use it to parse the stacks and instructions.

class Day05(input: List<String>) {

    private val stacks: List<MutableList<Char>> = createStacks(input)
    private val instructions: List<Instruction> = parseInstructions(input)
}

Since our input today is quite complicated and is broken up into two sections, we’ll break our discussion into two sections as well.

Puzzle Input: Stacks

As usual, let’s decide how we want to represent the stacks of crates. For each individual stack of crates, we’ll go with a MutableList<Char> and the “top” of the stack will be the first element in the list. I find this easier to reason about despite possibly paying a small penalty for constantly adding and removing items from the list at the head of the list. We could reverse the lists and make the top of the stack the last element in each list, but I think this confusing. We will store each of our individual MutableList<Char> stacks in a List, ending up with a List<MutableList<Char>>.

When I first solved the puzzle I had a completely different way of parsing out the stacks of crates. I went through row by row and built the lists up one element at a time left to right. That worked fine, but then I thought about it. What if we did things vertically? We know by looking at the input that each of the stacks is in a predictable row (column index 1, 4, 9, and so on). Could we figure out how many possible stacks there are and then pick out crates from each index of the input? It might be a tiny bit less efficient, but it should be easier to understand (and it is less code).

// In Day05

private fun createStacks(input: List<String>): List<MutableList<Char>> {
    val stackRows = input.takeWhile { it.contains('[') }
    return (1..stackRows.last().length step 4).map { index ->
        stackRows
            .mapNotNull { it.getOrNull(index) }
            .filter { it.isUpperCase() }
            .toMutableList()
    }
}

The first thing we need to do is pick out the stackRows from the input. These are rows at the top of the file that represent the stacks. Since each row will have at least one open bracket ([), we’ll look through the input using takeWhile. This will give us just the rows we care about.

Once we have that, we can set up a range from 1 to the index of the longest string in stackRows. This will invariably be the “bottom” of the stacks so we can look at the last() of the stackRows and take its length. Our range can start at 1, the index of the first stack (looking left to right) and can step by 4 (how far apart the stacks are). So in the end, our range will represent the indexes that contain stacks.

From there we can map the index to its vertical slice through all of the stackRows. To do this, we need to get the element at the index for each row. In some cases there might not be anything there so we’ll use mapNotNull to account for the fact that our code to get the value at an index safely (meaning - don’t throw an IndexOutOfBoundsException, just return null) will return nulls in some cases. This is done by calling getOrNull(index) on each row of the input, rather than get(index) and risking an exception.

Because some of the shorter stacks will have empty strings where letters would be in taller stacks, we’ll filter those out by checking if each character is an uppercase letter via isUpperCase.

At this point we have a List<Char> but since we want a MutableList<Char>, we’ll call toMutableList() on it. This, combined with the map off of our range, will give us a List<MutableList<Char>> representing the stacks of crates.

Puzzle Input: Instructions

We have a couple of options here on how to store the instructions. We could use Kotlin’s Triple class and go with a Triple<Int,Int,Int>, or we could define our own data class which more or less does the same thing. I went with a data class called Instruction because it just seemed cleaner to me.

// In Day05

private data class Instruction(val amount: Int, val source: Int, val target: Int)

And to parse the part of the input that represents instructions, we’ll look at the input and dropWhile the line does not start with “move”. This should advance us past all of the previous stack-related input rows and leave us with only the movement-related rows. For each movement row we’ll map the row and split it on a space. This will turn "move 1 from 2 to 3" to ["move", "1", "from", "2", "to", "3"] and from there we can pick out the elements we want (1, 3, and 5). We’ll nest a let inside our map so we can keep this as one functional expression, and inside there create a new Instruction after converting the parts we care about to integers via toInt().

// In Day05

private fun parseInstructions(input: List<String>): List<Instruction> =
    input
        .dropWhile { !it.startsWith("move") }
        .map { row ->
            row.split(" ").let { parts ->
                Instruction(parts[1].toInt(), parts[3].toInt() - 1, parts[5].toInt() - 1)
            }
        }

Remember that the Ints we get in the input are 1=one-based columns. Since we are storing the stacks in a zero-based List we’ll need to subtract 1 from both the source and destination.

⭐ Day 5, Part 1

The puzzle text can be found here.

Now that we’ve parsed our data into a useful format, we can start solving the problem. Let’s get reporting the actual solution out of the way and write an extension function to get the topmost crate from each stack and join them together into a String:

// In Day05

private fun Iterable<Iterable<Char>>.tops(): String =
    map { it.first() }.joinToString("")

This is written as an extension function on Iterable<Iterable<Char>> rather than the more exact List<MutableList<Char>> because during my attempt to solve the puzzle I changed data structures a few times and got tired of changing the signature of this function. At any rate, we map the first element of each stack and use joinToString to turn the List<Char> into a String without delimiters.

Next, we can write a function to perform all of the instructions. Here’s the deal. I know something about Part Two that you might not know yet. Rather than having to explain a potentially confusing refactor later in Part Two, let’s just write it the way Part Two wants it now. It might not make sense but when you read Part Two’s instructions it will.

Since the performInstructions function works via side effects (meaning all the work of the loop is done in-place and not recreated during each iteration of the loop) we can use forEach to look at each of our instructions. For each of the instructions, we destructure our Instruction data class into its three components - amount, source, and destination. This makes the code a bit simpler. Inside the loop we’ll set aside the crates toBeMove by looking up the source stack, and calling take on it to retrieve a List<Char> that is amount elements long. These are the crates we’ll move, but only a copy. The symbols representing those crates are still present on the source. To account for this we’ll need to remove them. Unfortunately, Kotlin’s MutableList doesn’t have a built-in function to remove an arbitrary number of elements from the front of the list. It only has a way to remove a single element. Rather than write one ourselves, we’ll use repeat(amount) to execute a removeFirst() on the source stack the appropriate number of times. This could be made more efficient, but since we’re dealing with tiny stacks, and we run this code once for a puzzle, I don’t think it is ultimately worth the trouble.

After we’ve figured out which crates we want to move from the source, we put them on the destination stack via addAll, specifying 0 as where we’d like to put them. At this point, we need to figure out if we want the toBeMoved crates to be reversed or not. So we’ll evaluate our reverse argument here and either reverse the toBeMoved list or not, before adding them to the destination. This is one of those cases where having if be an expression (rather than a statement) is very handy.

// In Day05

private fun performInstructions(reverse: Boolean) {
    instructions.forEach { (amount, source, destination) ->
        val toBeMoved = stacks[source].take(amount)
        repeat(amount) { stacks[source].removeFirst() }
        stacks[destination].addAll(0, if (reverse) toBeMoved.reversed() else toBeMoved)
    }
}

Calling the two functions we just wrote (specifying that we do want the containers reversed) will solve Part One.

// In Day05

fun solvePart1(): String {
    performInstructions(true)
    return stacks.tops()
}

Star earned! Onward!

⭐ Day 5, Part 2

The puzzle text can be found here.

Because we wrote our performInstructions function in a way that allowed us to reverse or not reverse the crates the crane picks off, we’re mostly done. We can use the same code we wrote to solve Part One, but specify that we do not want to reverse the crates as we pull them off the stack.

// In Day05

fun solvePart2(): String {
    performInstructions(false)
    return stacks.tops()
}

Star earned! See you tomorrow.

⭐ Day 5, Part 1

⭐ Day 5, Part 2

Further Reading