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

Today’s problem let’s us play with a data structure that we don’t see all that often - a Summed-area Table .

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

Problem Input

Our input is a single number, so we will just pass it to our class. See below for details.

⭐ Day 11, Part 1

The puzzle text can be found here.

Normally when I write up part 1 of these, I pretend not to know about part 2, except in the case where we’ll have to refactor something just a little bit. Like turning an Int into a Long prematurely or something like that. Today is not one of those days. We’re going to write the solution to parts 1 and 2 right now, so part 2 gets a lot simpler.

I had originally solved this by manually creating a grid and calculating all of the 3x3 power ratings. This worked fine for part 1, but got very slow for part 2, even by optimizing it with a recursive solution to cut down on calculating sub-squares. It worked, and finished in about 13s, but the #advent-of-code room on the Kotlin Slack pointed me towards a Summed-area Table , and that made this solution much, much quicker.

Thanks to Andy Bowes and Joel Pedraza for the hint!

Summed-Area Table

Let’s go over what a Summed-area table is before we get started. Suppose we have a N x M grid with all 1’s in each spot. In our case, N and M are the same (its a square) but this method also works for rectangles (N != M).

Summed-Area Table - All Ones

What we do is transform this grid into another grid where every box is the sum of ALL of the boxes to its left and above it. By creating that, we would have this kind of grid:

Summed-Area Table - Sums

Once we have that, we can use these numbers to calculate the sum of any N x M subsection in the grid! Suppose we want to get the area in the dark rectangle below:

Summed-Area Table - Rectangle

The problem is that we can’t just take the lower right hand number (25) because it represents a much larger area than we want. What we need to do is subtract out the areas that we don’t want, and then add back in the areas that we have subtracted twice. Look at this diagram:

Summed-Area Table - Overlaps

The black area is the area we want.
The red area is the area we need to subtract out on the left.
The green area is the area we need to subtract out above our range.
The red AND green area is the area we’ve eliminated twice, and need to add back in.

Using the grid above we can walk through it:

Start with the lower right hand corner = 25
Subtract out the red range using its lower right hand corner = 25 - 10 = 15
Subtract out the green range using its lower right hand corner = 15 - 10 = 5
Add back the red and green range using its lower right hand corner = 5 + 4 = 9

The correct answer is 9! Now that we know what we’re doing, we can write our solution!

Solving Part 1

Let’s write the function to calculate the power level for an individual spot first. We’ll also create an extension function on Int to get its hundreds place, if it exists:

private fun powerLevel(x: Int, y: Int): Int {
    val rackId = x + 10
    return (((rackId * y) + serialNumber) * rackId).hundreds() - 5
}

private fun Int.hundreds(): Int = (this / 100) % 10

We can skip creating a grid of values and just skip to the Summed-area table, as we really have no need for the “raw” grid.

private fun createSummedAreaTable(): Array<IntArray> {
    // Create an empty grid
    val summedGrid: Array<IntArray> = Array(gridSize) { IntArray(gridSize) }

    // Fill the grid
    (0 until gridSize).forEach { y ->
        (0 until gridSize).forEach { x ->
            val me = powerLevel(x, y)
            val up = if (y == 0) 0 else summedGrid[y - 1][x]
            val left = if (x == 0) 0 else summedGrid[y][x - 1]
            val upperLeft = if (x == 0 || y == 0) 0 else summedGrid[y - 1][x - 1]
            summedGrid[y][x] = me + up + left - upperLeft
        }
    }

    return summedGrid
}

Our grid is going to be an Array<IntArray> (an array of integer arrays). In this code, we go through all of the X’s and Y’s and calculate the value of each square. Remember, the value of each spot is the value we calculated for the square’s individual power level, plus the square above it, plus the square to its left, minus the value to its upper left (because we’ve already added it in twice). If any of those would run us off the edge of the grid, they are zero.

We’ll write another function called sumOfSquare to do the math we described above in the diagram:

private fun sumOfSquare(x: Int, y: Int, n: Int): Int {
    val lowerRight = summedAreaTable[y][x]
    val upperRight = if (y - n >= 0) summedAreaTable[y - n][x] else 0
    val lowerLeft = if (x - n >= 0) summedAreaTable[y][x - n] else 0
    val upperLeft = if (x - n >= 0 && y - n >= 0) summedAreaTable[y - n][x - n] else 0
    return lowerRight + upperLeft - upperRight - lowerLeft
}

This accounts for underflowing our arrays, and is probably more verbose than is really required, but I wanted to make it clear. So now we have a way to generate a Sum-Area table, and a way to get an arbitrary sum out of that square.

Now we need to write a function to scan our grid for 3 x 3 squares and find the largest sum (its power). But wait… part two is going to ask us for an arbitrarily large size, so let’s build that in now instead of refactoring. Instead of writing a function to find 3 x 3 squares, we’ll write one to find squares of a given range. And since we only ever need to know about the largest, we’ll just return that. In fact, we’ll define a class to return all the data we need:

private class GridSquare(val x: Int, val y: Int, val power: Int, val n: Int)

private fun bestSquareBetweenSizes(smallest: Int, largest: Int): GridSquare =
    (smallest..largest).asSequence().flatMap { n ->
        (n until gridSize).asSequence().flatMap { y ->
            (n until gridSize).asSequence().map { x ->
                GridSquare(x - n + 1, y - n + 1, sumOfSquare(x, y, n), n)
            }
        }
    }.maxBy { it.power }!!

This function runs through our range from smallest to largest, and then for each x and y in our grid. From that it calculates a GridSquare, which represents the x and y coordinate (from the upper left hand site, not the lower right as we are calculating), how big n is, and the power level. As you can see, these are all Sequences because we really don’t need to be creating Lists here. In fact, this would probably work faster if we just tracked the largest values outside the loop instead of constantly creating GridSquares, but I find this clearer.

Now we just have to set up our grid and ask it for the answer, telling it we’re assuming the smallest sub-square we want is 3 wide, and the largest is also 3 wide:

class Day11(private val serialNumber: Int, private val gridSize: Int = 300) {

    private val summedAreaTable: Array<IntArray> = createSummedAreaTable()

    fun solvePart1(): Pair<Int, Int> =
        bestSquareBetweenSizes(3, 3).run { Pair(x, y) }

}

Be really careful when typing the answer into Advent of Code! It doesn’t like 2, 3 because it has spaces. You’ll need to remove them yourself and use 2,3 for example.

Star one earned! To me, that was a ton of fun because I learned all about a data structure I had no idea existed before today!

⭐ Day 11, Part 2

The puzzle text can be found here.

Because we did all of that work to get Part 1 working the way it is, we don’t have to do much for this part. We just have to loop over all x/y combinations and ask for bigger and bigger squares. Once we have them, we can pick out the one with the highest power and that’s our answer!

fun solvePart2(): Triple<Int, Int, Int> =
    bestSquareBetweenSizes(1, gridSize).run { Triple(x, y, n) }

We can reuse bestSquareBetweenSizes and instead of hard coding 3, we give it the full range of the grid - 1 to 300 (gridSize). Turn the highest powered GridSquare into a Triple and that’s our answer. Again, be careful when typing in your answer, Advent of Code doesn’t appear to like spaces.

Second star earned!

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading