The popularity of Advent of Code cannot be understated. In it’s fifth year, the 2020 edition of Advent of Code had just over 1.3 million puzzle completions throughout the month of December. (source)

I found Day 20: Jurassic Jigsaw to be the most challenging puzzle this year. While the problem was not difficult to understand, the solution required so many steps that many opted out of the puzzle entirely. According to AoC completion statistics, day 20 was the second least completed puzzle of 2020 (behind the Christmas Day puzzle).

In this blog post, I’ll walk you through my solution to this puzzle.

If you want to jump straight into the code, you can find the entire solution on github.

Day 20 - Jurassic Jigsaw

The Problem

Our input consists of 144 tiles that need to be reassembled to form a single image (like a jigsaw puzzle). Here’s an example of two tiles from the sample data

Tile 1951:       Tile 2311:
#.##...##.       ..##.#..#.      
#.####...#       ##..#.....       
.....#..##       #...##..#.       
#...######       ####.#...#      
.##.#....#       ##.##.###.       
.###.#####       ##...#.###       
###.##.##.       .#.#.#..##       
.###....#.       ..#....#..       
..#.#..#.#       ###...#.#.      
#...##.#..       ..###..###       

Tiles can be rotated and flipped until one of their sides match. In the above example, Tile 1951’s east edge matches Tile 2311’s west edge in their current orientation.

Once the image is reassembled, we are asked to count the frequency of sea monsters in image. This is a sea monster:

#    ##    ##    ###
  #  #  #  #  #  #   

Modeling The Problem

Since I like to solve AoC problems using Object Oriented Ruby, I begin each problem by identifying the key abstractions in the problem domain and modeling them with objects.

A Tile class seems like an obvious choice for this problem, so i’ll start there. I’ll store tile rows as an array of strings in the @rows instance variable.

class Tile

  def initialize(id:,rows:)
    @id = id
    @rows = rows


I’ll also create an Image class to represent a set of Tile pieces.

class Image

  def initialize(tiles:)
    @tiles =


After writing a few lines to code to read in the input file, we’re off to the races!

tiles ="input.txt").split("\n\n").map do |data|
  tile = data.split("\n") tile.first.delete("^0-9"), data: tile[1..-1])
image = tiles)

Now, let’s move onto to solving the first puzzle of the day.

Puzzle 1 - Finding Corner Pieces

The first puzzle asks us to identify the corner pieces and calculate the product of their ID’s.

While we could assemble the entire image to identify the corner pieces, there is a simpler solution. Corner tiles have the unique characteristic of sharing an edge with exactly two other tiles. Therefore, we can reduce the problem to identifying the four tiles that share exactly two edges with other tiles.

Since we’ll be comparing tile edges, I created a method on the Tile class that returns the edges of a tile. Because tiles can be flipped and rotated, the method returns all eight possible edge orientations.

class Tile
  # other code omitted...

  def all_edges
    @all_edges ||= begin
      # N E S W edges
      edges = [ @rows.first,{|r|r[-1]}.join,
                @rows.last ,{|r|r[0]}.join ]


Then, I created helper methods that determine if tiles are neighbors.

class Tile
  # other code omitted...

  # set intersection of edges
  def shared_edges(tile)
    all_edges & tile.all_edges

  # true if tile is a neighbor, false otherwise
  def neighbor_of?(tile)
    self != tile && !shared_edges(tile).empty?


Dropping into an irb console, I can confirm this works as expected on a simple Tile with two rows. When in irb, I like to represent rows with numbers instead of ‘#’ and ‘.’ because I think it’s easier to visualize. Since the Tile class is storing the rows as strings, I can use whatever representation I’d like.

➜ irb
3.0.0 :001 > tile1 = 1, rows: ["12","34"])
 => #<Tile:0x00007ff3dc82a208 @id=1, @rows=["12", "34"]>
3.0.0 :002 > tile2 = 2, rows: ["12","56"])
 => #<Tile:0x00007ff3dc1ed228 @id=2, @rows=["12", "56"]>
3.0.0 :003 > tile1.all_edges
 => #<Set: {"12", "24", "34", "13", "21", "42", "43", "31"}>
3.0.0 :004 > tile2.all_edges
 => #<Set: {"12", "26", "56", "15", "21", "62", "65", "51"}>
3.0.0 :005 > tile1.neighbor_of?(tile2)
 => true

Because all_edges returns all possible edge orientations, I don’t need to worry about flipping or rotating the tile when checking for neighbors. Tiles are neighbors if the the intersection of their edges is not empty.

These Tile methods give me a convenient way to identify neighbors for each tile.

