Advent of Code 2021 - Day 10, in Kotlin - Syntax Scoring • Todd Ginsberg

I liked today’s puzzle because it reminds me of a problem I used to ask in programming interviews, back when I used to ask people to code. This version is quite a bit more complicated than the version I asked so it was fun figuring out how I would solve it. Today, we’ll get to see a sealed class structure, and write a rudimentary parser.

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

Problem Input

Since our input is several Strings, we’ll import them as a List<String>, and keep them that way. While we’re here, let’s define a companion object to today’s solution class to hold some constant data.

class Day10(private val input: List<String>) {

    companion object {
        private val scoresPart1 = mapOf(')' to 3, ']' to 57, '}' to 1197, '>' to 25137)
        private val openToClose = mapOf('(' to ')', '[' to ']', '{' to '}', '<' to '>')
    }
}

We’ll define two maps. The first map is to help us with scoring part one and maps a closing symbol to its value. The second map will be used to pair up opening symbols to closing symbols.

⭐ Day 10, Part 1

The puzzle text can be found here.

The instructions indicate that there are two types of errors we could get, either “corrupted” or “incomplete”. This problem lends itself nicely to a sealed class structure. A sealed class (or interface) in Kotlin allows us to define a class and all of the possible subclasses (or implementations) that it is allowed to have. So let’s go ahead and create a sealed interface called ParseResult. We’ll make ParseResult an interface because it doesn’t define any state or behavior. Even though the puzzle instructions are clear that we won’t receive valid inputs, let’s define a Success object anyway because it gives us an opportunity to talk about objects. In this case, Success doesn’t have any state, it’s mere presence is the indicator of success. So we don’t have to define it as a class, we can (and should) define it as an object.

We’ll need an implementation of ParseResult to represent a corrupted input, so we’ll call that one Corrupted and have it take the Char that it failed on. The other error condition we can have is incomplete input, so we’ll define Incomplete to represent that, and have it define the pending symbols that we didn’t match (this will be used in part two).

// In Dev10

private sealed interface ParseResult
private object Success : ParseResult
private class Incomplete(val pending: List<Char>) : ParseResult
private class Corrupted(val actual: Char) : ParseResult {
    fun score(): Int =
        scoresPart1.getValue(actual)
}

Part one asks us to score the corrupted rows according to an algorithm provided. Let’s make sure our Corrupted class has a score function to do this work for us. Note that because this is the only place we use scoresPart1, we could have just written a when expression here and not defined that map at all. It boils down to your preference and what you think looks better.

Now that we have a way to describe the parsing results, let’s write a parseRow function to parse a single row of input represented as a String. To do this, we’ll define a stack and push opening symbols on to it as we find them. A stack is a data structure that writes to and reads from the same end. Picture a stack of plates. If you wanted a plate, you’d take the top one. If you ate something off of it, washed it, and returned it to the stack of plates, you’d place it on the top. Our stack works the same way. We’ll have a stack of opening characters, and whenever we run into a closing character we’ll see if they match up.

// In Day10

private fun parseRow(row: String): ParseResult {
    val stack = ArrayDeque<Char>()

    row.forEach { symbol ->
        when {
            symbol in openToClose -> stack.addLast(symbol)
            openToClose[stack.removeLast()] != symbol -> return Corrupted(symbol)
        }
    }

    return if (stack.isEmpty()) Success else Incomplete(stack.reversed())
}

One thing to note about this class is the fact that we assume anything that isn’t an opening character must be a closing character. The instructions are clear that this is the case, and our input follows that. But in the real world you’d have to account for this maybe not being the case (at which point we’d probably define another class for our ParseResult interface). Another thing to note is that we might underflow the stack - meaning, we may have more closing symbols than opening symbols. Again, in the real world we’d have to account for this, but not here where the puzzle inputs are guaranteed to conform to the requirements.

If at any point we find a closing symbol that does not match its opening symbol, we will return from our function with a Corrupted response. If we get to the end of the input we’ve either completed successfully or run out of input before we were done parsing a valid row. We’ll return either Success or Incomplete respectively in those cases.

Now we can solve part one:

// In Day10

fun solvePart1(): Int =
    input
        .map { parseRow(it) }
        .filterIsInstance<Corrupted>()
        .sumOf { it.score() }

One function I wasn’t aware of when I wrote this (but IntelliJ told me about!) is filterIsInstance<T>. I had written .filter { it is Corrupted } which does read nicely, but filterIsInstance<T> does some extra work for us by returning (in our case) a List<Corrupted> rather than a List<ParseResult> in the filter case. This saves us from having to do a manual cast later, which is really nice. Evidently this has been in the Kotlin standard library since its early days and I had no idea, so this was a nice find (I guess that shows you how infrequently I do this kind of casting?).

Once we’ve parsed our rows and picked out the Corrupted results, we can get the sumOf their scores by looking them up in scoresPart1.

Star earned! Onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

Thankfully we did all the work we’ll need to do for the actual parsing in part one, and that it doesn’t change in part two. One thing that does change is the scoring method, so we’ll add a scoresPart2 map to our companion object. Its responsibility is to map a closing symbol to its score value.

// In Day10 companion object

private val scoresPart2 = mapOf(')' to 1, ']' to 2, '}' to 3, '>' to 4)

Next, we need to score an incomplete row, which we’ll do by adding a score function to the Incomplete class. Note that this returns a Long because my input ended up overflowing an Int. I don’t think your input will overflow a Long, but if it does (you can tell this happened if you end up with negative numbers), you might have to use a BigInteger here, which is unbounded and cannot overflow. And again, we could have written this as a when expression and not defined scoresPart2, but I think this looks cleaner.

// In Day10

private class Incomplete(val pending: List<Char>) : ParseResult {
    fun score(): Long =
        pending
            .map { openToClose.getValue(it) }
            .fold(0L) { carry, symbol ->
                (carry * 5) + scoresPart2.getValue(symbol)
            }
}

In order to calculate a score, we’ll use a fold, seeding it with 0L. Update: Originally I had seeded the fold with 0 (an Int) instead of 0L (a Long) and this caused at least one overflow bug. Thanks to Dan Kertz for finding and debugging this!

We’re almost done but we need to get the middle value in a list of ordered scores. Kotlin doesn’t have this built in, but we can solve this with an extension function. Because this function isn’t all that complicated, and there’s a non-zero chance we’ll need to use it again this year, and the fact that we don’t have a good place to put extensions like this, let’s define an Extensions.kt file and put our midpoint extension in there.

// In Extensions.kt

fun <T> List<T>.midpoint(): T =
    this[lastIndex/2]

This function can operate on any List and gives us the middle point. Kotlin conveniently provides us with a lastIndex property (which is itself an extension on List<T>!) to get the highest index in the list.

We now have everything we need to solve part two (which again, returns Long rather than Int like in part one):

// In Day10

fun solvePart2(): Long =
    input
        .map { parseRow(it) }
        .filterIsInstance<Incomplete>()
        .map { it.score() }
        .sorted()
        .midpoint()

Star earned!

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading