Skip to Content

Advent of Code 2018 - Day 5, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 5: 'Alchemical Reduction'

Posted on

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

You’ve managed to sneak in to the prototype suit manufacturing lab. The Elves are making decent progress, but are still struggling with the suit’s size reduction capabilities.

While the very latest in 1518 alchemical technology might have solved their problem eventually, you can do better. You scan the chemical composition of the suit’s material and discover that it is formed by extremely long polymers (one of which is available as your puzzle input).

The polymer is formed by smaller units which, when triggered, react with each other such that two adjacent units of the same type and opposite polarity are destroyed. Units’ types are represented by letters; units’ polarity is represented by capitalization. For instance, r and R are units with the same type but opposite polarity, whereas r and s are entirely different types and do not react.

For example:

  • In aA, a and A react, leaving nothing behind.
  • In abBA, bB destroys itself, leaving aA. As above, this then destroys itself, leaving nothing.
  • In abAB, no two adjacent units are of the same type, and so nothing happens.
  • In aabAAB, even though aa and AA are of the same type, their polarities match, and so nothing happens.

Now, consider a larger example, dabAcCaCBAcCcaDA:

dabAcCaCBAcCcaDA  The first 'cC' is removed.
dabAaCBAcCcaDA    This creates 'Aa', which is removed.
dabCBAcCcaDA      Either 'cC' or 'Cc' are removed (the result is the same).
dabCBAcaDA        No further actions can be taken.

After all possible reactions, the resulting polymer contains 10 units.

How many units remain after fully reacting the polymer you scanned?

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

Time to improve the polymer.

One of the unit types is causing problems; it’s preventing the polymer from collapsing as much as it should. Your goal is to figure out which unit type is causing the most problems, remove all instances of it (regardless of polarity), fully react the remaining polymer, and measure its length.

For example, again using the polymer dabAcCaCBAcCcaDA from above:

  • Removing all A/a units produces dbcCCBcCcD. Fully reacting this polymer produces dbCBcD, which has length 6.
  • Removing all B/b units produces daAcCaCAcCcaDA. Fully reacting this polymer produces daCAcaDA, which has length 8.
  • Removing all C/c units produces dabAaBAaDA. Fully reacting this polymer produces daDA, which has length 4.
  • Removing all D/d units produces abAcCaCBAcCcaA. Fully reacting this polymer produces abCBAc, which has length 6.

In this example, removing all C/c units was best, producing the answer 4.

What is the length of the shortest polymer you can produce by removing all units of exactly one type and fully reacting the result?

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.

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 5
  4. Advent of Code - Come join in and do these challenges yourself!