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

Day 4 was interesting for me in that I originally had a much different solution. Once I got the answers and had my tests passing, I just wasn’t quite happy with the code so I sat and thought about it for a few minutes. One of the things I do when solving these problems is make bad assumptions about what part 2 will look like when solving part 1, so I tend to over-write code. By going back over the problem, I was able to see where I was doing a lot of work to carry around data, or format it a specific way, where I really didn’t need to. Refactoring and sticking to just the barest essentials made this solution a lot simpler in the end.

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

Problem Input

We are given a file that has one log per line, unsorted. We will sort and parse this into a usable structure in the code for part 1.

⭐ Day 4, Part 1

The puzzle text can be found here.

That’s a lot of text, and it really look me a while to understand what we’re being given and what we’re being asked for. In my original implementation I did a lot of work to keep the full time and date (using LocalDateTime) but once I realized that we didn’t care about dates, just the number of minutes, this got a lot easier.

The strategy we’re going to use for this is to make a map, where the key is the guard’s id, and the value is a list of minutes that the guard is sleeping. Even if a guard is asleep in the same minute on different shifts, they will both be in the list. Doing that gives us a Map<Int, List<Int>>.

First we are going to have to parse our input into this structure. If you look at the input, we can make several assumptions:

If we want them in order by time, we can just do a natural sort. Thankfully, the puzzle author used YYYY-MM-DD for the date format!
We can assume that guards show up to work awake. This means if a guard shows up early at 23:59, we don’t have to worry about that.
If a guard falls asleep or wakes up, we only care about the minute that it happened and nothing else.
If a guard shows up to work, we only care about the guard number and nothing else.

Keeping that in mind, let’s write a couple of regular expressions to help us:

companion object {
    private val guardPattern = """^.+ #(\d+) .+$""".toRegex()    // Extract guard id
    private val timePattern = """^\[.+:(\d\d)] .+$""".toRegex()  // Extract minute
}

Because we’re always going to be getting a single value from the regular expression, we’ll define an extension function to assist us. I’ve resisted my urge to put this in my Extensions.kt file, but we might move it there later if another puzzle ends up needing this.

private fun Regex.single(from: String): String =
    this.find(from)!!.destructured.component1()

And Kotlin’s Hold My Beer operator (!!) finally makes an appearance! I try to avoid writing !! in Kotlin code, but in this case I feel it’s the best option. Here we are asking our regular expression to find a single matching group in a string. Because we know that it is there, we don’t really want to have to handle the case where no match happens. So we use !! to tell Kotlin “I understand you want this to be nullable, but I know better, trust me”. The alternative would be to handle this with ?.let, and then throw an exception if parsing fails. I felt the brevity of !! was a worthwhile trade-off.

Now that we have our helpers, we can write the parser logic:

private fun parseInput(input: List<String>): Map<Int, List<Int>> {
    val sleeps = mutableMapOf<Int, List<Int>>()
    var guard = 0
    var sleepStart = 0

    input.sorted().forEach { row ->
        when {
            row.contains("Guard") -> guard = guardPattern.single(row).toInt()
            row.contains("asleep") -> sleepStart = timePattern.single(row).toInt()
            else -> {
                val sleepMins = (sleepStart until timePattern.single(row).toInt()).toList()
                sleeps.merge(guard, sleepMins) { a, b -> a + b }
            }
        }
    }
    return sleeps
}

As you can see, we’re sorting the input, so we can just loop through it all and create our map structure. We keep track of the current guard. When we see that they have fallen asleep we note the time. When they awaken we take the time they fell asleep and the time they woke up and create a list of all the minutes between that time. We do this by creating a range and converting it to a List<Int>. For example, if guard 1 fell asleep at 00:01 and woke up at 00:04, we would have a listOf(1,2,3), because the wake-up time is exclusive. Because the List<Int> associated with our guard may already exist, we have to merge the existing list with our new list. This is a really neat function from the Java standard library that I’ve never used before.

At this point we know all of the minutes that each guard is asleep. Solving the problem is essentially going through all of the guards and finding the one that has the longest list of minutes asleep.

fun solvePart1(): Int =
    sleepMinutesPerGuard
        .maxBy { it.value.size }!!
        .run { key * value.mostFrequent()!! }

More Hold My Beer operator?! Yes, I know, I know. But again, in this case, we know that these values will exist. We know we have guards, and therefore must have a sleepiest one. We can safely tell Kotlin that these won’t ever be null. The alternative would have been to add ?: throw IllegalArgumentException() in its place, and that just felt messy under the circumstances. If this were a production system, I’d probably handle errors and possible nulls more gracefully.

If it were a matter of finding just the sleepiest guard, we would be done with the maxBy { it.value.size }!! call. This looks through all of the values in the Map, and finds the longest list. But we’re asked to multiply the guard’s id with the minute they sleep the most in. I wrote an extension function to find the most frequent element in a list, and put that in my Extensions.kt file:

fun <T> Iterable<T>.mostFrequent(): T? =
    this.groupBy { it }.maxBy { it.value.size }?.key

This returns a T? because we can’t be sure the Iterable has elements in it. To find the most frequent, we group the elements by their identity, and find the longest list, returning the identity (the map key).

Running this gives us our first star of the day! Onward!

⭐ Day 4, Part 2

The puzzle text can be found here.

I’ll confess I had to read this a few times to understand what is being asked, but once I understood it the solution came together without having to write much more code. The approach we’ll take here is to make a list of Pair<Int, Int>, where the first element is the guard’s id, and the second element is the minute they were asleep. This means we will have a list of every minute that every guard slept.

fun solvePart2(): Int =
    sleepMinutesPerGuard.flatMap { entry ->
        entry.value.map { minute ->
            entry.key to minute // Guard to Minute
        }
    }
        .mostFrequent()!! // Which guard slept the most in a minute?
        .run { first * second }

The flatmap/map structure should look familiar. We’re looping through nested structures and need to flatten them out. Once that loop is over we have a List<Pair<Int,Int>>. Calling .mostFrequent() on it gives us the guard and minute that shows up the most! We use run as a general purpose map, and multiply the guard id and minute together for our answer!

That’s another star, and another day done. I really enjoyed this puzzle because my first implementation “worked”, but wasn’t something I was very proud of. It felt wrong because I was doing way too much data management and parsing. By going back and writing down those assumptions above, my code became a lot clearer!

⭐ Day 4, Part 1

⭐ Day 4, Part 2

Further Reading