class Image

  # other code omitted...

  # return an array of neighboring tiles
  def neighbors_of(tile)
    @tiles.filter_map { |t| t if tile.neighbor_of?(t) }

  # return a hash of tiles to their neighbors (an adjacency list)
  def neighbors
    @neighbors ||={|tile| [tile, neighbors_of(tile)]}.to_h

  def corners{|tile,neighbors| neighbors.length == 2 }.keys


I decided to store the results of the neighbor calculations in an adjacency list, which lets me easily identify corner tiles and calculate the solution to the first puzzle.

➜ irb
# tiles is an array of Tile objects parsed from a file
3.0.0 :001 > image =>tiles)
 => #<Image:0x00007ff3dd181db0 @tiles=#<Set:...>>
3.0.0 :002 >*)
 => 23497974998093

Puzzle 2 - Reassemble The Image

The second puzzle is where things get mind numbingly awful interesting!

This puzzle requires us to reassemble the tiles into an image, strip the borders from each tile and count the number of times a specific pattern occurs in the combined image. Oh, and the reassembled image may itself need to be flipped and rotated to find the pattern.

(╯°□°)╯︵ ┻━┻


Flipping and Rotating Tiles

To make reasoning about this problem easier, I’ll assign labels to each of the eight possible tile edges. Starting from the north side of the tile and moving clockwise, I’ll use labels A,B,C and D and the reverse of these edges E,F,G and H.

For example, here’s the front and back of a 5x5 tile with edges labeled.

edge labeling

Using these labels, I can represent the front and back side of this tile as A,B,C,D,E,D,G,B. Note that edges F and H are not represented in this orientation, but will be if we rotate the tile 90 degrees to the right.

edge label example

This newly rotated tile can be represented as H,A,F,C,D,C,B,A

Repeating this process two more times gives me a compact way to represent all possible tile orientations.

This concept translates nicely into Ruby, where I used arrays of symbols to represent the edges in each tile orientation.

class Tile

  # other code omitted...

  EDGE_LABELS =  %i[a b c d e f g h]
  EDGE_STATES = [%i[a b c d e d g b], # 0°
                 %i[h a f c d c b a], # rotate 90°
                 %i[g h e f c f a h], # rotate 180°
                 %i[b g d e f e h g]] # rotate 270°

  # returns the edge for the given label
  def edge_for(label)
    # hash of label to edge {a: "#..#.",b: ".##..",...}
    @edge_hash ||=


The edge_for method maps the labels to the string representation of the tile edge.

The EDGE_STATE array represents the front and back edges of a tile at each rotation (0°,90°,180°,270°).

Representing tiles in this way means I can avoid complex 2D array transformations while reassembling tiles. I only need to keep track of how many times the tile has been flipped or rotated.

As a result of how the edge states are modeled, the flip! and rotate! methods are dead simple.

class Tile

  SIDES = {:N=>0,:E=>1,:S=>2,:W=>3}
  EDGE_LABELS =  %i[a b c d e f g h]
  EDGE_STATES = [%i[a b c d e d g b], # 0°
                 %i[h a f c d c b a], # 90°
                 %i[g h e f c f a h], # 180°
                 %i[b g d e f e h g]] # 270°

  def initialize(id:,rows:)
    # ...
    @flipped,@num_rotations = false,0

  def rotate!
    @num_rotations = (@num_rotations+1) % NUM_SIDES

  def flip!
    @flipped = !@flipped

  # returns the edge at the specified direction (N S E W),
  def edge_at(direction)
    edge_index = @flipped ? SIDES[direction] + NUM_SIDES : SIDES[direction]


Let’s walk through an example of this in action.

3.0.0 :001 > tile = 1, rows: ["12","34"])
 => #<Tile:0x00007fe6ac8a6bb0 @id=1, @rows=["12", "34"], @flipped=false, @num_rotations=0>
3.0.0 :002 > tile.edge_at(:N)
 => "12"
3.0.0 :003 > tile.flip!
 => true
3.0.0 :004 > tile.edge_at(:N)
 => "21"
3.0.0 :005 > tile.rotate!
 => 1
3.0.0 :006 > tile.edge_at(:N)
 => "13"
3.0.0 :007 > tile
=> #<Tile:0x00007fe6ac8a6bb0 @id=1, @rows=["12", "34"], @flipped=true, @num_rotations=1>

Arranging The Tiles

My solution to the first puzzle left me with an adjacency list, which means I already know the neighbors for each tile. To reassemble the image, I just need to flip/rotate each tile until it fits with it’s neighbors. Returning to the Tile class, I create an arrange! method that flips/rotates the tile until the edge is facing the requested direction.

