Advent of Code 2020 - Day 20

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

For this problem we get a set of tiles, each a (potentially rotated and/or flipped) fragment of a global image. Each tile is 10x10 with the inner 8x8 actually the image data, while the outer edges are there just to indicate matching of two tiles: to form the global image, the edges of adjacent tiles must match; that means applying different flipping and rotation to each tile to build a coherent whole.

Part 1

For this part we need to identify the corner tiles. We don't need to rebuild the whole image, just find the tiles with edges matching other tiles on two edges. Since we will need to do that for part 2, we will start to create a Tile class, that we will extend later; but if we were just concerned about this part, we wouldn't need this level of complexity.

We will initialize the tiles from the input, with the tile ID and the ten, ten-char lines. We need to keep the ID, keep the inner 8x8 part as the tile itself, and the boundaries. We need to establish a convention for storing the edges, to make sure that we are matching them in the right way (not really important at this stage, but unavoidable when rotating and flipping tiles to build the whole thing). We will store the edges in clockwise order starting at the top, horizontal edges left-to-right and vertical ones top-to-bottom. These directions need to be absolute like this; if we choose relative directions, such as clockwise, the bottom edge of one tile and the top edge of the tile below (for instance) would be stored in opposite directions, and would not match.

We will further consider all edges inverted as potential boundaries, to account for potential flips and rotations. With this, we can pair-wise compare the tiles and look for adjacency, which happens if the intersection of one tiles edges and the potential edges of the other one is non-empty. We use this condition to build an adjacency matrix using a dictionary with each tile ID as key and the set of compatible tiles as value. With this matrix, we just need to take the IDs of the tiles with degree 2 (i.e. the set of compatible tiles has two elements).

Part 2

For the second part we need to find sea monsters in the image, which means we need to assemble the whole image first. We will add some functionality to the tiles to help in this. First, the ability to rotate and flip themselves; these are quite straightforward, but we must take care to properly apply the operation to the edges. Next we will use the adjacency matrix to give each tile links to the tiles it matches with, so it has a direct way to refer to its neighbours.

We will build the image one row at a time. We choose any corner as the top left. The choice is irrelevant; the result of each choice can be converted in one of the others by rotating and/or flipping the image.

We will use the match function to apply the necessary operations to a tile until its top and left match the given tiles, using None for borders. This is as easy as rotating the tile until the top matches its target. If the left does not march like that, a horizontal flip must do the trick.

We match the right position of the initial corner. Then we can fill in the first row; we know the next tile is the right-neighbour of the previous one, and we match it to None and the previous tile.

Next we fill in subsequent rows, each starting with the bottom-neighbour of the first tile in the previous row, matched to that tile and None, and continuing matching to the corresponding tile in the previous row and the previous tile in the current row.

Once we are done, we stitch everything together into a single image.

Now for the monsters. We will define a monster by the positions of '#' characters with respect to the top left position in the 'window' that contains the monster, as well as the window's width and height.

To find the monsters we slide the window over the image, convolution-like, and at each position we check if all the monster positions contain a '#' in the image. If so, we mark those positions.

Since the image may be flipped or rotated we try all combinations until we find one with monsters.

Once we have that, we get the positions of all the '#' characters in the image. The answer to the problem is the size of the difference of the two sets. The difference of the sizes will not work, as there may be overlaps in the monsters.