Advent of Code 2020 - Day 20, in Kotlin - Jurassic Jigsaw • Todd Ginsberg

If you ask me, today’s puzzle has been the most difficult one of 2020 so far. I had a really fun time trying to solve this, including an extended period of time trying to track down what turned out to be a transposition error. Today’s solution involves a lot of code, so I hope this comes across clearly and effectively. As usual, if you have any questions, my contact information is on the bottom of each page, and I’m happy to help explain something a little better

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

Problem Input

We will read our entire puzzle input in as a single String today, and we will parse that into a List<Tile>. Our Tile class is going to grow a lot, but we’ll start with the basics here so we can get our input parsing out of the way.

Let’s define Tile as a private class within Day20. If we need another Tile in the future, we can either pull this out to its own file and refactor it, or we can define a new one without namespace colissions.

// In Day20

private class Tile(val id: Long, var body: Array<CharArray>) {
    // ...
}

Let’s go over Tile and the intent behind it before figuring out our parser. Each Tile has an id, which we will define as a Long. We could leave it as a String, and convert it right at the end when we answer Part 1, but this seems cleaner. The body of the Tile is the visual representation, and is defined as an Array<CharArray>>. Normally, I’d probably define body as a List<String>, but since we will be changing the tile in-place in part 2 (and in theory, you could rewrite some functions from part 1 to be more efficient). The body is defined as a var, so we can overwrite it completely for some operations.

Now that we know what our destination format is, we can parse our input:

// In Day21

private fun parseInput(input: String): List<Tile> =
    input.split("\n\n").map { it.lines() }.map { tileText ->
        val id = tileText.first().substringAfter(" ").substringBefore(":").toLong()
        val body = tileText.drop(1).map { it.toCharArray() }.toTypedArray()
        Tile(id, body)
    }

Each tile in our input is separated by two newlines (note: If you save this on Windows, these might be different for you). The first row of each tile declares its id, and can then be discarded. To parse out the id, we use a combination of substringAfter and substringBefore, from the Kotlin standard library to isolate our id. We’ll also convert it from a String to a Long here.

Next, we need to parse out the body for each Tile. To do that, we drop the first row (with the id) and turn the remaining rows into CharArray instances, and wrap all of those up in an Array, by calling toTypedArray on the result from the map call (which is a List<CharArray> at that point).

We can then use this to parse our input when we define today’s solution class:

class Day20(input: String) {

    private val tiles: List<Tile> = parseInput(input)

}

⭐ Day 20, Part 1

The puzzle text can be found here.

Before we begin, I want to discuss some observations with the Tile objects. We’re mostly going to be considering the sides of each tile, and I’ll refer to these by their cardinal directions (North, South, East, West) for lack of a better term.

When considering the sides of the tiles, tiles will fall into three categories:

Tiles that have TWO sides in common with other tiles on the grid are CORNER PIECES

Tiles that have THREE sides in common with other tiles on the grid are EDGE PIECES

Tiles that have FOUR sides in common with other tiles on the grid are INTENRAL PIECES

Another observation is:

For every side that is SUPPOSED to match, there will only ever be ONE candidate. Thankfully the puzzle author did NOT make it so that for a given side, there would be more than one match.

This means if we say “Search for tiles that have a side that looks like X”, we will only have two tiles in the whole set that meet that condition, and they will pair up.

Given these facts, we now ONLY really care about finding a single corner and orienting it in a direction that we can base our puzzle off of. This means that for our purposes tiles fit into two categories:

A corner piece we can start with.
Anything else.

Orientation and Sides

I’ve talked a lot about “orientation” and “sides”, so lets define some code to manage those concepts.

First, we’ll define a private enum called Orientation in our Day20 class, to represent how a puzzle piece is facing:

// In Day20

private enum class Orientation {
    North, East, South, West
}

We could have made those sealed classes and moved some logic into them, but I feel like for a self-contained puzzle class, this works fine.

Next, we need a private function in Tile in order to parse out what a specific side looks like. We won’t cache these answers because we will be rotating and flipping these tiles, so these answers will change:

// In Day20.Tile

private fun sideFacing(dir: Orientation): String =
    when (dir) {
        Orientation.North -> body.first().joinToString("")
        Orientation.South -> body.last().joinToString("")
        Orientation.West -> body.map { row -> row.first() }.joinToString("")
        Orientation.East -> body.map { row -> row.last() }.joinToString("")
    }

In case you are curious, when I wrote this I transposed how to calculate East and South (WHY?!). This took me an extra long time to figure out because my puzzle was being put together in a weird order and I just couldn’t figure it out.

Anyway. Given an Orientation, we want to know how to pick that side out of the body. For North and South, we take the first and last rows of the body respectively, and turn the CharArray into a String via joinToString. For West and East, we take the first or last characters of each row respectively and map them into a List<Char>, before converting them to Strings.

Because later on we’ll be asking each Tile if it has a side matching a specific pattern, we are going to have each Tile cache which sides it has. Not only the sides that it has now, in this orientation, but what would happen if we flipped this Tile? What sides would it have then? Therefore, we’ll define these two concepts as private properties in our Tile class:

// In Day20.Tile

private val sides: Set<String> = Orientation.values().map { sideFacing(it) }.toSet()
private val sidesReversed = sides.map { it.reversed() }.toSet()

To create our sides, we loop through each Orientation and ask for that sideFacing. And because we don’t really need these a a List<String>, we’ll convert it to a Set<String>. Figuring out what each side would be if the tile were to become flipped over, we reverse each side and put it in its own Set<String>. We could have put them both in one set, but this way to me seems a bit clearer, especially later on when we are finding match candidates.

Because our properties are private, we’ll add a single function to determine if a Tile would have a specific side, in any possible orientation:

// In Day20.Tile

private fun hasSide(side: String): Boolean =
    side in sides || side in sidesReversed

Rotation and Flipping

The puzzle description is clear that we will need to both rotate and flip our tiles. Therefore, we’re going to have to write some code to do that. But first, let’s talk about how we’ll do it.

When flipping or rotating, we have three options:

Keep the Tile references the same and work entirely in place, move individual cells within the body to their new place without defining a new body.
Keep the Tile references the same but when manipulating the body, create a new one and replace it.
Create a new Tile representing the new state whenever we manipulate it, and update references when a Tile changes.

I have decided to go with Option 2. Option 1 is the most space efficient. Option 3 is the most “functional”. But Option 2 allows us to alter a Tile as a side-effect, and not have to worry about keeping track of a new Tile instance. I’m also fine with the small performance hit required to create a new copy of body each time, because the code to do so is much easier to follow.

Therefore, let’s write flip() first, because it is the easiest of the two concepts:

// In Day20.Tile

private fun flip(): Tile {
    body = body.map { it.reversed().toCharArray() }.toTypedArray()
    return this
}

Two things to note. First, when we call reversed() on a CharArray, we actually get back a List<Char>, so we have to turn it back into a CharArray manually. Second, we’re returning this at the end, even though this function does not create a new instance. This is to ease the burden on the caller when rotating a specific instance.

And next, we’ll rotate:

// In Day20.Tile

private fun rotateClockwise(): Tile {
    body = body.mapIndexed { x, row ->
        row.mapIndexed { y, _ ->
            body[y][x]
        }.reversed().toCharArray()
    }.toTypedArray()
    return this
}

To rotate our body clockwise, we need to transpose the x and y axis, and then reverse every row. If we went with Option 1 above (mutate body in-place instead of making a new one), we would have a nice O(n) time and O(1) space implementation. And originally I wrote it that way and it worked fine. But the small performance boost for a one-time puzzle was not with the trade-off in complexity. Rotating in place requires a lot of moving values around, and it is just more complicated to write and explain.

With our new ability to flip and rotateClockwise, it might be nice to have a function that helps us perform those operations. We can define this series of transformations as a sequence, so we can keep asking for the next state and stop calculating it when we find it. Because our flip and rotateClockwise are mutating operations, this is a nice feature to have.