class Tile

  # other code omitted...

  def arrange!(dir,edge)
    return false unless has_edge?(edge)
    8.times do |i|
      return true if edge_at(dir) == edge
      i == NUM_SIDES-1 ? flip! : rotate!


To reassemble the image, I start by selecting and placing a corner tile in the upper left of the image. Next, I perform a breadth first traversal of the adjacency list, rotating/flipping and placing neighboring tiles as I go. This process continues until the traversal is complete.

class Image

  def initialize(tiles:)
    @tiles =
    @dimension = Math.sqrt(tiles.size)
    @image ={}

  # other code omitted...

  def reassemble!
    corner = corners.first
    # rotate corner into position
    se1,se2 = neighbors[corner].map{|tile| corner.shared_edges(tile) }
    8.times do |i|
      break if se1.include?(corner.edge_at(:E)) && se2.include?(corner.edge_at(:S))
      i == 3 ? corner.flip! : corner.rotate!
    # place the corner tile
    # process the rest
    assemble_image!(tile: corner, row:0, col:0)

  def assemble_image!(tile:,row:,col:)
    return if row >= @dimension || col >= @dimension
    neighbors[tile].each do |t|
      unless @seen.include?(t)
        if t.has_edge?(tile.edge_at(:E))
          t.arrange!(:W, tile.edge_at(:E))
          place_tile(tile:t, row:row, col:col+1)
          assemble_image!(tile:t, row:row, col:col+1)
        elsif t.has_edge?(tile.edge_at(:S))
          t.arrange!(:N, tile.edge_at(:S))
          place_tile(tile:t, row:row+1, col:col)
          assemble_image!(tile:t, row:row+1, col:col)

  def place_tile(tile:,row:,col:)
    @seen ||=


Assembling The Image

The last step in reassembling the image requires us to strip the borders from each tile.

class Tile

  # other code omitted...

  def remove_borders


Before we merge the tiles together, recall that my solution has only involved tile edges. I’ve never once changed the orientation of the tile rows at any point. Before reassembling the tiles into a larger image, it’s time to apply the rotations and flips to all rows of the tile. I wrote a method on the Tile class called refresh, which returns a copy of the tile rows with the flip/rotate transformations applied.

class Tile

  # other code omitted ...

  def refresh
    rows ={ |row| row.split("") }
    @num_rotations.times { rows = }!) if @flipped


The Tile class never modifies the tile rows directly. I found the problem easier to reason about if the tile rows were separate from it’s orientation. This just-in-time tile flipping and rotating prevents my code from unnecessarily transforming 2D arrays at every step of the process. It also made debugging much simpler.

For good measure, I also added a rows method that calls refresh on the tile and caches the result for the given flip status and number of orientations. This ensures that tile transformations are never repeated.

def rows
  @rows_cache ||= {|h,k| h[k] = refresh }

You can see the caching in action in irb

3.0.0 :001 > tile = 1, rows: ["12","34"])
 => #<Tile:0x00007fc734984150 @id=1, @rows=["12", "34"], @flipped=false, @num_rotations=0>
3.0.0 :002 > tile.rows
 => ["12", "34"]
3.0.0 :003 > tile
 => #<Tile:0x00007fc734984150 @id=1, @rows=["12", "34"], @flipped=false, @num_rotations=0, @rows_cache={[false, 0]=>["12", "34"]}>
3.0.0 :004 > tile.rotate!
 => 1
3.0.0 :006 > tile.rows
 => ["31", "42"]
3.0.0 :005 > tile
 => #<Tile:0x00007fc734984150 @id=1, @rows=["12", "34"], @flipped=false, @num_rotations=1, @rows_cache={[false, 0]=>["12", "34"], [false, 1]=>["31", "42"]}>

Finding Sea Monsters

While this problem could probably be solved with a regex, I opted for a different solution (read: I suck at regexes).

I converted the sea monster into a set of (x,y) coordinates. Using those coordinates, I traversed my reassembled image checking the collection of points and counting when a match was found.

I put all this logic in a TileScanner class because my Tile class was starting to feel busy, and this seemed like a separate concern. The class operates on Tile objects; one for the reassembled image and one for the monster. Because it was smaller, I opted to flip/rotate the monster tile instead of the larger image.

You can check out the implementation here if you’re interested in the details.


We made it! Phew, that was…a lot.

Day 20 took a ton of effort. While the problem was simple to understand, the implementation required significantly more code than any other puzzle this year. This was the only Advent of Code puzzle I did not complete the day it was released. However, I had much more fun solving the problem after I had a chance to think more deeply about the solution.

The entire solution, along with unit tests and sample input can be found on github.