Skip to Content

Advent of Code 2021 - Day 20, in Kotlin - Trench Map

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 20: 'Trench Map'

Posted on

On the surface, this problem looks a lot simpler (to me) than it really is. I didn’t look at my sample input (I almost never do, I just download it and add it to git because I’ve accidentally messed it up before by hitting a key I didn’t mean to). I just didn’t see the twist between the sample input and the actual input. That’s what made today’s puzzle fun for me - the dawning realization that I had underestimated the difficulty and that I’d probably have to sit and think things through.

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

Problem Input

Initially, I had represented the “on” pixels in today’s puzzle as a Set<Point2d>, and that worked fine for the sample input. But Eric Wastl can be tricky and made our actual input do weird things. My initial input (and I suspect yours as well) starts with a #. That means if we go through and map a fully empty 3x3 grid, we’ll end up turning that spot on. Infinitely. So we’ll have to get clever.

Today, we’ll store our grid in a List<String>. This makes it easy to grow our grid outwards for each successive generator, and keeps the data in a format we can index into.

class Day20(input: List<String>) {

    private val algorithmString: String = input.first().map { if (it == '#') '1' else '0' }.joinToString("")
    private val startingImage: List<String> = parseInput(input)


    private fun parseInput(input: List<String>): List<String> =
        input.drop(2).map { row ->
            row.map { char ->
                if (char == '#') 1 else 0
            }.joinToString("")
        }
}

In each case, we’ll represent “on” with 1 and “off” with 0. We set aside the first row of input to be the algorithmString, and put the rest in the startingImage (our List<String).

⭐ Day 20, Part 1

The puzzle text can be found here.

Now that we’re parsed our input, let’s talk strategy. Because the universe of points is “infinite”, we’ll have to consider points slightly outside our data model during each round of enhancement. By experimenting, I found that expanding the grid by 1 in each direction per round is all we need. The trick in today’s puzzle is that as we do that, we end up converting totally empty space to a string of all 0’s, which means our input will have us turn on that spot (because the algorithmString starts with #). That would be fine if it stayed that way, but if we look at 9 neighbors that are all “on” we’ll end up looking at the last element in the algorithmString and it is . (off). The effect is that in one round we turn the infinite void on, and in the next we turn it all off. Not ideal. To counteract this, we’ll define a defaultValue, which is going to be either a 0 or a 1. It too will flip back and forth each round, and we’ll use that to indicate if a spot immediately outside our grid is either on or off (depending on its state, which flips per round).

To do all that, we’ll need to know the nine points we look at for any given Point2d. I won’t add this to Point2d as I don’t think we’ll end up using it (maybe I’m wrong, we can move it if things change later).

// In Day20

private fun Point2d.surrounding(): List<Point2d> =
    listOf(
        Point2d(x - 1, y - 1), Point2d(x, y - 1), Point2d(x + 1, y - 1),
        Point2d(x - 1, y), this, Point2d(x + 1, y),
        Point2d(x - 1, y + 1), Point2d(x, y + 1), Point2d(x + 1, y + 1),
    )

It’s important that these are in “reader” order (top left going right, down one line, go right, etc).

Next, we’ll need to know if this Point2d is inside the bounds of the universe we care about. We’ll add an extension operator function on List<String> to measure a Point2d against the bounds of the data structure.

// In Day20

private operator fun List<String>.contains(pixel: Point2d): Boolean =
    pixel.y in this.indices && pixel.x in this.first().indices

Now that we know those things, we want to get the value of a point in or out of the data structure. Remember how we said we’d need to keep track of what “on” and “off” mean in the infinite void space between rounds? That’s what defaultValue is for here. If the pixel we want is in the grid we’ve got, that’s fine, return whatever is there. Otherwise, we can’t simply just return “off”, we might have to return “on” sometimes. In those cases we return defaultValue and make calculating that some other function’s problem.

// In Day20

private fun List<String>.valueAt(pixel: Point2d, defaultValue: Char): Char =
    if (pixel in this) this[pixel.y][pixel.x] else defaultValue

For each round, we’ll expand our data structure by 1 in each direction. We can set this up by using ranges for x and y. We evaluate every Point2d in that range by finding its surrounding neighbors, mapping those points to their on/off 1/0 values, converting that to a String and then converting that String from binary to an Int using toInt(2) (2 being binary). We look that value up in the algorithmString and repeat. Eventually, we’ll create a new List<String> of what the next step of the enhancement process looks like.

// In Day20

private fun List<String>.nextRound(defaultValue: Char): List<String> =
    (-1..this.size).map { y ->
        (-1..this.first().length).map { x ->
            algorithmString[
                Point2d(x, y)
                    .surrounding()
                    .map { this.valueAt(it, defaultValue) }
                    .joinToString("")
                    .toInt(2)
            ]
        }.joinToString("")
    }

And now we can write a function to call nextRound as many times as we want. We could do this iteratively but I like fold for this purpose. There are a couple of fun things to watch out for here. Our initial state for the fold is comprised of both the startingImage and the initial defaultValue, which we will set to 0. We destructure this inside the fold’s lambda to make it easier to manage. Every time through the fold, we first calculate the nextRound image based on the previous one, and then calculate the next value for defaultValue, which should flip back and forth for real inputs. Basically, picking either the first or last element from the algorithmString in alternating iterations.

// In Day20

private fun solve(rounds: Int): Int =
    (1 .. rounds).fold(startingImage to '0') { (image, defaultValue), _ ->
        image.nextRound(defaultValue) to if (defaultValue == '0') algorithmString.first() else algorithmString.last()
    }.first.sumOf { it.count { char -> char == '1' } }

At the end of the fold, we count up the number of times we see 1 in our data structure, and that’s how many lights we see. Note that we could have gone with Array<IntArray> for our data structure to make this part easier (a sum of sums rather than a sum of counts). But that would have made the nextRound function more complicated when piecing together the binary number.

All that’s left to do is call solve twice:

// In Day20

fun solvePart1(): Int =
    solve(2)

Star earned! Onward!

⭐ Day 20, Part 2

The puzzle text can be found here.

Change the 2 to a 50 and we’re done. :)

// In Day20
    
fun solvePart2(): Int =
    solve(50)

Star earned!

Further Reading

  1. Index of All Solutions - All posts and solutions for 2021, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 20
  4. Advent of Code - Come join in and do these challenges yourself!