Skip to Content

Advent of Code 2018 - Day 4, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 4: 'Repose Record'

Posted on

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

I cut the description down a bit, go check out the full one, its funny.

For example, consider the following records, which have already been organized into chronological order:

[1518-11-01 00:00] Guard #10 begins shift
[1518-11-01 00:05] falls asleep
[1518-11-01 00:25] wakes up
[1518-11-01 00:30] falls asleep
[1518-11-01 00:55] wakes up
[1518-11-01 23:58] Guard #99 begins shift
[1518-11-02 00:40] falls asleep
[1518-11-02 00:50] wakes up
[1518-11-03 00:05] Guard #10 begins shift
[1518-11-03 00:24] falls asleep
[1518-11-03 00:29] wakes up
[1518-11-04 00:02] Guard #99 begins shift
[1518-11-04 00:36] falls asleep
[1518-11-04 00:46] wakes up
[1518-11-05 00:03] Guard #99 begins shift
[1518-11-05 00:45] falls asleep
[1518-11-05 00:55] wakes up

Timestamps are written using year-month-day hour:minute format. The guard falling asleep or waking up is always the one whose shift most recently started. Because all asleep/awake times are during the midnight hour (00:00 - 00:59), only the minute portion (00 - 59) is relevant for those events.

Visually, these records show that the guards are asleep at these times:

Date   ID   Minute
            000000000011111111112222222222333333333344444444445555555555
            012345678901234567890123456789012345678901234567890123456789
11-01  #10  .....####################.....#########################.....
11-02  #99  ........................................##########..........
11-03  #10  ........................#####...............................
11-04  #99  ....................................##########..............
11-05  #99  .............................................##########.....

The columns are Date, which shows the month-day portion of the relevant day; ID, which shows the guard on duty that day; and Minute, which shows the minutes during which the guard was asleep within the midnight hour. (The Minute column’s header shows the minute’s ten’s digit in the first row and the one’s digit in the second row.) Awake is shown as ., and asleep is shown as #.

Note that guards count as asleep on the minute they fall asleep, and they count as awake on the minute they wake up. For example, because Guard #10 wakes up at 00:25 on 1518-11-01, minute 25 is marked as awake.

If you can figure out the guard most likely to be asleep at a specific time, you might be able to trick that guard into working tonight so you can have the best chance of sneaking in. You have two strategies for choosing the best guard/minute combination.

Strategy 1: Find the guard that has the most minutes asleep.

What minute does that guard spend asleep the most?

In the example above, Guard #10 spent the most minutes asleep, a total of 50 minutes (20+25+5), while Guard #99 only slept for a total of 30 minutes (10+10+10). Guard #10 was asleep most during minute 24 (on two days, whereas any other minute the guard was asleep was only seen on one day).

While this example listed the entries in chronological order, your entries are in the order you found them. You’ll need to organize them before they can be analyzed.

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:

  1. 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!
  2. 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.
  3. If a guard falls asleep or wakes up, we only care about the minute that it happened and nothing else.
  4. 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

Strategy 2: Of all guards, which guard is most frequently asleep on the same minute?

In the example above, Guard #99 spent minute 45 asleep more than any other guard or minute - three times in total. (In all other cases, any guard spent any minute asleep at most twice.)

What is the ID of the guard you chose multiplied by the minute you chose? (In the above example, the answer would be 99 * 45 = 4455.)

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!

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