Expand description
§Jurassic Jigsaw
At first this seems like a daunting problem. However a little anaylsis shows that the input has some nice properties that makes solving this more tractable.
- Tile edges match with at most one other tile
- The forward and reverse tile edges form two distinct sets of 312 values with no overlap.
Tiles can be flipped and rotated for a total of 8 possible permutations each. When parsing the tiles we store all 8 edge possibilities to enable assembling the jigsaw in part two. For performance we avoid transforming the inner 8x8 pixels until we have determined the layout of the grid.
§Part One
First we calculate the frequency of each edge, both forwards and backwards as tiles can be in any orientation. As there only 2¹⁰ or 1024 possible edge values we can use an array intead of a hashtable for speed, converting the edges into a binary number to index the array.
This results in 96 values that occur once and 528 values that occur twice. Then for every tile we sum the frequency of each edge. Corner tiles will have two edges that only occur once, not matching with any other tile, for a total of 1 + 1 + 2 + 2 = 6.
Other edge tiles have a total of 1 + 2 + 2 + 2 = 7 and inner tiles a total of 2 + 2 + 2 + 2 = 8.
§Part Two
First we arbitrarily pick any corner tile that is oriented so that its unique edges are facing
top and left. Then we proceed row by row, looking up the next tile to the right. Each time
we find a tile we remove it from the remaining tiles, so that looking up a tile is always a
very fast constant time O(1) operation.
The complete picture is stored as an array of u128 values as the tiles form a square 12 wide,
for a total of 12 * 8 = 96 pixels. As we add each tile, we convert its pixels into a u8 binary
number and left shift to add to the existing pixels.
When finding the monsters we make some further assumptions about the input:
- The monsters will all be oriented the same way
- Monsters will not overlap with each other
For speed the monster bit patterns are rotated and flipped instead of the image, then stored in hardcoded arrays. The search ends as soon as we find monsters in any orientation.