https://adventofcode.com/2020/day/20 ('Jurassic Jigsaw')
Day 20 was the problem that required the most work this year. While there was nothing really conceptually hard involved, it was fiddly and I made lots of mistakes on the way that took time to track down. After finishing I felt like I'd just done a 3 and a half hour exam!
Part 1
A quick look at the puzzle input showed that there were 144 tiles, all 10 by 10 in size, and each tile had a 4-digit ID. It seemed most natural to represent the tile data as a dictionary mapping tile ID to an array of 10 10-character strings, one string per line in the tile. As a result, parsing the input was straightforward:
def read_input():
tiles = {}
with open('day20.txt') as input_file:
tile_id = None
current_tile = []
for line in input_file.read().splitlines():
if line.startswith('Tile'):
if current_tile:
tiles[tile_id] = current_tile
current_tile = []
tile_id = int(line[5:9])
elif line.startswith(('.', '#')):
current_tile.append(line)
if current_tile:
tiles[tile_id] = current_tile
current_tile = []
return tiles
Part 1 says:
Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?
This is a bit sneaky as we don't actually need to assemble the tiles into an image (yet). If we can find tiles that have two adjacent edges that don't match up with any other tiles then they must be the corner tiles.
To do this we need a way of labelling individual tile edges. I arbitrarily chose to number the edges clockwise from the top of the tile in the orientation it was presented in the puzzle input:
0
+---+
| |
3 | | 1
| |
+---+
2
Each edge therefore has a unique ID: a tuple of (tile_id, edge_no). We can now pull out a dictionary mapping edge ID to a string representing the edge itself:
def get_tile_edges(tiles):
'Return a dictionary mapping (tile_id, edge_no) to strings for each tile edge'
edges = {}
for (tile_id, tile) in tiles.items():
edges[(tile_id, 0)] = tile[0] # top
edges[(tile_id, 1)] = ''.join(row[-1] for row in tile) # right
edges[(tile_id, 2)] = tile[-1] # bottom
edges[(tile_id, 3)] = ''.join(row[0] for row in tile) # left
return edges
To find the corners we must see which edges match up with each other, with the possibility of needing to flip tiles to find a match. It is also not clear at this stage whether there might be multiple matches (I hoped not as I suspected part 2 would actually require assembling the whole image and this would be much harder if there were multiple possibilities!) Let's work on the assumption that each edge will match either exactly one other edge (allowing for flipping) or no edges at all - in which case it must lie on the outside of the completed image.
To find matching edges we can cycle through each of the 576 edges. For each edge we can look at the other 575 edges and see if they either have the same string or if reversing one makes them equal - and if so we have a match. The result is a dictionary mapping each edge to the edge it matches with or to None if there was no match.
def find_matching_edges(tiles):
'''Return a dictionary mapping each (tile_id, edge_no) to
the (tile_id, edge_no) it matches with, or None if that
edge must lie on the outside edge of the resulting grid'''
edge_strings = get_tile_edges(tiles)
matches = {}
for (edge, edge_string) in edge_strings.items():
if edge in matches:
continue
found = False
for (other_edge, other_edge_string) in edge_strings.items():
if edge[0] == other_edge[0]:
continue
if edge_string == other_edge_string or edge_string == other_edge_string[::-1]:
if edge in matches:
raise Exception(f'Multiple matches for {edge}')
found = True
matches[edge] = other_edge
matches[other_edge] = edge
if not found:
matches[edge] = None
return matches
Note that we have taken advantage of the fact that if (tile_1, edge_1) matches (tile_2, edge_2) then we also know that (tile_2, edge_2) matches (tile_1, edge_1) and the number of checks required is halved.
The code will also bail out if the assumption of unique matches is broken - but luckily it turns out that running it on the puzzle input doesn't result in the exception being thrown so it looks like this assumption is safe! The above code doesn't however check for weird situations like a tile edge only matching another edge on the same tile, but fortunately the puzzle wasn't quite this cruel.
Now we have the dictionary of matching edges, identifying the corners is straightforward:
from functools import reduce
from operator import mul
def part1():
tiles = read_input()
# Look for edges that match up
matches = find_matching_edges(tiles)
# Find edges that must be on the corners by seeing if the
# edge is on the outside and then checking that the edge
# clockwise adjacent to it is also on the outside. The
# tiles owning such edges will be the corner tiles.
corner_tiles = set(edge[0] for (edge, other_edge) in matches.items()
if other_edge is None and matches[(edge[0], (edge[1] + 1) % 4)] is None)
return reduce(mul, corner_tiles)
Part 2
I did have a think about whether it might be possible to avoid assembling the whole image by looking for parts of a sea monster in each tile. I decided that this was probably an even more complicated rabbit hole to disappear down, and it actually made sense to bite the bullet and stitch together the whole image.
First are three functions it turned out to be useful to define as they represent operations that came up frequently. Given that we're labelling edges as a tuple of (tile ID, edge number), these functions each return a tuple representing a different edge on the same tile:
def cw(edge):
'Return the next edge clockwise on the same tile'
return (edge[0], (edge[1] + 1) % 4)
def acw(edge):
'Return the next edge anticlockwise on the same tile'
return (edge[0], (edge[1] + 3) % 4)
def opp(edge):
'Return the edge opposite the given edge on the same tile'
return (edge[0], (edge[1] + 2) % 4)
As there are 144 tiles and the puzzle's preamble implies that the resulting image is square, we can assume that we'll need a 12 x 12 grid of tiles to form the image.
Representing the Grid
The first question is: how should we model the grid of tiles? We need to allow for tiles being flipped or rotated, so for each grid position we could store the tile ID at that position and some value that indicates how the tile has been transformed. In the end it seemed simplest just to maintain a dictionary mapping grid position to a tuple of tile ID and the edge numbers of the tile's edges that are in the top, right, bottom and left positions once the tile has been oriented correctly.
For example, if tile 1000 needed to be flipped on its vertical axis then rotated clockwise in order to fit at grid position (3, 4) we would have the following entry in the dictionary:
(3, 4): (1000, 1, 0, 3, 2)
This is because flipping the tile then rotating it looks like this:
0 0 1
+---+ +---+ +---+
| | | | | |
3 | | 1 ----> 1 | | 3 ----> 2 | | 0
| | | | | |
+---+ +---+ +---+
2 2 3
As a result edge 1 is in the top position, edge 0 on the right, edge 3 on the bottom and edge 2 on the left. Storing the tiles this way keeps an unambiguous record of their final orientation, and has the advantage that when we're trying to find tiles that fit in adjacent slots it's easy to see which edges they need to match up with. (In fact, an unambiguous record of the tile's orientation only requires us to record where two adjacent sides end up, but recording all four saves us from having to repeatedly work out where the other two ended up).
Populating the Grid
Now we've decided how to represent the grid of tiles, how should we populate it? If we start from the top-left corner (call this (0, 0)) and work across each row in turn down to the bottom right corner ((11, 11)) then each time we're populating a grid square we'll be in one of the following situations:
- There's no grid square to the left or above the current tile - i.e. we're looking at the top-left corner. As we did in part 1, we can pick a corner tile by looking for any tile that has two adjacent outside edges and orienting it so one is on the left and the other is at the top.
- There's a grid square to the left but no grid square above - i.e. we're looking at a tile in the top row. Here we can determine which tile to use by looking at the right edge of the tile to the left, but we need to determine the tile's orientation by making sure the outside edge is at the top.
- There's a grid square above but not to the left - i.e. we're looking at a tile in the leftmost column. As for situation 2, we can use the bottom edge of the tile above to find the correct tile and then orient it using by putting the outside edge on the left.
- There are grid squares both to the left and above - i.e. we're looking at any other tile. We have both the right edge of the tile to the left and the bottom edge of the tile above to determine the tile to use and its orientation.
Having determined which tile we're using and which of its edges are going in the left and top positions of its grid square, we can simply use the opp() function defined above to get the right and bottom edges - which are important as they'll be needed to find the tiles to the right and below.
The whole process looks ike:
GRID_SIZE = 12
def generate_grid(matches):
# Grid is a map from (x, y) to (tile, top_edge_no, right_edge_no, bottom_edge_no, left_edge_no)
grid = {}
for row in range(0, GRID_SIZE):
for column in range(0, GRID_SIZE):
# Determine which edges should go to the left and
# top of this grid square.
left_edge = None
top_edge = None
if column == 0 and row == 0:
# We're at the top left of the grid. Find a
# corner piece by looking for a tile with
# two adjacent outside edges.
for (left_edge, matching_edge) in matches.items():
top_edge = cw(left_edge)
if matching_edge is None and matches[top_edge] is None:
break
else:
raise Exception('Could not find a corner piece for the top left corner.')
else:
if column > 0:
# Use the right edge of the tile to the left
# to determine the left edge of this tile.
(left_tile_id, _, left_tile_right_edge_no, _, _) = grid[(column - 1, row)]
left_edge = matches[(left_tile_id, left_tile_right_edge_no)]
if row == 0:
# We're on the top row. Any outside edge
# next to the left edge must be the top
# edge.
top_edge = find_adjacent_outside_edge(left_edge, matches)
if row > 0:
# Use the bottom edge of the tile above to
# determine the top edge of this tile.
(above_tile_id, _, _, above_tile_bottom_edge_no, _) = grid[(column, row - 1)]
top_edge = matches[(above_tile_id, above_tile_bottom_edge_no)]
if column == 0:
# We're on the leftmost column. Any
# outside edge next to the top edge
# must be the left edge.
left_edge = find_adjacent_outside_edge(top_edge, matches)
else:
# We're in the middle of the grid.
# Check the both edges belong to the
# same tile.
if left_edge[0] != top_edge[0]:
raise Exception(
f'Inconsistency at {(column, row)}: right edge of tile to the left matches {left_edge[0]}.{left_edge[1]} but bottom edge of tile above matches {top_edge[0]}.{top_edge[1]}')
# If we have the left and top edges we know the
# right and bottom edges.
right_edge = opp(left_edge)
bottom_edge = opp(top_edge)
grid[(column, row)] = (left_edge[0], top_edge[1], right_edge[1], bottom_edge[1], left_edge[1])
return grid
The above uses the following function when looking for outside edges on tiles in the top row or leftmost column:
def find_adjacent_outside_edge(edge, matches):
'Look for an outside edge adjacent to the given edge on the same tile.'
clockwise_edge = cw(edge)
if matches[clockwise_edge] is None:
return clockwise_edge
anticlockwise_edge = acw(edge)
if matches[anticlockwise_edge] is None:
return anticlockwise_edge
raise Exception(f'Expected an outside edge adjacent to edge {edge[0]}.{edge[1]}.')
Building the Image
Now we know which tiles are in which position on the grid we need to stitch together the complete image. The plan is to work from the top left again and:
- Trim each tile to remove the outer edges (these are not part of the actual image data according to the puzzle text)
- Using the data from the
griddictionary we just populated, flip and rotate the tile's image data until it has the right orientation. - Add the data to a giant tile that represents the whole image.
Trimming a tile is simple enough:
def trim_tile(tile):
'Remove the outer edges of the tile'
return [row[1:-1] for row in tile[1:-1]]
It's the second step here that's the trickiest. The grid dictionary will tell us which edges of a tile are in which positions. We need a way of taking an entry like (1000, 1, 0, 3, 2) (our example from before) and figuring out that this means we need to flip the tile data about its vertical axis and then rotate it clockwise.
There are actually only 8 possibilities here as we're talking about the group of symmetries of a square (this is the group D4, the dihedral group of order 8). As a result I didn't do anything clever - instead I just worked through all 8 and applied the appropriate transformation for each. This only requires looking at the edge numbers that are in the left and top positions, so if as in our example we see 2 in the left position and 1 in the top position we know we need to flip about the vertical axis and then rotate clockwise.
To perform the transformation of the tile we need functions that can manipulate the tile data to produce a flipped or rotated tile. It turns out that all symmetry transformations of a square can be generated by various combinations of flipping about the vertical axis and rotating one or more times by 90° clockwise (i.e. these transformations are generators of the symmetry group D4). These functions look like:
def flip_v(tile):
'Flip around vertical axis'
return [row[::-1] for row in tile]
def rotate_90(tile):
'Rotate by 90 degrees clockwise'
new_tile = []
size = len(tile)
for row in range(size):
s = []
for column in range(size):
s.append(tile[size - 1 - column][row])
new_tile.append(''.join(s))
return new_tile
To see these in action, suppose we have a 3 by 3 tile like:
a b c
d e f
g h i
Rotating this tile clockwise should produce:
g d a
h e b
i f c
On the other hand, flipping it about its vertical axis should produce:
c b a
f e d
i h g
To check:
>>> tile = ['abc', 'def', ghi']
>>> rotate_90(tile)
['gda', 'heb', 'ifc']
>>> flip_v(tile)
['cba', 'fed', 'ihg']
so it looks like these functions work as expected.
Now we can work through the 8 possible distinct combinations of these transformations and write down which edge number ends up on the left side and which at the top (assuming we start with our standard edge numbering of 0 at the top, 1 on the right, 2 at the bottom and 3 on the left). Here's one way the two transformations flip_v and rotate_90 can be used to generate all the others:
0 3 2 1
+---+ +---+ +---+ +---+
| | | | | | | |
3 | | 1 ----> 2 | | 0 ----> 1 | | 3 ----> 0 | | 2
| | rotate_90 | | rotate_90 | | rotate_90 | |
+---+ +---+ +---+ +---+
2 1 0 3
|
| flip_v
v
0 1 2 3
+---+ +---+ +---+ +---+
| | | | | | | |
1 | | 3 ----> 2 | | 0 ----> 3 | | 1 ----> 0 | | 2
| | rotate_90 | | rotate_90 | | rotate_90 | |
+---+ +---+ +---+ +---+
2 3 0 1
This gives the following table:
| Transformation | Left edge | Top edge |
|---|---|---|
| Nothing | 3 | 0 |
rotate_90(tile) |
2 | 3 |
rotate_90(rotate_90(tile)) |
1 | 2 |
rotate_90(rotate_90(rotate_90(tile))) |
0 | 1 |
flip_v(tile) |
1 | 0 |
rotate_90(flip_v(tile)) |
2 | 1 |
rotate_90(rotate_90(flip_v(tile))) |
3 | 2 |
rotate_90(rotate_90(rotate_90(flip_v(tile)))) |
0 | 3 |
All the code needs to do is see which left edge/top edge combination we have and apply the appropriate transformation:
def adjust_tile(tile, left_edge, top_edge):
'''Given the edge numbers that should be on the left and at
the top, perform any necessary transformations to re-orient
the tile'''
if left_edge == 3 and top_edge == 0:
return tile
if left_edge == 2 and top_edge == 3:
return rotate_90(tile)
if left_edge == 1 and top_edge == 2:
return rotate_90(rotate_90(tile))
if left_edge == 0 and top_edge == 1:
return rotate_90(rotate_90(rotate_90(tile)))
if left_edge == 1 and top_edge == 0:
return flip_v(tile)
if left_edge == 2 and top_edge == 1:
return rotate_90(flip_v(tile))
if left_edge == 3 and top_edge == 2:
return rotate_90(rotate_90(flip_v(tile)))
if left_edge == 0 and top_edge == 3:
return rotate_90(rotate_90(rotate_90(flip_v(tile))))
raise Exception(f'Invalid combination of left and top edges: {left_edge}, {top_edge}')
Now we have all the pieces we need to put the image together!
TILE_SIZE = 10
def create_image(grid, tiles):
'''Given the grid information and the tiles, stitch the
tiles together into an image'''
image = []
for row in range(0, GRID_SIZE):
# We're stripping the outer edges from each tile, so
# only need space for TILE_SIZE - 2 image rows per
# grid row.
for _ in range(TILE_SIZE - 2):
image.append('')
for column in range(0, GRID_SIZE):
(tile_id, top_edge, _, _, left_edge) = grid[(column, row)]
tile = tiles[tile_id]
tile = adjust_tile(tile, left_edge, top_edge)
tile = trim_tile(tile)
for (i, tile_row) in enumerate(tile):
image_row = row * (TILE_SIZE - 2) + i
image[image_row] += tile_row
return image
Finding Sea Monsters
But we're still not there! This really is a marathon question. We need to find the total number of hashes in the finished image that aren't part of a sea monster. A sea monster is defined as:
#
# ## ## ###
# # # # # #
so contains 15 hashes. Therefore the answer to part 2 will be the total number of hashes in the image minus 15 times the number of sea monsters.
First let's find the total number of hashes, assuming image is the output of the create_image() function defined above:
hashes = sum(sum(1 for c in row if c == '#') for row in image)
Now we need to count the number of sea monsters. The puzzle wording isn't completely clear, but I took it to mean that only one orientation of the image would yield any sea monsters at all - all other orientations would have none. We have a choice here: we can either reorient the entire image and look for the untransformed sea monster, or reorient the sea monster and look for it in an untransformed image. Given that we already have functions to transform arbitrarily-sized tiles and the image is just a big tile, it seems easiest to reorient the image until we find the orientation that yields some sea monsters.
However, before we worry about finding the right image orientation we need to be able to detect a sea monster! The requirement for a sea monster is only that the hashes defined above are present - there could be extra hashes, and even the following would still count as a sea monster:
####################
####################
####################
The way to go seems to be to examine every 20 x 3 block of characters in the image and check just the characters that are required in the sea monster to see if they're hashes. To do this we can define the offsets at which we expect to find hashes, along with the width and height of a sea monster:
# These are the offsets that describe a sea monster shape
#
# 00000000001111111111
# 01234567890123456789
# 0 #
# 1 # ## ## ###
# 2 # # # # # #
MONSTER_OFFSETS = [
(18, 0),
(0, 1), (5, 1), (6, 1), (11, 1), (12, 1), (17, 1), (18, 1), (19, 1),
(1, 2), (4, 2), (7, 2), (10, 2), (13, 2), (16, 2)
]
MONSTER_WIDTH = 20
MONSTER_HEIGHT = 3
so checking for a monster at (x, y) in the image looks like:
def has_monster(image, x, y):
'Return True if a sea monster can be found at (x, y) in the image'
if y > len(image) - MONSTER_HEIGHT:
return False
if x > len(image[0]) - MONSTER_WIDTH:
return False
for offset in MONSTER_OFFSETS:
sx = x + offset[0]
sy = y + offset[1]
if image[sy][sx] != '#':
return False
return True
and counting all the sea monsters is just repeated application of the above:
def count_monsters(image):
'Return the total number of sea monsters in the image'
count = 0
for x in range(len(image[0]) - MONSTER_WIDTH):
for y in range(len(image) - MONSTER_HEIGHT):
if has_monster(image, x, y):
count += 1
return count
However as mentioned above, we also need to allow for reorienting the image! We already know how to generate all the possible symmetry transformations for a square, so we can just walk through them one at a time:
def reoriented_images(image):
'Work through the 8 possible ways the image could be flipped and rotated'
yield image
yield rotate_90(image)
yield rotate_90(rotate_90(image))
yield rotate_90(rotate_90(rotate_90(image)))
yield flip_v(image)
yield rotate_90(flip_v(image))
yield rotate_90(rotate_90(flip_v(image)))
yield rotate_90(rotate_90(rotate_90(flip_v(image))))
Putting it All Together
We're on the home straight and the finish line is in sight! Using all the work done above we can actually solve part 2:
def part2():
tiles = read_input()
# Match up the tile edges
matches = find_matching_edges(tiles)
# Now build a grid of all the tiles, flipping and rotating as necessary
grid = generate_grid(matches)
# Gather all tiles together into one image
image = create_image(grid, tiles)
# Get the total number of hashes in the image
hashes = sum(sum(1 for c in row if c == '#') for row in image)
# Look for sea monsters
# The assumption here (based on the puzzle wording) is that
# sea monsters only appear in one orientation of the image,
# so we just need to keep reorienting the image until we
# find a non-zero number of monsters.
for reoriented_image in reoriented_images(image):
monsters = count_monsters(reoriented_image)
if monsters > 0:
# Return the number of hashes that aren't in a sea monster
return hashes - monsters * len(MONSTER_OFFSETS)
Phew!
I would be interested to know of any shortcuts to all the above - this required much more code than any of the other days this year, so I was left with the nagging feeling I'd missed a clever trick!
Top comments (0)