Assembling jigsaw puzzles for Advent of Code

Advent of Code is an annual set of small programming challenges that are released every December. Each day from December 1 to Christmas two challenges are released, growing more difficult each day (kind of like an advent calendar).

I always enjoy participating in Advent of Code; it reminds me why I like programming in the first place. Well-defined problems with definitive answers that usually require some kind of out of the box thinking are the best kind of algorithm problems. You get to actually use some of the theory and techniques you learned in computer science class, and it's a good way to practice with a new language (this year I'm going to try using Haskell).

While waiting for this year's event to start I've been going back to complete some of the challenges I never got around to finishing in previous years. One of these is Day 20, 2020.

The problem involves reassembling a series of tiles into a complete image by matching up the edges of each tile. However, each tile is rotated and flipped randomly, and trying every combination of rotations and mirrors between every single tile seems like a daunting task. Without any reference point to start from it's not clear how to go about solving this problem, which is probably why it stumped me in 2020.

As with a lot of these challenges, there's a key insight in the instructions that provides a path to start solving it:

Each tile's image data includes a border that should line up exactly with its adjacent tiles. All tiles have this border, and the border lines up exactly when the tiles are both oriented correctly. Tiles at the edge of the image also have this border, but the outermost edges won't line up with any other tiles.

That last sentence is our clue. If a tile has a border that doesn't line up with any rotated or flipped border of any other tile then we know it's an edge piece. Even better, if a tile has two unique edges then we know it's a corner piece.

Using this information we can sort the tiles into corners, edges, and middle pieces, just like separating out all the flat edges when solving a real jigsaw puzzle.

Take one of the corner pieces and rotate it until the two unique edges are on the top and left and you've got a top-left corner. Now you have a reference to start building the puzzle. You can fill in the edges by trying each of the edge tiles you sorted out previously until they fit. With the frame constructed, simply spiral inward with the middle pieces until the whole puzzle is done.

This is a fun problem, and one that's easy to visualize, so I made a simple visualization using the HTML canvas:

You can see my TypeScript implementation of the algorithm here.