# Advent of Code 2020 - Day 20, in Kotlin - Jurassic Jigsaw

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 20: 'Jurassic Jigsaw'

Posted on

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:

1. Tiles that have TWO sides in common with other tiles on the grid are CORNER PIECES
2. Tiles that have THREE sides in common with other tiles on the grid are EDGE PIECES
3. 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:

2. 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:

1. 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`.
2. Keep the `Tile` references the same but when manipulating the `body`, create a new one and replace it.
3. 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()
return (0 until width).map { row ->
(0 until width).map { col ->
when {
row == 0 && col == 0 ->
mostRecentTile
col == 0 -> {
}
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:

1. When we start, find the top left hand corner via `findTopCorner()`.
2. Set up two loops so that we go through every `row` and `column` in our eventual image.
3. If we are looking at the very top left corner, use the corner we’ve found.
4. 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.
5. 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 `id`s from these `Tile`s 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

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()
.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:

1. Convert all of the `Tile` objects that make up our `image` (from part 1) into a single `Tile`.
2. Go through each of the `orientations` of our single image
3. Take the `first` one that returns `true` from `maskIfFound`, indicating we have found and marked off our Sea Monster (!!)
4. 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!