day 20⌗

https://adventofcode.com/2020/day/20

The task is to assemble an image from different 10x10 tiles. The tiles themselves can be flipped and rotated.

transformations⌗

I didn’t want to calculate the image transformations myself, so I used java’s java.awt.geom.AffineTransform. I created a 4x4 testimage with 16 different shades of red to calculate a hash of the overall image to check, which transformation yield the same result.

all 18 possible transformations

• Clockwise180
• Clockwise180,FlipHorizontal
• Clockwise180,FlipVertical
• Clockwise270
• Clockwise270,FlipHorizontal
• Clockwise270,FlipVertical
• Clockwise90
• Clockwise90,FlipHorizontal
• Clockwise90,FlipVertical
• FlipHorizontal
• FlipHorizontal,Clockwise180
• FlipHorizontal,Clockwise270
• FlipHorizontal,Clockwise90
• FlipVertical
• FlipVertical,Clockwise180
• FlipVertical,Clockwise270
• FlipVertical,Clockwise90
• NoOp

examples of different transformations yielding the same image⌗

image	transformations	hash
	NoOp	0153045607590105120135150165180195210225
	Clockwise270, FlipVertical	0601201801575135195309015021045105165225
	FlipVertical, Clockwise90	0601201801575135195309015021045105165225
	Clockwise180, FlipVertical	1801952102251201351501656075901050153045
	FlipHorizontal	1801952102251201351501656075901050153045

There are only 8 distinct transformations⌗

image	transformations	hash
	NoOp	0153045607590105120135150165180195210225
	Clockwise90	4510516522530901502101575135195060120180
	Clockwise180	2252101951801651501351201059075604530150
	Clockwise270	1801206001951357515210150903022516510545
	Clockwise90, FlipVertical	2251651054521015090301951357515180120600
	FlipHorizontal	1801952102251201351501656075901050153045
	FlipVertical	4530150105907560165150135120225210195180
	FlipVertical, Clockwise90	0601201801575135195309015021045105165225

image transformations⌗

take this tile from the example input

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

tiles as images⌗

image	transformations	image	transformations
	NoOp		Clockwise90, FlipVertical
	Clockwise90		FlipHorizontal
	Clockwise180		FlipVertical
	Clockwise270		FlipVertical, Clockwise90

calculating edges⌗

To find the matching edges I decided to encode the edges of each tile (and its transformed representations) as hashes. For that we take the top, left, bottom and right pixels and convert them into binary representation.

#.##...##. -->
1011000110 = 710

So the top edge of tile 1951 from above is represented as 710.

matching edges⌗

To find a matching pair the directions of the matches matter.

match-direction: vertical⌗

id1 (top)
id2 (bottom)

match-direction: horizontal⌗

id1 (left) | id2 (right)

matching tiles⌗

This are all the matching edges.

finding the corner pieces⌗

If you count the number of matching tiles for each tile, you can determine their place in the picture.

The tiles with only two matching tiles must be the corners of the picture. Thankfully, Erik designed the puzzle in a way that this property holds.

So, our corners are these tiles.

assembling the picture⌗

Assembling the picture turns out to be quite complex. First, we have to pick one of the four corner pieces and assume, this is our top-left tile.

Let’s pick the aforementioned corner-tile 1951 as our top-left cornerpiece.

We now have to figure out how to transform it in a way, such that the matching edges are on the inside - or, we flip it around and look for the edges that face outwards.

finding the outer edges⌗

We now have to pick those transformations where the top and left edge have one of those hashes (177, 564, 587, 841)

finding correct transformations of 1951 to make it a cornerpiece with the correct edges facing outwards⌗

Here are the edge-configurations of every possible transformation of tile 1951.

We now know, that there are only two valid transformations of tile 1951: FlipVertical and Clockwise90.

With this information we can orient the neighbors of 1951 properly.

orienting the neighbors⌗

We know from above that 1951 only has two possible neighbors.

Let’s expand that relationship further.

We have two possibilities to arange these pieces

y\x	0	1
0	1951 FlipVertical	2311 FlipVertical
1	2729 FlipVertical

y\x	0	1
0	1951 Clockwise90	2729 Clockwise90
1	2311 Clockwise90

more constraints⌗

We know that the piece at (1,0) has to have its top edge outwards-facing.

