Day 20. Jurassic Jigsaw
Problem statement
https://adventofcode.com/2020/day/20 (mirror)My solution
This is the longest solution in whole Advent of Code 2020. While each particular step is not very hard to understand on its own, there are multiple small places where unnotices bugs may creep up.
Case in point: I lost a couple hours before I noticed a typo in method GetOrientedBit. A typo for a single orientation meant that the simple test case from description was passing (because that orientation was never encountered), but the for actual input the program was not producing the correct answer.
JigsawPiece class
First of all, let’s describe JigsawPiece class that is the main building block of my solution.
Each JigsawPiece object will obviously correspond to a single tile from input data, for example:
Tile 1321:
.....#.##.
....##.###
#..##.....
.........#
#.#...#...
##..#....#
#..#.#....
......#.##
...#......
.###.#####
Class JigsawPiece will have the following properties:
int ContentSize: each tile is a square that consists of n×n pixels, of which the middle (n-2)×(n-2) pixels are image contents, surrounded by one-pixel wide border. We setContentSizeto n-2.int ID: read directly from input.int[] Border: a four-element array, which will represent the one-pixel wide border for each of four sides of a tile. The sides are indexed in the following order: 0 is top, 1 is right, 2 is bottom, 3 is left (exactly as in CSS).
┌─0─┐
3 1
└─2─┘
Border will be internally represented as a binary number, with ones for “black” pixels #, and zeros for “white” pixels .; see the diagram below to understand the scanning direction!
Tile 1321:
.....#.##.
....##.### top: .....#.##. → 0000010110 = 22
#..##..... bottom: #####.###. → 1111101110 = 1006
.........#
#.#...#... ↓
##..#....#
↑ #..#.#....
......#.## left: ...###.#.. → 0001110100 = 116
...#...... right: .#.#.#.#.# → 0101010101 = 341
.###.#####
←
char [,] Contents: a (n-2)×(n-2) 2D char array that contains the contents of the tile (so excluding the border).int Orientation: since each tile can be rotated or flipped, there are eight possible orientations of a tile. We will internally use the following convention: the first four orientations are rotations over 0, 90, 180, 270 angles counterclockwise, and the following four orientations will be the mirros of previous four over the vertical axis. This value will correspond to the orietation of a puzzle piece in the final image, after we assemble the image.
Orientation 0: Orientation 4:
ABC CBA
DEF FED
GHJ JHG
Orientation 1: Orientation 5:
CFJ JFC
BEH HEB
ADG GDA
Orientation 2: Orientation 6:
JHG GHJ
FED DEF
CBA ABC
Orientation 3: Orientation 7:
GDA ADG
HEB BEH
JFC CFJ
The only defined constructor for JigsawPiece will accept the input data of a single tile and fill all calculate proper values for those properties (with the exception of Orientation, which is initially set to 0).
JigsawPiece has three public methods.
int RightTileEdgereturns the number corresponding to the border number of the tile, but including the orientation! Consider example: if in the assembled image a tile is rotated counterclockwise by 90 degrees and unflipped (i.e. in orientation 1), then the right border will be the one which initally was the bottom border.
┌─0─┐ ┌─1─┐
3 1 → in orientation 1 becomes → 0 2
└─2─┘ └─3─┘
int BottomTileEdgeworks analogously.char GetJigsawOrientedBit(int x, int y)returns the pixel value, which will end at position (x,y) after orienting the tile according to the value ofOrientation.
All those complex methods allow us to only write the values of char[,] Contents and int[] Border once – afterwards the rotations and/or flips are implemented logically by only calculating proper access indices!
One more imporatnt method that needs to be discussed here is BorderClass, which is declared outside of the class as a static helper, but is nonetheless connected with JigsawPiece.
Two tiles may be glued together along a border, if their border numbers “match”. However, there are two possible cases:
- Border numbers are equal, e.g.:
111101101and111101101. - Border numbers are equal after one is reversed, e.g.:
111101101and101101111.
This is because rotation preserves the border number, and flipping always reverses the border number.
Therefore, for each border number we will define an equivalency class as following:
- For a border number, we calculate its reverse number.
- We take the smaller of the number and its reverse.
If two border numbers are in the same equivalency class, then the jigsaw pieces with those border numbers can be glued together in the final image.
Part A – assembling the images
A very important observation about the puzzle input, that significantly simplifies the algorithm, is that:
if two tiles have a border that can be glued, then they will always be glued
Or in other words, there are never more than two borders that have the same equivalency class.
To map tile ID to its position in the assembled image, we will create a int[] orderOfTiles array. At index i, corresponding to the position in the assembled image, it will hold the ID of the tile at that position. Positions are enumerated as in the diagram below, (where n is the number if images in a row).
0 1 2 3 ...
n-1 n n+2 n+3 ...
2n-1 2n ...
...
Step 1 – top left piece
We start the solution by finding a puzzle piece from the top-left corner of the assembled image. To do so, we will count how many times each border equivalency class is encountered in the input tiles.
A corner tile will have two borders that cannot be matched. An edge tile (that is not a corner tile) will have exactly one border without a match.
So we find any tile, that has two unmatched borders – and choose such orientation for that tile, so that the unmatched borders are on the edge of the assembled image.
Step 2 – top row
When we chose the top left tile, we can now look at the right border of that starting tile.
┌───A───┐ ┌───E───┐
│ │ │ │
B C C F
│ │ │ │
└───D───┘ └───G───┘
Here, A and B are unmatched border numbers. Now we need to find a jigsaw piece, which has a border number matching to C, and find an orientation in which border C is the left border, and the top border E is an umatched border.
We repeat this procedure until we fill whole top row of the jigsaw.
(Per problem description assembled image is a square, so to calculate the number of tiles per side we need to calculate the square root of the number of tiles in the input).
Step 3 – left row
Assembling the left row is analogous to the top row, there is nothing special here.
Step 4 – assembling the rest of the tiles
Now, that we have the topmost and leftmost pieces assembled, we can find an empty space with two borders defined by pieces to the top and to the left of that space (G and J on the diagram).
┌───A───┐ ┌───E───┐
│ │ │ │
B C C F
│ │ │ │
└───D───┘ └───G───┘
┌───D───┐
│ │
H J
│ │
└───K───┘
Here, we find a jigsaw piece that have border equivalence classes G and J, and find the required orientation.
After assembling the image, we lookup the IDs of tiles in the corners, multiply them and return Part A answer.
Part B – searching for the monsters
After assembling the image, finding the monsters are pretty straightforward. To find a monster, i.e. the following pattern
#
# ## ## ###
# # # # # #
we will create a “window”, a 2D char array regionToCheck starting at position (x,y), 20 pixels wide, 3 pixels high, and fill it with the AccessImageBit method. Then we just check if each required pixel is black (is a # character).
There is one caveat – as each tile can be in one of eight orientations, the same can be said about the assembled image. The monsters can be found only in one orientation of the final image, so we iterate over all possible orientations until we find the correct one.
Method AccessImageBit must take into account the orientation of the image:
char AccessImageBit(int imageX, int imageY, Dictionary tiles, int[] orderOfTiles, int bigOrientation) (Note that my solution assumes that the monsters do not overlap. Handling the overlapping would fortunately be easy to implement with a bitmask if it was necessary).