Skip to Content

Advent of Code 2018 - Day 3, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 3: 'No Matter How You Slice It'

Posted on

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 Elves managed to locate the chimney-squeeze prototype fabric for Santa’s suit (thanks to someone who helpfully wrote its box IDs on the wall of the warehouse in the middle of the night). Unfortunately, anomalies are still affecting them - nobody can even agree on how to cut the fabric.

The whole piece of fabric they’re working on is a very large square - at least 1000 inches on each side.

Each Elf has made a claim about which area of fabric would be ideal for Santa’s suit. All claims have an ID and consist of a single rectangle with edges parallel to the edges of the fabric. Each claim’s rectangle is defined as follows:

The number of inches between the left edge of the fabric and the left edge of the rectangle.
The number of inches between the top edge of the fabric and the top edge of the rectangle.
The width of the rectangle in inches.
The height of the rectangle in inches.

A claim like #123 @ 3,2: 5x4 means that claim ID 123 specifies a rectangle 3 inches from the left edge, 2 inches from the top edge, 5 inches wide, and 4 inches tall. Visually, it claims the square inches of fabric represented by # (and ignores the square inches of fabric represented by .) in the diagram below:

...........
...........
...#####...
...#####...
...#####...
...#####...
...........
...........
...........

The problem is that many of the claims overlap, causing two or more claims to cover part of the same areas. For example, consider the following claims:

#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2

Visually, these claim the following areas:

........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........

The four square inches marked with X are claimed by both 1 and 2. (Claim 3, while adjacent to the others, does not overlap either of them.)

If the Elves all proceed with their own plans, none of them will have enough fabric.

How many square inches of fabric are within two or more claims?

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

Amidst the chaos, you notice that exactly one claim doesn’t overlap by even a single square inch of fabric with any other claim. If you can somehow draw attention to it, maybe the Elves will be able to make Santa’s suit after all!

For example, in the claims above, only claim 3 is intact after all claims are made.

What is the ID of the only claim that doesn’t overlap?

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!

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