 Day 20 was almost the end of my 2020 Advent of Code. I managed to solve part one in 15 minutes, but then part two got me for days. I finally solved it, but I can’t promise pretty code.

## Challenge

The puzzle can be found here. I’m given a series of tiles, each of which is ten by ten with either . or # like:

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


I’ll need to find a way to arrange the given tiles such that the any two tiles sharing a border have the same pattern on that border like these three:

#...##.#..  ..###..###  #.#.#####.
..#.#..#.#  ###...#.#.  .#..######
.###....#.  ..#....#..  ..#.......
###.##.##.  .#.#.#..##  ######....
.###.#####  ##...#.###  ####.#..#.
.##.#....#  ##.##.###.  .#...#.##.
#...######  ####.#...#  #.#####.##
.....#..##  #...##..#.  ..#.###...
#.####...#  ##..#.....  ..#.......
#.##...##.  ..##.#..#.  ..#.###...


The tiles can be rotated and flipped to get there.

The solution to part one is to find that layout and return the product of the four ids of the corners of the resulting map.

In part two, I’m asked to remove the edges (they are just used for orientation), and then look for sea monsters in the resulting image, again, with rotations and flips:

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


For each sea monster, I can change those to O and then count the remaining #.

## Solution

### Part 1

I’ll read in the tile list, breaking on double newline. I’ll keep a dictionary of tiles, where the key is the id, and the rest holds information about the tile. I’ll loop over the raw tiles, pulling the id from the first line, and then the grid from the rest. I’ll also record the sides (both forward and backwards) . Then I’ll loop over the tiles that are already recorded and look for any shared sides. If they are found, I’ll record them as neighbors:

with open(sys.argv, 'r') as f:

tiles = {}

for raw_tile in tiles_raw:
lines = raw_tile.strip('\n').split('\n')
idn = int(lines.split().strip(':'))
grid = lines[1:]
sides = [grid, grid[-1], ''.join([g for g in grid]), ''.join([g[-1] for g in grid])]
sides += [s[::-1] for s in sides]
tiles[idn] = {"grid": grid, "sides": sides, 'neighbors': {}}

for i, tile in tiles.items():
if i == idn:
continue
shared = [s for s in tile['sides'] if s in sides]
for s in shared:
tiles[idn]['neighbors'][i] = s
tiles[i]['neighbors'][idn] = s


With that information, finding the corners is just finding the tiles with only two neighbors:

corners = list(map(int, [t for t in tiles if len(tiles[t]['neighbors']) == 2]))
res = 1
for c in corners:
res *= c

print(f'Part 1: {res}')


### Part 2

This is where it gets crazy. First, I need to lay all the tiles together into a big grid. I’ll pick a corner arbitrarily, and then start working through it’s neighbors looking for one that matches the right side. I created a few helper functions:

def get_side(tile, side):
if side == "top":
return tile
if side == "bottom":
return tile[-1][::-1]
if side == "right":
return "".join([t[-1] for t in tile])
if side == "left":
return "".join([t for t in tile])[::-1]
raise ValueError

def get_sides(tile):
return [get_side(tile, "top"), get_side(tile, "right"), get_side(tile, "bottom"), get_side(tile, "left")]

def rotate(tile):
R = len(tile)
C = len(tile)
new = [["x" for _ in range(C)] for _ in range(R)]
for r in range(R):
for c in range(C):
new[r][c] = tile[C - c - 1][r]
return ["".join(r) for r in new]

def flip(tile):
return tile[::-1]



I’m going to store the combined image in an array of strings, so I created another helper to add a tile to the array, either to the end of the current row, or to the start of a new row of tiles:

def add_fullpic(tile, newline=False):
global fullpic
if fullpic == []:
fullpic = deepcopy(tile)
elif newline:
for r in tile:
fullpic.append(r)
else:
R = len(fullpic) - len(tile)
for r in range(len(tile)):
fullpic[r + R] += tile[r]


Now I’ll create a loop while there are tiles that are not yet added. At a high level, it looks like:

r, c = 0, 0
gridmap = {}
fullpic = []

while not len(gridmap) == len(tiles):
if r == 0 and c == 0:
...[snip]...
c += 1
elif c == 0:
# add new tile based on first tile in previous row's bottom
...[snip]...
c += 1
else:
# look for next in row
...[snip]...
if find next:
...[snip]...
c += 1
else:
r, c = r + 1, 0


This is where the code gets a bit ugly and I can’t stand to spend time cleaning it up. For the first tile, I’ll add it, and rotate it until the bottom and right sides match the sides listed as neighbors:

    if r == 0 and c == 0:
idn = corners
tile = tiles[idn]["grid"]
neighbors = list(tiles[idn]["neighbors"].values())
neighbors += [n[::-1] for n in neighbors]
while True:
bottom, right = get_side(tile, "bottom"), get_side(tile, "right")
if bottom in neighbors and right in neighbors:
break
tile = rotate(tile)
gridmap[(r, c)] = idn
tiles[idn]["grid"] = tile
c += 1


For other first tiles in a row, I’ll get the tile from the above tile’s neighbor list, and rotate / flip until it matches the bottom:

    elif c == 0:
p_idn = gridmap[(r - 1, c)]
p_tile = tiles[p_idn]["grid"]
side_options = [get_side(p_tile, "bottom"), get_side(p_tile, "bottom")[::-1]]
idn = [i for i, s in tiles[p_idn]["neighbors"].items() if s in side_options]
tile = tiles[idn]["grid"]
n_side = get_side(tiles[p_idn]["grid"], "bottom")
found = False
for i in range(8):
if i == 4:
tile = flip(tile)
if get_side(tile, "top") == n_side[::-1]:
found = True
break
tile = rotate(tile)
raise
gridmap[(r, c)] = idn
tiles[idn]["grid"] = tile
c += 1


It’s important to note that there are only eight orientations for each tile. Four rotations, flip on either edge, and then four more rotations.

Finally, when looking to grow an existing row, I’ll look to see if there are any neighbors that match the right side of the last tile. If there’s one, I’ll rotate/flip it until it matches, and add it. If there are none, I’ll go to the next row:

    else:
p_idn = idn
p_tile = tiles[p_idn]["grid"]
side_options = [get_side(p_tile, "right"), get_side(p_tile, "right")[::-1]]
idn = [i for i, s in tiles[p_idn]["neighbors"].items() if s in side_options]
if len(idn) == 1:
idn = idn
tile = tiles[idn]["grid"]
n_side = get_side(tiles[p_idn]["grid"], "right")
found = False
for i in range(8):
if i == 4:
tile = flip(tile)
if get_side(tile, "left") == n_side[::-1]:
found = True
break
tile = rotate(tile)
raise
gridmap[(r, c)] = idn
tiles[idn]["grid"] = tile
c += 1



At this point, I have the assembled image. Now I need to remove the edges.

G = []
for i in range(len(fullpic) // 10):
G.extend(fullpic[(10 * i) + 1 : (10 * i) + 9])
G = ["".join([r[(10 * c) + 1 : (10 * c) + 9] for c in range(len(r) // 10)]) for r in G]


The first loop removes the extra rows, and the second the extra columns.

Next is the monster. I’ll define the monster as a series of offsets to some point:

monster = [(0, 1), (1, 2), (4, 2), (5, 1), (6, 1), (7, 2), (10, 2), (11, 1),
(12, 1), (13, 2), (16, 2), (17, 1), (18, 0), (18, 1), (19, 1)]


I’ll loop over the grid for each orientation checking if the point is the start of the monster, and if so, add all the monster points to a set. If there were overlapping monsters, this would account for that (there aren’t, so I could have just counted that and multiplied by the size of the monster at the end).

mon = set()
for i in range(8):
if i == 4:
G = flip(G)
for r in range(len(G) - 2):
for c in range(len(G) - 20):
if all([G[r + dr][c + dc] == "#" for dc, dr in monster]):
for dc, dr in monster:
mon.add((r + dr, c + dc))
G = rotate(G)

part2 = len([c for r in G for c in r if c == "#"]) - len(mon)
print(f"Part 2: {part2}")


### Final Code

This is all relatively fast, in around half a second:

\$ time python3 day20-clean.py 20-puz
Part 1: 12519494280967
Part 2: 2442

real    0m0.486s
user    0m0.472s
sys     0m0.005s


This code is pretty ugly, but it works:

#!/usr/bin/env python3

import sys
from copy import deepcopy

def get_side(tile, side):
if side == "top":
return tile
if side == "bottom":
return tile[-1][::-1]
if side == "right":
return "".join([t[-1] for t in tile])
if side == "left":
return "".join([t for t in tile])[::-1]
raise ValueError

def get_sides(tile):
return [get_side(tile, "top"), get_side(tile, "right"), get_side(tile, "bottom"), get_side(tile, "left")]

def rotate(tile):
R = len(tile)
C = len(tile)
new = [["x" for _ in range(C)] for _ in range(R)]
for r in range(R):
for c in range(C):
new[r][c] = tile[C - c - 1][r]
return ["".join(r) for r in new]

def flip(tile):
return tile[::-1]

global fullpic
if fullpic == []:
fullpic = deepcopy(tile)
elif newline:
for r in tile:
fullpic.append(r)
else:
R = len(fullpic) - len(tile)
for r in range(len(tile)):
fullpic[r + R] += tile[r]

with open(sys.argv, "r") as f:

tiles = {}

for raw_tile in tiles_raw:
lines = raw_tile.strip("\n").split("\n")
idn = int(lines.split().strip(":"))
grid = lines[1:]
sides = get_sides(grid)
sides += [s[::-1] for s in sides]
tiles[idn] = {"grid": grid, "sides": sides, "neighbors": {}}

for i, tile in tiles.items():
if i == idn:
continue
shared = [s for s in tile["sides"] if s in sides[:4]]
for s in shared:
tiles[idn]["neighbors"][i] = s
tiles[i]["neighbors"][idn] = s

corners = list(map(int, [t for t in tiles if len(tiles[t]["neighbors"]) == 2]))
res = 1
for c in corners:
res *= c

print(f"Part 1: {res}")

r, c = 0, 0
gridmap = {}
fullpic = []

while not len(gridmap) == len(tiles):
if r == 0 and c == 0:
idn = corners
tile = tiles[idn]["grid"]
neighbors = list(tiles[idn]["neighbors"].values())
neighbors += [n[::-1] for n in neighbors]
while True:
bottom, right = get_side(tile, "bottom"), get_side(tile, "right")
if bottom in neighbors and right in neighbors:
break
tile = rotate(tile)
gridmap[(r, c)] = idn
tiles[idn]["grid"] = tile
c += 1
elif c == 0:
p_idn = gridmap[(r - 1, c)]
p_tile = tiles[p_idn]["grid"]
side_options = [get_side(p_tile, "bottom"), get_side(p_tile, "bottom")[::-1]]
idn = [i for i, s in tiles[p_idn]["neighbors"].items() if s in side_options]
tile = tiles[idn]["grid"]
n_side = get_side(tiles[p_idn]["grid"], "bottom")
found = False
for i in range(8):
if i == 4:
tile = flip(tile)
if get_side(tile, "top") == n_side[::-1]:
found = True
break
tile = rotate(tile)
raise
gridmap[(r, c)] = idn
tiles[idn]["grid"] = tile
c += 1
else:
p_idn = idn
p_tile = tiles[p_idn]["grid"]
side_options = [get_side(p_tile, "right"), get_side(p_tile, "right")[::-1]]
idn = [i for i, s in tiles[p_idn]["neighbors"].items() if s in side_options]
if len(idn) == 1:
idn = idn
tile = tiles[idn]["grid"]
n_side = get_side(tiles[p_idn]["grid"], "right")
found = False
for i in range(8):
if i == 4:
tile = flip(tile)
if get_side(tile, "left") == n_side[::-1]:
found = True
break
tile = rotate(tile)
raise
gridmap[(r, c)] = idn
tiles[idn]["grid"] = tile
c += 1
elif len(idn) == 0:
r, c = r + 1, 0
else:
raise Exception

G = []
for i in range(len(fullpic) // 10):
G.extend(fullpic[(10 * i) + 1 : (10 * i) + 9])
G = ["".join([r[(10 * c) + 1 : (10 * c) + 9] for c in range(len(r) // 10)]) for r in G]

monster = [(0, 1), (1, 2), (4, 2), (5, 1), (6, 1), (7, 2), (10, 2), (11, 1),
(12, 1), (13, 2), (16, 2), (17, 1), (18, 0), (18, 1), (19, 1)]

mon = set()
for i in range(8):
if i == 4:
G = flip(G)
for r in range(len(G) - 2):
for c in range(len(G) - 20):
if all([G[r + dr][c + dc] == "#" for dc, dr in monster]):
for dc, dr in monster:
mon.add((r + dr, c + dc))
G = rotate(G)

part2 = len([c for r in G for c in r if c == "#"]) - len(mon)
print(f"Part 2: {part2}")