Advent of Code 2018 - Day 5, in Kotlin • Todd Ginsberg

On Day 5, we’ll learn how handy fold() can be, and write an infix function for fun.

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

Problem Input

Our input is a single String, which we can use without altering, so we will load that up and pass it into our class.

class Day05(private val input: String) {

}

⭐ Day 5, Part 1

The puzzle text can be found here.

The first thing that strikes me is that we’re going to have to find a way to compare two characters to see if they are an upper/lower pair. To do this, let’s write an extension function on Char? to determine whether it and another Char represent a matched pair.

private infix fun Char?.matches(other: Char): Boolean =
    when {
        this == null -> false
        this.toUpperCase() != other.toUpperCase() -> false
        else -> this != other
    }

A couple of things might jump out initially. First, why do we actually have this on Char? and not Char? Keep reading to the actual solution and that will be explained. Next, why is this an infix function? The answer is it really doesn’t have to be, but I just wanted to illustrate what they are and how they work. By marking a function as infix, I can get rid of the dot and parens when calling it.

For example, each of these represents the same call:

char1.matches(char2)

char1 matches char2

It’s subjective, but there are situations when you want your function to look more like an operator.

Now that we have a way to see if characters match, let’s discuss our approach to the problem. Think about looking at our input string one character at a time. As we inspect a Char, we are only comparing it against one other Char, one we’ve already seen. If we could keep a list of characters we’ve seen, we can see if the next char matches the most recent char. If they match, remove them both. Otherwise, move the next char into the list of chars we’ve already seen. The reason we need a list is twofold. First, we need that to represent our new string, and we need to be able to keep looking back in history. Second, if we remove a char the second oldest now becomes the oldest, and we have to account for that. And our matches function must handle Char?, because there might not actually be a previous character yet.

Let’s put fold to use to write a function to reduce a String representing a polymer. We’ll write this as an extension function to make the code look cleaner when we call it:

private fun String.react(): String =
    this.fold(mutableListOf<Char>()) { done, char ->
        when {
            done.firstOrNull() matches char -> done.removeAt(0)
            else -> done.add(0, char)
        }
        done
    }
        .reversed()
        .joinToString(separator = "")

Kotlin’s fold function is really handy. Essentially we carry along a List<Char> that we always have access to, and write a lambda that gets called for each Char in our string. By deciding if something matches, we can either remove the latest char from the done list, or add our new char to the done list. At the end we reverse the list and join it back into a String, but in theory we could just return its length because that’s all the problem is asking for. However, I feel the spirit of the problem calls for us to actually reverse and join the string.

Our solution is now just a matter of reducing the input and returning its length:

fun solvePart1(): Int =
    input.react().length

Star earned! Onward!

⭐ Day 5, Part 2

The puzzle text can be found here.

My first inclination was to create a range of A-Z, remove those letters and their lowercase counterparts from the input, and then call react on each of the resulting strings. This is fine, and would work. However, it adds 26 extra sweeps through our input that we don’t really need to do. What if we still create the A-Z range, but instead of removing those characters, just ignore them when reacting. This will require us to modify our react function to optionally account for a character to ignore.

private fun String.react(ignoring: Char? = null): String =
    this.fold(mutableListOf<Char>()) { done, char ->
        when {
            ignoring != null && char.equals(ignoring, true) -> Unit
            done.firstOrNull() matches char -> done.removeAt(0)
            else -> done.add(0, char)
        }
        done
    }
        .reversed()
        .joinToString(separator = "")

By giving ignoring a default value of null, we can safely call this without ignoring anything (like in part 1). If we call it with an actual character to ignore, we need to measure equality not just of the ignorable char without regard to case. Thankfully, Kotlin has a built in argument to Char.equals to ignore case. Because that part of the when statement doesn’t actually need to do anything, we just have that one evaluate Unit. The rest of the code is the same.

For our solution we create a range, react our input ignoring each element of the range, and find the smallest one:

fun solvePart2(): Int =
    ('A'..'Z')
        .map { input.react(it).length }
        .min()
        ?: throw IllegalStateException()

I felt a bit dirty with the Hold My Beer operator (!!) yesterday, so I’m actually throwing an exception today. But again, we know there will be a value, so you could do it either way. I wish I could somehow write a contract to explain to Kotlin that if I have a non-empty collection, it should have a minimum.

That earns us another star, and brings us to the end of Day 5, 20% done with Advent of Code 2018.

⭐ Day 5, Part 1

⭐ Day 5, Part 2

Further Reading