// In Day20.Tile

fun orientations(): Sequence<Tile> = sequence {
    repeat(2) {
        repeat(4) {
            yield(this@Tile.rotateClockwise())
        }
        this@Tile.flip()
    }
}

We set up two loops. The inner loop will rotate the Tile and yield it each time. If those four rotations don’t match what the caller is looking for, we flip the Tile and rotate through them again. This will go through all 8 possible orientations that a Tile can be in.

The last orientation-related function we need is one to make a tile face a specific way. Essentially: “Orient yourself so that this side faces this direction”. Because we have our nice orientations() sequence, we can loop through them and take the first one that has our intended orientation.

// In Day20.Title

private fun orientToSide(side: String, direction: Orientation) =
    orientations().first { it.sideFacing(direction) == side }

Finding the Corner

We talked before about only really caring if something is a corner piece or not. In order to determine if something is a corner, we need a way to ask a Tile how many of its edges it shares with a set of other Tile objects.

// In Day20.Tile

fun sharedSideCount(tiles: List<Tile>): Int =
    sides.sumOf { side ->
        tiles
            .filterNot { it.id == id }
            .count { tile -> tile.hasSide(side) }
    }

To start, we loop through each one of our sides and sum up how many other tiles have that same side. This calculation is why I broke out sides from sidesReversed, otherwise we would have an answer that is 2x higher than we want. The same goes for filtering our current tile out of the set of candidates. And as we’ve seen a few times this year so far, this is a nice combination of sumBy and count, a common pattern.

Another useful function we’ll need is one to determine if a specific side of a specific tile is shared with any other tile. We will use this when finding the corner and orienting it.

// In Day20.Tile 

fun isSideShared(dir: Orientation, tiles: List<Tile>): Boolean =
    tiles
        .filterNot { it.id == id }
        .any { tile -> tile.hasSide(sideFacing(dir)) }

Again, we need to be careful to remove the tile we are looking at from contention. After that we determine if any other tile has a side that looks like the side we have, according to its direction. This function answer the question: “Does any other tile exist that could match up with my East side?” (for every direction).

Now we have enough information to find a top corner to begin our puzzle image with!

// In Day20

private fun findTopCorner(): Tile =
    tiles
        .first { tile -> tile.sharedSideCount(tiles) == 2 }
        .orientations()
        .first {
            it.isSideShared(Orientation.South, tiles) && it.isSideShared(Orientation.East, tiles)
        }

First, we find some candidates - tiles that only have 2 shared edges. Since any corner will do, we’ll take the first one that we find. Next, we need to look at all of that tile’s possible orientations one by one until we find one that shares its South and East edge with some other tile.

Why? Because when we build our puzzle, we will be building it from the upper left (North West corner) to the lower right (South East corner).

Strictly speaking, because we can find corner pieces we have enough information to solve Part 1. We could just find the Tile objects that share two sides with the full set of tiles and use those as-is. But since we’ll need the full puzzle for Part 2, and we’re so close, we might as well continue on and complete the puzzle.

Creating the Final Image

We are so close to being able to put our pieces together into a final image! We need one more function in Tile to make finding tiles that fit next to a specific tile easier to manage.

// In Day20.Tile

fun findAndOrientNeighbor(mySide: Orientation, theirSide: Orientation, tiles: List<Tile>): Tile {
    val mySideValue = sideFacing(mySide)
    return tiles
        .filterNot { it.id == id }
        .first { it.hasSide(mySideValue) }
        .also { it.orientToSide(mySideValue, theirSide) }
}

This function will find a Tile that matches our given side and is oriented properly. Essentially a “Go find a tile that matches my eastern edge, and make sure that lines up in their western edge” kind of thing. We do this by finding candidate tiles that are not the tile we are calling this on, and taking the first tile we find in the set that even has the side we care about. Once we find that, we call orientToSide to rotate and flip the found tile into the proper orientation.

And now, we can build our image from the tiles!