Here are the tile-configurations of 2311 and 2729 after applying the possible transformations (FlipVertical and Clockwise90)

Let’s examine 2311:

• if we put 2311 at (1,0) we have to apply FlipVertical. The the top edge has to be facing outwards, which it does (hash 231).
• if we put 2311 at (0,1) we have to apply Clockwise90. The the left edge has to be facing outwards, which it does (hash 231).

Let’s examine 2729:

• if we put 2729 at (1,0) we have to apply Clockwise90. The the top edge has to be facing outwards, which it does (hash 962).
• if we put 2729 at (0,1) we have to apply FlipVertical. The the left edge has to be facing outwards, which it does (hash 962).

This doesn’t help us either, since these configurations are still valid.

finding tiles with two neighbors⌗

We want to place the tile (1,1). It has to satisfy the following condition

   tile(1,1).top  == tile(1,0).bottom
&& tile(1,1).left == tile(0,1).right

This means we’re looking for a tile t where

t.top == 210 && t.left == 9 ||
t.top == 9   && t.left == 210

We have still have two possibilities to arange these pieces.

y\x	0	1
0	1951 FlipVertical	2311 FlipVertical
1	2729 FlipVertical	1427 FlipVertical

y\x	0	1
0	1951 Clockwise90	2729 Clockwise90
1	2311 Clockwise90	1427 Clockwise90

finding the top right corner piece⌗

We can now look for the top right corner piece with one added constraint. Its left edge has to match the right edge of (1,0). The transformation has to orient the tile in a way that the top and right faces point outwards.

Still two possibilities to arrange our tiles.

y\x	0	1	2
0	1951 FlipVertical	2311 FlipVertical	3079 NoOp
1	2729 FlipVertical	2729 FlipVertical

y\x	0	1	2
0	1951 Clockwise90	2729 Clockwise90	2971 Clockwise90
1	2311 Clockwise90	1427 Clockwise90

finding the bottom left corner piece⌗

We can now look for the bottom left corner piece with one added constraint. Its top edge has to match the bottom edge of (0,1). The transformation has to orient the tile in a way that the bottom and left faces point outwards.

y\x	0	1
0	1951 FlipVertical	2311 FlipVertical
1
2

y\x	0	1
0	1951 Clockwise90	2729 Clockwise90
1
2

mirrored symmetry⌗

We see that it’s going to continue to find two possibilities, since the whole thing can be mirrored. For completing the example we just pick the first configuration. For that we place 2971 at (2,0) and 3079 at (0,2).

y\x	0	1	2
0
1
2

continue to fill the missing pieces⌗

(1,2)⌗

y\x	0	1	2
0
1
2

(2,1)⌗

y\x	0	1	2
0
1
2

(2,2)⌗

Yay - our last cornerpiece

the last piece⌗

y\x	0	1	2
0
1
2

generalizing the rules⌗

• pick one of the cornerpieces for (0,0) and orient it
  • top and left edges must face outwards
  • if there are more than one possible transformation, pick one of them

  val filterFn: ((Int, Edge, List[Transformation], BufferedImage)) => Boolean = { row =>
    (useTopTileFilter, useLeftTileFilter) match {
      case (true, true)   => topTileFilter(row) && leftTileFilter(row)
      case (true, false)  => topTileFilter(row) && leftOuterFilter(row)
      case (false, true)  => leftTileFilter(row) && topOuterFilter(row)
      case (false, false) => topOuterFilter(row) && leftOuterFilter(row)
    }
  }

finding Nessi⌗

the final assembly⌗

assembled image with borders	assembled image with highlighted border	final version with borders removed

nessi⌗

We have to find this pattern in the final image, but (of course) we don’t know how the image has been transformed.

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

We transform the image in all 8 ways and search for the pattern in each image.

transformations	image
NoOp
Clockwise90
Clockwise180
Clockwise270
FlipHorizontal
FlipVertical
FlipVerticalClockwise90
Clockwise90FlipVertical

The final image⌗

We need to count the number of water-pixels that are not occupied by a sea monster. I don’t know if the sea monsters would overlap, so I selected all sea-monster pixels and diffed it with all water-pixels.

Solution for part 2⌗

The solution for the random seed of my user looked like this

Turned out there were no overlapping sea monsters ;-)

Great fun, but quite complex to solve. I could have done it a lot simpler, but I enjoyed the programming with graphics.

$$ $$