Skip to Content

Advent of Code 2018 - Day 2, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 2: 'Inventory Management System'

Posted on

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

“Wouldn’t they have had enough fabric to fill several boxes in the warehouse? They’d be stored together, so the box IDs should be similar. Too bad it would take forever to search the warehouse for two similar box IDs…” They walk too far away to hear any more.

Late at night, you sneak to the warehouse - who knows what kinds of paradoxes you could cause if you were discovered - and use your fancy wrist device to quickly scan every box and produce a list of the likely candidates (your puzzle input).

To make sure you didn’t miss any, you scan the likely candidate boxes again, counting the number that have an ID containing exactly two of any letter and then separately counting those with exactly three of any letter. You can multiply those two counts together to get a rudimentary checksum and compare it to what your device predicts.

For example, if you see the following box IDs:

abcdef contains no letters that appear exactly two or three times.
bababc contains two a and three b, so it counts for both.
abbcde contains two b, but no letter appears exactly three times.
abcccd contains three c, but no letter appears exactly two times.
aabcdd contains two a and two d, but it only counts once.
abcdee contains two e.
ababab contains three a and three b, but it only counts once.

Of these box IDs, four of them contain a letter which appears exactly twice, and three of them contain a letter which appears exactly three times. Multiplying these together produces a checksum of 4 * 3 = 12.

What is the checksum for your list of box IDs?

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

Confident that your list of box IDs is complete, you’re ready to find the boxes full of prototype fabric.

The boxes will have IDs which differ by exactly one character at the same position in both strings. For example, given the following box IDs:

abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz

The IDs abcde and axcye are close, but they differ by two characters (the second and fourth). However, the IDs fghij and fguij differ by exactly one character, the third (h and u). Those must be the correct boxes.

What letters are common between the two correct box IDs? (In the example above, this is found by removing the differing character from either ID, producing fgij.)

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(n2), 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.

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 2
  4. Advent of Code - Come join in and do these challenges yourself!