Skip to Content

Advent of Code 2018 - Day 11, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 11: 'Chronal Charge'

Posted on

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

You watch the Elves and their sleigh fade into the distance as they head toward the North Pole.

Actually, you’re the one fading. The falling sensation returns.

The low fuel warning light is illuminated on your wrist-mounted device. Tapping it once causes it to project a hologram of the situation: a 300x300 grid of fuel cells and their current power levels, some negative. You’re not sure what negative power means in the context of time travel, but it can’t be good.

Each fuel cell has a coordinate ranging from 1 to 300 in both the X (horizontal) and Y (vertical) direction. In X,Y notation, the top-left cell is 1,1, and the top-right cell is 300,1.

The interface lets you select any 3x3 square of fuel cells. To increase your chances of getting to your destination, you decide to choose the 3x3 square with the largest total power.

The power level in a given fuel cell can be found through the following process:

  • Find the fuel cell’s rack ID, which is its X coordinate plus 10.
  • Begin with a power level of the rack ID times the Y coordinate.
  • Increase the power level by the value of the grid serial number (your puzzle input).
  • Set the power level to itself multiplied by the rack ID.
  • Keep only the hundreds digit of the power level (so 12345 becomes 3; numbers with no hundreds digit become 0).
  • Subtract 5 from the power level.

For example, to find the power level of the fuel cell at 3,5 in a grid with serial number 8:

  • The rack ID is 3 + 10 = 13.
  • The power level starts at 13 * 5 = 65.
  • Adding the serial number produces 65 + 8 = 73.
  • Multiplying by the rack ID produces 73 * 13 = 949.
  • The hundreds digit of 949 is 9.
  • Subtracting 5 produces 9 - 5 = 4.

So, the power level of this fuel cell is 4.

Here are some more example power levels:

  • Fuel cell at 122,79, grid serial number 57: power level -5.
  • Fuel cell at 217,196, grid serial number 39: power level 0.
  • Fuel cell at 101,153, grid serial number 71: power level 4.

Your goal is to find the 3x3 square which has the largest total power. The square must be entirely within the 300x300 grid. Identify this square using the X,Y coordinate of its top-left fuel cell. For example:

For grid serial number 18, the largest total 3x3 square has a top-left corner of 33,45 (with a total power of 29); these fuel cells appear in the middle of this 5x5 region:

-2  -4   4   4   4
-4   4   4   4  -5
 4   3   3   4  -4
 1   1   2   4  -3
-1   0   2  -5  -2

For grid serial number 42, the largest 3x3 square’s top-left is 21,61 (with a total power of 30); they are in the middle of this region:

-3   4   2   2   2
-4   4   3   3   4
-5   3   3   4  -4
 4   3   3   4  -3
 3   3   3  -5  -1

What is the X,Y coordinate of the top-left fuel cell of the 3x3 square with the largest total power?

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

You discover a dial on the side of the device; it seems to let you select a square of any size, not just 3x3. Sizes from 1x1 to 300x300 are supported.

Realizing this, you now must find the square of any size with the largest total power. Identify this square by including its size as a third parameter after the top-left coordinate: a 9x9 square with a top-left corner of 3,5 is identified as 3,5,9.

For example:

  • For grid serial number 18, the largest total square (with a total power of 113) is 16x16 and has a top-left corner of 90,269, so its identifier is 90,269,16.
  • For grid serial number 42, the largest total square (with a total power of 119) is 12x12 and has a top-left corner of 232,251, so its identifier is 232,251,12.

What is the X,Y,size identifier of the square with the largest total power?

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!

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