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

Day 2 of Advent of Code is here, and this was an interesting problem for Kotlin. There might be faster ways to solve this problem, but I feel like this is a pretty clear solution that is easy to explain.

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

Problem Input

Once again our input is a bunch of Strings, so I’ll just parse them into a List<String> and hand it into our class for today’s problem. Since there isn’t any additional manipulation required, I’ll just make it a private var.

class Day02(private val input: List<String>) {
	...
}

⭐ Day 2, Part 1

The puzzle text can be found here.

In my head, this was a lot easier until I read “two a and two d, but it only counts once”. So if there are multiple pairs, we only care that it happened at all, not how many pairs in each String there are. In order to get started, I wrote an extension function on String to determine if there are any pairs of 2 or 3. I did this by returning a Pair<Boolean, Boolean>, where the first slot represents a set of 2 and the second slot represents a set of 3.

private fun String.findLetterSets(): Pair<Boolean, Boolean> {
    val byChar = this.groupingBy { it }.eachCount()
    return Pair(
        byChar.any { it.value == 2 },
        byChar.any { it.value == 3 }
    )
}

Thanks to groupingBy, this is pretty simple code. It creates a Map<Char, Int>, and then we just go find out if the map contains any 2’s or 3’s.

And then we use that Pair<Boolean, Boolean> for each String, and count the number of true flags in each position:

fun solvePart1(): Int {
    val pairs = input.map { it.findLetterSets() }
    return pairs.count { it.first } * pairs.count { it.second }
}

That earns us our first star of the day!

⭐ Day 2, Part 2

The puzzle text can be found here.

OK, in order to do this one we’re going to need to slice and dice Strings. Knowing that we will eventually have to produce an entirely new String at the end of the problem complicates this. It would be a lot easier of we could return one or both of the paired Strings, wouldn’t it? Let’s go ahead and write a extension function to remove a single character from a String, because we’ll end up needing it in the end. Since Strings in Kotlin and Java are immutable, we’ll need to reconstruct our new String without the index we want to remove:

private fun String.removeAt(index: Int): String =
    if (this.length <= 1) ""
    else this.substring(0 until index) + this.substring(index + 1)

Now that that’s out of the way, let’s write a function to find the difference between two Strings. By “difference” in this case I mean the indexes of all the differences. We’re going to take full advantage of the fact that all of our inputs are the same length.

private fun String.diffIndexes(other: String): List<Int> =
    this
        .mapIndexed { idx, char -> if (other[idx] != char) idx else null }
        .filterNotNull()

Let me explain that. We loop through each character in the String we call our extension on and get each character and its index. Then we compare that character with its pair in the “other” string. If they are different, we record the index, otherwise we record null. Once we filter out the nulls we are left with a List<Int>, where the values represent the indexes of the characters that differ, if any.

We also could have used zip to write this same function but it ended up being slower, creating a lot of Pair objects that we ended up throwing away, and didn’t seem any clearer to me. Maybe it’s clearer to you? If so, use this instead:

// Alternate implementation
private fun String.diffIndexes(other: String): List<Int> =
    this.zip(other)
        .mapIndexed{ idx, pair -> if(pair.first != pair.second) idx else null }
        .filterNotNull()

Now for the tricky part. The runtime of this section isn’t stellar at O(n²), but I feel it’s pretty clear, and if we’re working on small sets of input I’ll take clarity over just about any other factor. What we’re going to do is loop through all of the input strings, and compare it to every other String that comes after it (because if we compare the ones before it, we’ll be doing work twice). We find the first pair that has a single difference, remove the offending character, and return it. Let’s see the code, and then I’ll explain it some more:

fun solvePart2(): String =
    input
        .asSequence()
        .mapIndexed { i, outer ->
            input.asSequence().drop(i).mapNotNull { inner ->
                val diff = outer.diffIndexes(inner)
                if (diff.size == 1) {
                    outer.removeAt(diff.first())
                } else {
                    null
                }
            }
        }
        .flatten()
        .first()

Yikes! First, you’ve probably noticed asSequence(). If we had left it as a List, it would have worked just the same, but wouldn’t have been evaluated lazily and would have ended up creating and throwing away a lot of objects. In this example, we have the notion of an “outer” string and an “inner” string. The outer string is the string we are comparing against all of the strings that come after it. The inner string is the second string. So for each outer, we compare it against many inners. That’s why we have that input.asSequence().drop(i). We drop all of the strings we’ve already compared because there is no sense in comparing A vs. B, just to turn around and compare B vs. A - the answer never changes!

The inner guts of the loop use the extension functions we’ve already written. In this case we compare the inner and outer strings. If they differ by one and only one place, we remove the differing character and add our new String to the results. Otherwise, we return null because these strings don’t match closely enough. Because we are using mapNotNull, Kotlin will remove the nulls for us. We then flatten this (because of our nested structure, we have a Sequence<Sequence<String>>, and really want a Sequence<String>), find the first element, and return it - our answer.

I know that seems like a lot, but to me this was as simple as I could get it. Again, it might be faster if we avoid the sequences and just track dueling index values, but I feel that looks a bit unclean. I like that this is a single expression.

This earns us our second star of the day! Good work.

⭐ Day 2, Part 1

⭐ Day 2, Part 2

Further Reading