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

Welcome to Day 3 of Advent of Code 2018! Today’s problem lets us explore a lot of the build in features that Kotlin has for collections.

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

Problem Input

Today’s input is going to require a data class to hold it and a regular expression to parse it. So let’s treat parsing it as a separate task from parts 1 or 2. First, we will create a data class called Claim, which holds the claim id, left and top offsets, width, and height:

data class Claim(val id: Int, val left: Int, val top: Int, val width: Int, val height: Int)

And since we need to turn a String into a Claim, let’s also write a companion object for our Claim, do to the parsing:

data class Claim(val id: Int, val left: Int, val top: Int, val width: Int, val height: Int) {

    // This code parses a String into a Claim, using a Regular Expression
    companion object {
        private val pattern = """^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$""".toRegex()
        fun parse(input: String): Claim =
            pattern.find(input)?.let {
                val (id, left, top, w, h) = it.destructured
                Claim(id.toInt(), left.toInt(), top.toInt(), w.toInt(), h.toInt())
            } ?: throw IllegalArgumentException("Cannot parse $input")
    }
}

Don’t worry, I know that looks complicated. First, we defined a variable called pattern, which is our Regular Expression. A regular expression is a way of describing a pattern to a computer, and in this case it matches our inputs. We put various symbols in parenthesis to tell the pattern that we want to group certain things and capture them. In this case, the id, left offset, top offset, width, and height. We feed the String input into our pattern and find the groups we are looking for. Because the groups might not get found, I’m wrapping the whole thing in let, which lets us fail out if the parse isn’t successful. Then it’s a matter of telling the regular expression to destructure what it found for us, and to create a Claim object from that data.

Regular Expressions can be very powerful tools if you parse text, and are available in every language you’ll run across. It’s worth spending time to learn the basics. Otherwise, we’d have to write our own parse logic that looked for symbols and split strings, and found commas and whatnot. The Regular Expression just makes this a lot simpler.

⭐ Day 3, Part 1

The puzzle text can be found here.

This might seem tricky at first, and there are a couple of ways to solve it. We could define a 1000x1000 array and count the number of claims that end up in each spot, and then count the number of spots that are filled with more than one claim. That would work. However, I’m going to just defined a Map, where the key is a Pair<Int,Int>, representing a pair of coordinates, and the value is another Int, representing the number of claims in that spot. Once we have that, we can count up how many values are greater than 1, and that’s how many claims we have overlapping!

But first, we need a way for a Claim to express the area it takes up, as a list of Pair<Int,Int>, so lets write that:

data class Claim(val id: Int, val left: Int, val top: Int, val width: Int, val height: Int) {
    fun area(): List<Pair<Int, Int>> =
        (0 + left until width + left).flatMap { w ->
            (0 + top until height + top).map { h ->
                Pair(w, h)
            }
        }
}

All our area function does is set up a double loop over the width and height, and creates a List<Pair<Int,Int>>. Notice we have to flatmap our outer loop, or we would end up with the wrong data structure (a List<List<Pair<Int,Int>>> instead). We need to flatten the results of each inner call into one single list. This is a pretty common pattern when setting up nested mapping structures.

Now that we can determine all of the spots a Claim has, we can write our solution as a single expression!

fun solvePart1(): Int =
    claims
        .flatMap { it.area() }  // List<Pair<Int,Int>>
        .groupingBy { it }
        .eachCount()            // Map<Pair<Int,Int>, Int>
        .count { it.value > 1 }

Essentially, flatMap/groupingBy/eachCount is a nice way to end up with a Map<Pair<Int,Int>>, Int>, where they key is a spot, and the value is the number of times we’ve seen that spot. The groupingBy function returns a Grouping object, which we always have to turn into something else. It’s good for holding data and shaping it how we’d like it, but you probably wouldn’t use it as one of your primary data structures. In this case, we tell it we just want the values counted, rather than enumerated or folded over or something like that. That’s how we end up, at least for now, with our Map<Pair<Int,Int>, Int>.

From there, we count the number of values that are greater than 1, and we have our answer. Like I said above, there are a few ways to solve this, but I think this is a really nice example of what’s in Kotlin’s standard library if you take the time to play around with it.

Star 1 earned, on to part 2!

⭐ Day 3, Part 2

The puzzle text can be found here.

I really wanted to write this as a nice single expression but I just couldn’t find an elegant way to do it, so we’ll have to deal with some side effects. Essentially we are going to maintain another Map<Pair<Int,Int>, Int>, but rather than store a count, the value in this case is going to be a claim id. That way, when we add new spots to the map, we can check to see if we’re overlapping another claim. If we maintain another set of all claim ids, we can remove claims that overlap each other as we discover them. Then we just find the single result left in the set of claim ids, and that’s the one that never overlapped anything else.

fun solvePart2(): Int {
    val cloth = mutableMapOf<Pair<Int, Int>, Int>()
    val uncovered = claims.map { it.id }.toMutableSet()
    claims.forEach { claim ->
        claim.area().forEach { spot ->
            val found = cloth.getOrPut(spot) { claim.id }
            if (found != claim.id) {
                uncovered.remove(found)
                uncovered.remove(claim.id)
            }
        }
    }
    return uncovered.first()
}

In the code above, cloth is the map of spot to claim id, and uncovered is the set of all claim ids. We loop through all of the spots that make up each claim and insert them into the cloth map. If we find that we’ve just replaced a value in the map, we can deduce that it must be another claim. And from that, we can remove both the claim id of the claim we’re working on, as well as the one we found that overlapped.

In the end, we just return the single value left in the uncovered set.

And that earns us two stars for today!

⭐ Day 3, Part 1

⭐ Day 3, Part 2

Further Reading