// In Day20

private fun createImage(): List<List<Tile>> {
    val width = sqrt(tiles.count().toFloat()).toInt()
    var mostRecentTile: Tile = findTopCorner()
    var mostRecentRowHeader: Tile = mostRecentTile
    return (0 until width).map { row ->
        (0 until width).map { col ->
            when {
                row == 0 && col == 0 ->
                    mostRecentTile
                col == 0 -> {
                    mostRecentRowHeader =
                        mostRecentRowHeader.findAndOrientNeighbor(Orientation.South, Orientation.North, tiles)
                    mostRecentTile = mostRecentRowHeader
                    mostRecentRowHeader
                }
                else -> {
                    mostRecentTile =
                        mostRecentTile.findAndOrientNeighbor(Orientation.East, Orientation.West, tiles)
                    mostRecentTile
                }
            }
        }
    }
}

You know what? I’m not a huge fan of this function either. But it does the job, and I think we can live with it.

The first thing to note is that our puzzle input (thankfully) always declares a perfectly square image. So to figure out how wide and high our square is, we take the square root of the number of puzzle pieces. We have to jump through a couple of hoops because Kotlin (and Java) do not have a square root function that operates on integers, only floating point numbers. So to get the square root, we have to convert to a floating point, get the square root, and convert back to an integer.

Next, we’ll declare two state variables - mostRecentTile and mostRecentRowHeader. To understand why, we’ll need to discuss how this function works:

When we start, find the top left hand corner via findTopCorner().
Set up two loops so that we go through every row and column in our eventual image.
If we are looking at the very top left corner, use the corner we’ve found.
If we are at the start of a new row (col == 0), we need to look at the tile TO OUR NORTH, and find a tile that fits TO ITS SOUTH.
1. When we find that, we set mostRecentRowHeader to the tile we just found.
2. We also set mostRecentTile to the tile we just found.
3. We return the tile we just found, this is the start of a new row.
Otherwise, we are looking at a spot that is to the right of our mostRecentTile, so we:
1. Find a tile that lines up the EASTERN border of the mostRecentTile, and orient it so its WESTERN side matches.
2. Set the mostRecentTile to the tile we just found
3. Return the mostRecentTile

At the end of this, we will have a List<List<Tile>>, our image!

We can call this, setting it as a property in our Day20 class, and then we can find its corners to solve part 1!

// In Day 20

private val image: List<List<Tile>> = createImage()

fun solvePart1(): Long =
    image.first().first().id * 
    image.first().last().id *
    image.last().first().id * 
    image.last().last().id

To find the corners, we examine the image and take both the first and last tile from the first row, and the first and last tile from the last row. We multiply the ids from these Tiles and that’s our answer!

Star most definitely earned! Onward!

⭐ Day 20, Part 2

The puzzle text can be found here.

Believe it or not, we don’t actually have to write all that much code to solve Part 2, given all the work we’ve done to solve Part 1.

Think about our task - we need to combine all of our Tile objects into a single image now, and rotate and flip that image until we find the Sea Monster. But wait, we already HAVE an object that can rotate and flip - Tile!

So let’s combine all of our Tile objects into a single Tile object!

First, we’ll need a way for the Tile to help strip off the outer border (as mentioned in the puzzle instructions). Because of how we’ll build the final image, we don’t really want the whole body back (minus borders), we just want one single row.

// In Day20.Tile

fun insetRow(row: Int): String =
    body[row].drop(1).dropLast(1).joinToString("")

To get the “inset” for a given row in the body, we drop its first character, and take everything else except the final character, which we drop with dropLast. To return a String, we need to call joinToString.

Now we can combine all of our Tile objects into a single Tile object, minus all borders:

// In Day20

private fun imageToSingleTile(): Tile {
    val rowsPerTile = tiles.first().body.size
    val body = image.flatMap { row ->
        (1 until rowsPerTile - 1).map { y ->
            row.joinToString("") { it.insetRow(y) }.toCharArray()
        }
    }.toTypedArray()
    return Tile(0, body)
}

