# Advent of Code: Year 2020, Day 20

Today was… not fun, to say the very least. It was a lot of tedium, and I am not super proud of my solution.

Today involved a lot of matrix operations. I attempted to use Raku’s Math::Matrix, but found the features to be lacking; I don’t know what I expected from a package that hasn’t had a release in 2+ years. Instead, this solution was written using NumPy, a package which I am familiar with, but is not in my day-to-day rotation, so I am sure there is a better solution than mine out there.

## The Problem

### Part 1

The messages from yesterday decode into a series of images that we need to reassemble back into a single image.

Each of our inputs comes with an ID and the image itself. Here is an example of nine tiles of input:

```
Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###
Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#..
Tile 1171:
####...##.
#..##.#..#
##.#..#.#.
.###.####.
..###.####
.##....##.
.#...####.
#.##.####.
####..#...
.....##...
Tile 1427:
###.##.#..
.#..#.##..
.#.##.#..#
#.#.#.##.#
....#...##
...##..##.
...#.#####
.#.####.#.
..#..###.#
..##.#..#.
Tile 1489:
##.#.#....
..##...#..
.##..##...
..#...#...
#####...#.
#..#.#.#.#
...#.#.#..
##.#...##.
..##.##.##
###.##.#..
Tile 2473:
#....####.
#..#.##...
#.##..#...
######.#.#
.#...#.#.#
.#########
.###.#..#.
########.#
##...##.#.
..###.#.#.
Tile 2971:
..#.#....#
#...###...
#.#.###...
##.##..#..
.#####..##
.#..####.#
#..#.#..#.
..####.###
..#.#.###.
...#.#.#.#
Tile 2729:
...#.#.#.#
####.#....
..#.#.....
....#..#.#
.##..##.#.
.#.####...
####.#.#..
##.####...
##..#.##..
#.##...##.
Tile 3079:
#.#.#####.
.#..######
..#.......
######....
####.#..#.
.#...#.##.
#.#####.##
..#.###...
..#.......
..#.###...
```

Unfortunately, it seems the camera was malfunctioning, so these images may be **flipped** or **rotated**. We can find the way these fit together by aligning the borders of adjacent tiles. Here are the above nine tiles flipped and rotated until they fit together:

```
#...##.#.. ..###..### #.#.#####.
..#.#..#.# ###...#.#. .#..######
.###....#. ..#....#.. ..#.......
###.##.##. .#.#.#..## ######....
.###.##### ##...#.### ####.#..#.
.##.#....# ##.##.###. .#...#.##.
#...###### ####.#...# #.#####.##
.....#..## #...##..#. ..#.###...
#.####...# ##..#..... ..#.......
#.##...##. ..##.#..#. ..#.###...
#.##...##. ..##.#..#. ..#.###...
##..#.##.. ..#..###.# ##.##....#
##.####... .#.####.#. ..#.###..#
####.#.#.. ...#.##### ###.#..###
.#.####... ...##..##. .######.##
.##..##.#. ....#...## #.#.#.#...
....#..#.# #.#.#.##.# #.###.###.
..#.#..... .#.##.#..# #.###.##..
####.#.... .#..#.##.. .######...
...#.#.#.# ###.##.#.. .##...####
...#.#.#.# ###.##.#.. .##...####
..#.#.###. ..##.##.## #..#.##..#
..####.### ##.#...##. .#.#..#.##
#..#.#..#. ...#.#.#.. .####.###.
.#..####.# #..#.#.#.# ####.###..
.#####..## #####...#. .##....##.
##.##..#.. ..#...#... .####...#.
#.#.###... .##..##... .####.##.#
#...###... ..##...#.. ...#..####
..#.#....# ##.#.#.... ...##.....
```

With the corresponding tile IDs being:

```
1951 2311 3079
2729 1427 2473
2971 1489 1171
```

To confirm we put the image together correctly, we need to multiply the IDs of the four corners. In this case we get:

```
1951 * 3079 * 2971 * 1171 = 20899048083289
```

What is the product of the four corners in our real input?

#### Solution

See below for explanation and any implementation-specific comments.

```
import sys
import numpy as np
def orientations(tile):
for rotation in range(4):
new_tile = np.rot90(tile, k=rotation)
yield new_tile # [1]
yield np.flip(new_tile, 1)
if __name__ == '__main__':
tiles = {}
for block in open(sys.argv[1]).read().split('\n\n'):
lines = block.splitlines()
tile_id = int(lines[0].split(' ')[1][:-1])
tile = np.array([list(line) for line in lines[1:]]) == '#' # [2]
tiles[tile_id] = tile
grid_width = int(np.sqrt(len(tiles)))
combined_tiles = []
found_all_matches = False
for start_tile_id in tiles.keys():
for start_tile in orientations(tiles[start_tile_id]):
combined_tiles = [(start_tile_id, start_tile)]
used = {start_tile_id} # [3]
found_all_matches = True
for i in range(1, len(tiles)):
found_match = False
for tile_num, tile in tiles.items():
if tile_num in used:
continue
previous_horizontal = combined_tiles[i - 1][1] if i % grid_width != 0 else None
previous_vertical = combined_tiles[i - grid_width][1] if i // grid_width != 0 else None
for try_tile in orientations(tile):
if previous_horizontal is not None and not np.all(previous_horizontal[:, -1] == try_tile[:, 0]):
continue
if previous_vertical is not None and not np.all(previous_vertical[-1, :] == try_tile[0, :]):
continue
combined_tiles.append((tile_num, try_tile))
used.add(tile_num)
found_match = True
break
if not found_match:
found_all_matches = False
break
if found_all_matches:
break
if found_all_matches:
break
tile_ids = np.array([entry[0] for entry in combined_tiles]).reshape((grid_width, grid_width)) # [4]
corner_product = tile_ids[0, 0] * tile_ids[0, -1] * tile_ids[-1, 0] * tile_ids[-1, -1]
print(corner_product)
```

This runs as such:

```
$ python day20.py input.txt
23497974998093
```

#### Explanation

First things first, you can see this is an absolute travesty from a time complexity standpoint. I count 5 nested for-loops, making this *O(n ^{5})*, which falls squarely in the horrible category. Regardless, it runs in under five seconds, so it’s not a huge deal. Just wanted to acknowledge that I

*know*it is bad.

The logic for this mess is as follows:

- First, parse the input into a dictionary with the ID as the key, and a 2D NumPy array as the value
- We translate
`.`

and`#`

to`True`

and`False`

on the way in

- We translate
- We start with a random tile and iterate through it’s orientations
- 3 rotations (plus the un-rotated version) as well as one flip for each rotation
- For each rotation we look for the possible matches on all four edges
- When we find one that fits, we store it in
`combined_tiles`

and keep looking - When we run into one that doesn’t fit, we start the whole process over

- Once we have put all the pieces in their place, we extract
*just*the tile IDs into a grid (like in the example) and multiply the corners.

If it’s stupid, but it works, it ain’t stupid 🤷🏻♂️

##### Specific Comments

- For anyone not familiar with the
`yield`

keyword, it is what’s known as a`generator`

in Python (a lazy list in Raku). Basically, this iterable is only evaluated*when it is asked for*, so all that is stored in memory is how to generate the next term, not anything else. Additionally, generators return to the function*exactly*where they left off. So after yielding`new_tile`

the next term will be the flipped version of`new_tile`

. Here is a link for further reading. - NumPy is interesting, so when you have an array compared to a value, it compares each value in the array to that value, and puts it into a new array. This is our way of converting to
`True`

and`False`

values. -
This defines a

`set`