Remembering that image is a List<List<Tile>>, we want to loop over each List<Tile>, and then within that over each Tile row by row. We also have to account for the fact that for any given Tile, we do not want the first or last rows (because they are borders). Looping through rows of List<Tile> and then each row of each of those Tile objects, we join every insetRow together into a CharArray. At the end, we take this body and insert it into a new Tile. Since we don’t really care what id the tile has, it can be anything - pick something that means something to you or leave it at zero.

Finding the Sea Monster

In order to find the Sea Monster, let’s figure out what we have. We have a single Tile with the picture in a body field, which is essentially a grid. In order to find the Sea Monster, we want to examine every spot in our body to see if it and the surrounding spots represent a Sea Monster.

To do this, we’ll define a mask for the Sea Monster - a List<Point2D> of the offsets from a given point for our pattern. In this case it can be anything, but in practice we’ll only ever define a mask for the Sea Monster.

Once we have that mask, we can go through every x/y starting point in our body and see if the offsets that the mask represent are ALL the # character. IF they ARE, we’ve found a Sea Monster and we’ll mark those spots with a 0 (although you can pick anything that isn’t a #).

// In Day20.Tile

fun maskIfFound(mask: List<Point2D>): Boolean {
    var found = false
    val maxWidth = mask.maxByOrNull { it.y }!!.y
    val maxHeight = mask.maxByOrNull { it.x }!!.x
    (0..(body.size - maxHeight)).forEach { x ->
        (0..(body.size - maxWidth)).forEach { y ->
            val lookingAt = Point2D(x, y)
            val actualSpots = mask.map { it + lookingAt }
            if (actualSpots.all { body[it.x][it.y] == '#' }) {
                found = true
                actualSpots.forEach { body[it.x][it.y] = '0' }
            }
        }
    }
    return found
}

Things to note in here: first, we calculate the maxWidth and maxHeight of the mask so we don’t bother looking at points in the body that would make the mask run out of bounds. Second, we loop through every x and y combination as a starting point for the mask offsets, and turn them into actualSpots. We then test that all of those actualSpots are the # character. If they are, we paint them a different character, so we can exclude them from the count later.

If our function finds the mask we return true, otherwise we didn’t find it and we return false.

Finally Solving Part 2

We finally have enough code to solve Part 2!

// In Day20

fun solvePart2(): Int {
    val seaMonsterOffsets = listOf(
        Point2D(0, 18), Point2D(1, 0), Point2D(1, 5), Point2D(1, 6), Point2D(1, 11), Point2D(1, 12),
        Point2D(1, 17), Point2D(1, 18), Point2D(1, 19), Point2D(2, 1), Point2D(2, 4), Point2D(2, 7),
        Point2D(2, 10), Point2D(2, 13), Point2D(2, 16)
    )

    return imageToSingleTile()
        .orientations()
        .first { it.maskIfFound(seaMonsterOffsets) }
        .body
        .sumBy { row ->
            row.count { char -> char == '#' }
        }
}

We first define the seaMonsterOffsets as our mask. These will be used as we’ve described above. If you draw out each of those points on a piece of graph paper, they’ll look like a Sea Monster:

            1111111111 
  01234567890123456789
0                   # 
1 #    ##    ##    ### - Hi! I'm friendly, please don't be frightened!
2  #  #  #  #  #  #

To finally solve Part 2, we need to:

Convert all of the Tile objects that make up our image (from part 1) into a single Tile.
Go through each of the orientations of our single image
Take the first one that returns true from maskIfFound, indicating we have found and marked off our Sea Monster (!!)
Count up the number of # spots in our Tile body and return it for the answer.

Run this and… star earned!

I can’t tell you how relieved I am to finally be done with this puzzle. Having said that, I had a LOT of fun and spent almost my entire Sunday on both the solution and this writeup. So if any of this is unclear, please send me a note and I’ll try to clear things up.

See you tomorrow!

⭐ Day 20, Part 1

⭐ Day 20, Part 2

Further Reading