with a single item,*not*a dictionary. Python can be a little confusing on that front:`x = {} # empty dict x = {'foo': 'bar'} # dict with 1 item x = set() # empty set x = {'foo'} # set with 1 item x = set(['foo']) # also a set with 1 item (`set()` takes an iterable)`

`reshape`

allows us to convert a list of lists back into an`n x n`

matrix.

### Part 2

After putting the image together, we find that it is a picture of the ocean, and it is full of **sea monsters**. First things first, lets take of the borders used to align the pieces. The above example becomes this:

```
.#.#..#. ##...#.# #..#####
###....# .#....#. .#......
##.##.## #.#.#..# #####...
###.#### #...#.## ###.#..#
##.#.... #.##.### #...#.##
...##### ###.#... .#####.#
....#..# ...##..# .#.###..
.####... #..#.... .#......
#..#.##. .#..###. #.##....
#.####.. #.####.# .#.###..
###.#.#. ..#.#### ##.#..##
#.####.. ..##..## ######.#
##..##.# ...#...# .#.#.#..
...#..#. .#.#.##. .###.###
.#.#.... #.##.#.. .###.##.
###.#... #..#.##. ######..
.#.#.### .##.##.# ..#.##..
.####.## #.#...## #.#..#.#
..#.#..# ..#.#.#. ####.###
#..####. ..#.#.#. ###.###.
#####..# ####...# ##....##
#.##..#. .#...#.. ####...#
.#.###.. ##..##.. ####.##.
...###.. .##...#. ..#..###
```

And then we can remove the gaps to be left with a full grid:

```
.#.#..#.##...#.##..#####
###....#.#....#..#......
##.##.###.#.#..######...
###.#####...#.#####.#..#
##.#....#.##.####...#.##
...########.#....#####.#
....#..#...##..#.#.###..
.####...#..#.....#......
#..#.##..#..###.#.##....
#.####..#.####.#.#.###..
###.#.#...#.######.#..##
#.####....##..########.#
##..##.#...#...#.#.#.#..
...#..#..#.#.##..###.###
.#.#....#.##.#...###.##.
###.#...#..#.##.######..
.#.#.###.##.##.#..#.##..
.####.###.#...###.#..#.#
..#.#..#..#.#.#.####.###
#..####...#.#.#.###.###.
#####..#####...###....##
#.##..#..#...#..####...#
.#.###..##..##..####.##.
...###...##...#...#..###
```

We need to find the sea monsters in the above image. They look like this:

```
#
# ## ## ###
# # # # # #
```

When looking for a sea monster, the spaces can be either `#`

or `.`

, as long as those specific `#`

symbols match. After rotating and flipping the grid, we find two sea monsters (marked as `O`

characters):

```
.####...#####..#...###..
#####..#..#.#.####..#.#.
.#.#...#.###...#.##.O#..
#.O.##.OO#.#.OO.##.OOO##
..#O.#O#.O##O..O.#O##.##
...#.#..##.##...#..#..##
#.##.#..#.#..#..##.#.#..
.###.##.....#...###.#...
#.####.#.#....##.#..#.#.
##...#..#....#..#...####
..#.##...###..#.#####..#
....#.##.#.#####....#...
..##.##.###.....#.##..#.
#...#...###..####....##.
.#.##...#.##.#.#.###...#
#.###.#..####...##..#...
#.###...#.##...#.##O###.
.O##.#OO.###OO##..OOO##.
..O#.O..O..O.#O##O##.###
#.#..##.########..#..##.
#.#####..#.#...##..#....
#....##..#.#########..##
#...#.....#..##...###.##
#..###....##.#...##.##.#
```

After identifying the sea monsters, we can calculate how rough the water is by counting the number of remaining `#`

characters. In the above example it is `273`

; what is the water roughness in our actual input?

#### Solution

See below for explanation and any implementation-specific comments.

```
import sys
import numpy as np
def orientations(matrix):
for rotation in range(4):
new_matrix = np.rot90(matrix, k=rotation)
yield new_matrix
yield np.flip(new_matrix, 1)
if __name__ == '__main__':
tiles = {}
for block in open(sys.argv[1]).read().split('\n\n'):
lines = block.splitlines()
tile_id = int(lines[0].split(' ')[1][:-1])
tile = np.array([list(line) for line in lines[1:]]) == '#'
tiles[tile_id] = tile
grid_width = int(np.sqrt(len(tiles)))
combined_tiles = []
found_all_matches = False
for start_tile_id in tiles.keys():
for start_tile in orientations(tiles[start_tile_id]):
combined_tiles = [(start_tile_id, start_tile)]
used = {start_tile_id}
found_all_matches = True
for i in range(1, len(tiles)):
found_match = False
for tile_num, tile in tiles.items():
if tile_num in used:
continue
previous_horizontal = combined_tiles[i - 1][1] if i % grid_width != 0 else None
previous_vertical = combined_tiles[i - grid_width][1] if i // grid_width != 0 else None
for try_tile in orientations(tile):
if previous_horizontal is not None and not np.all(previous_horizontal[:, -1] == try_tile[:, 0]):
continue
if previous_vertical is not None and not np.all(previous_vertical[-1, :] == try_tile[0, :]):
continue
combined_tiles.append((tile_num, try_tile))
used.add(tile_num)
found_match = True
break
if not found_match:
found_all_matches = False
break
if found_all_matches:
break
if found_all_matches:
break
final_grid_ids = np.array([entry[0] for entry in combined_tiles]).reshape((grid_width, grid_width))
corner_product = final_grid_ids[0, 0] * final_grid_ids[0, -1] * final_grid_ids[-1, 0] * final_grid_ids[-1, -1]
print(f'Part 1: {corner_product}')
tile_width = combined_tiles[0][1].shape[0] - 2 # Remove borders on each side
grid = np.zeros((tile_width * grid_width, tile_width * grid_width), dtype=bool)
for index, (_, tile) in enumerate(combined_tiles):
row, column = divmod(index, grid_width)
grid[
row * tile_width:row * tile_width + tile_width,
column * tile_width:column * tile_width + tile_width
] = tile[1:-1, 1:-1]
monster = (
' # ',
'# ## ## ###',
' # # # # # # '
)
monster = np.array([list(line) for line in monster]) == '#'
water_roughness = None
for orientation in orientations(grid):
num_monsters = 0
for i in range(grid.shape[0] - monster.shape[0] + 1):
for j in range(grid.shape[1] - monster.shape[1] + 1):
grid_slice = orientation[i:i + monster.shape[0], j:j + monster.shape[1]]
if np.all((grid_slice & monster) == monster):
num_monsters += 1
if num_monsters > 0:
water_roughness = np.sum(grid) - num_monsters * np.sum(monster)
break
print(f'Part 2: {water_roughness}')
```

This runs as such:

```
$ python day20.py input.txt
Part 1: 20899048083289
Part 2: 2256
```

#### Explanation

Immediately where part one left off we apply the following logic:

- First remove the border from each tile we just aligned
- Start with an empty grid (
`np.zeroes`

) and build it up tile-by-tile so that we have an outer matrix full of smaller matrices - Define our monster as a NumPy matrix
- Again, iterate through possible orientations (grid orientations this time) and generate slices the size of a monster
- Check if the slice
*is*a monster - If we found a monster, we must be in the right orientation
- To find the water roughness we
`sum`

the whole grid (which will just count the`True`

values), then subtract the number of those`True`

values that are in a monster`num_monsters - np.sum(monster)`

## Final Thoughts

According to the creator of Advent of Code, weekend puzzles are intentionally harder because that is when people have time to do them. With that in mind, I am hoping the rest of the puzzles are easier than today! If I can’t have that, then I at least hope they are less tedious. 🙂 Just five more days!