2020-12-20 - Jurassic Jigsaw
(original .ipynb)
Day 20 input is a sequence of "tiles" - grids composed of # and . characters (mine is here). The tiles can be combined to form a grid, where a tile can be beside another tile if its edges match up. They can be rotated or flipped (think of them like a jigsaw piece). Part 1 involves combining them to find the corner tiles. Part 2 involves producing an output image and looking for a certain "monster" pattern.
from collections import defaultdict
from functools import reduce
puzzle_input_str = open("puzzle_input/day20.txt", "r").read()
test_input_str = """Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###
Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#..
Tile 1171:
####...##.
#..##.#..#
##.#..#.#.
.###.####.
..###.####
.##....##.
.#...####.
#.##.####.
####..#...
.....##...
Tile 1427:
###.##.#..
.#..#.##..
.#.##.#..#
#.#.#.##.#
....#...##
...##..##.
...#.#####
.#.####.#.
..#..###.#
..##.#..#.
Tile 1489:
##.#.#....
..##...#..
.##..##...
..#...#...
#####...#.
#..#.#.#.#
...#.#.#..
##.#...##.
..##.##.##
###.##.#..
Tile 2473:
#....####.
#..#.##...
#.##..#...
######.#.#
.#...#.#.#
.#########
.###.#..#.
########.#
##...##.#.
..###.#.#.
Tile 2971:
..#.#....#
#...###...
#.#.###...
##.##..#..
.#####..##
.#..####.#
#..#.#..#.
..####.###
..#.#.###.
...#.#.#.#
Tile 2729:
...#.#.#.#
####.#....
..#.#.....
....#..#.#
.##..##.#.
.#.####...
####.#.#..
##.####...
##..#.##..
#.##...##.
Tile 3079:
#.#.#####.
.#..######
..#.......
######....
####.#..#.
.#...#.##.
#.#####.##
..#.###...
..#.......
..#.###..."""
def parse_tile(tile_str):
tile_lines = tile_str.split("\n")
id_str = tile_lines[0].strip().removeprefix("Tile ").removesuffix(":")
tile_lines = tile_lines[1:]
tile = [
[c for c in row]
for row in tile_lines
]
return int(id_str), tile
def parse_input(input_str):
tile_strs = input_str.split("\n\n")
return [parse_tile(tile_str) for tile_str in tile_strs]
def tile_side_patterns(tile, step=1):
top = "".join(tile[0])
bottom = "".join(tile[len(tile)-1])
left = "".join([row[0] for row in tile])
right = "".join([row[len(row)-1] for row in tile])
return top[::step], bottom[::step], left[::step], right[::step]
def tile_is_corner(tile_id, sides_by_tiles, tiles_by_sides):
shared_sides = 0
for side in sides_by_tiles[tile_id]:
shared_sides += len(tiles_by_sides[side]) - 1
return shared_sides == 2
def get_side_mappings(tiles):
sides_by_tiles = defaultdict(lambda:[])
tiles_by_sides = defaultdict(lambda:[])
for tile_id, tile in tiles:
# normal
for side in tile_side_patterns(tile):
tiles_by_sides[side].append(tile_id)
sides_by_tiles[tile_id].append(side)
# flipped
for side in tile_side_patterns(tile, -1):
tiles_by_sides[side].append(tile_id)
return sides_by_tiles, tiles_by_sides
def find_corner_tiles(tiles):
sides_by_tiles, tiles_by_sides = get_side_mappings(tiles)
return [
tile_id
for tile_id,tile in tiles
if tile_is_corner(tile_id, sides_by_tiles, tiles_by_sides)
]
def part1(input_str):
tiles = parse_input(input_str)
corner_tiles = find_corner_tiles(tiles)
return reduce(lambda a,b: a*b, corner_tiles)
assert 20899048083289 == part1(test_input_str)
part1(puzzle_input_str)
20033377297069
import math
from pprint import pprint
def rotate(tile):
# this zip(...) expr to rotate a 2D array is stupendous.
# obviously I didn't come up with it
return [list(row) for row in zip(*tile[::-1])]
def flip(tile):
# this expr to flip is very basic
# however, I did write this one
return tile[::-1]
def rotations(lst):
for _ in range(4):
yield lst
yield flip(lst)
lst = rotate(lst)
def fit_below(placed_tile, target_tile):
top_placed, bottom_placed, left_placed, right_placed = tile_side_patterns(placed_tile)
top_target, bottom_target, left_target, right_target = tile_side_patterns(target_tile)
return bottom_placed == top_target
def fit_right(placed_tile, target_tile):
top_placed, bottom_placed, left_placed, right_placed = tile_side_patterns(placed_tile)
top_target, bottom_target, left_target, right_target = tile_side_patterns(target_tile)
return right_placed == left_target
def topleft_align(tile, tile_id, tiles_by_sides):
for tile in rotations(tile):
top, bottom, left, right = tile_side_patterns(tile)
top = len(tiles_by_sides[top]) == 1
left = len(tiles_by_sides[left]) == 1
if top and left:
return tile
raise Exception(f"Not possible to align tile {tile_id} to top-left, likely it does not belong there")
def find_fit_alignment(solution, row, col, base_tile):
up_tile = solution[row-1][col] if row > 0 else None
left_tile = solution[row][col-1] if col > 0 else None
next_new_line = col == len(solution) - 1
next_col = 0 if next_new_line else col + 1
next_row = row + 1 if next_new_line else row
for tile in rotations(base_tile):
aligned = True
if left_tile != None:
aligned = aligned and fit_right(left_tile[1], tile)
if up_tile != None:
aligned = aligned and fit_below(up_tile[1], tile)
if aligned:
return tile, next_row, next_col
return None, row, col
def trim_tile(tile):
return [
"".join(line[1:-1])
for line
in tile[1:-1]
]
def render_tiles(tiles):
# start of by trimming the borders of each tile
#print(tiles[0][0][0])
draw_tiles = []
for row in tiles:
new_row = []
for tile_id, tile in row:
new_row.append(trim_tile(tile))
draw_tiles.append(new_row)
# ok now draw_tiles has the border-less tiles, we
# can start putting the image together. it'll be
# an array of lines that we'll "".join("\n") at
# the end
image = []
for row in draw_tiles:
lines = [[] for n in range(len(row[0]))]
for tile in row:
for i, line in enumerate(tile):
lines[i].append(line)
image += [
[ c for c in "".join(line) ]
for line
in lines
]
return image
monster_str = "\n".join([
" # ",
"# ## ## ###",
" # # # # # # "
])
def get_monster_data():
monster_coords = []
monster_lines = monster_str.split("\n")
height = len(monster_lines) # well yes it's three but :shrug:
width = 0
for r, row in enumerate(monster_lines):
for c, col in enumerate(row):
if col == "#":
if c > width:
width = c
monster_coords.append((r,c))
return monster_coords, width, height
def monster_match(image, r, c, monster_data):
monster_coords, monster_width, monster_height = monster_data
too_far_down = r + monster_height >= len(image)
too_far_right = c + monster_width >= len(image[0])
if too_far_down or too_far_right:
return []
monster_found = all(image[r+mr][c+mc] == "#" for mr,mc in monster_coords)
if not monster_found:
return []
return [(r+mr, c+mc) for mr, mc in monster_coords]
def part2(input_str):
tiles = parse_input(input_str)
tile_lookup = {tile_id:tile for tile_id,tile in tiles}
sides_by_tiles, tiles_by_sides = get_side_mappings(tiles)
corner_tiles = find_corner_tiles(tiles)
dimension = int(math.sqrt(len(tiles)))
# alright start off building the empty grid
solution = []
for r in range(dimension):
row = []
for c in range(dimension):
row.append(None)
solution.append(row)
# select a corner, align it and set it to [0][0] (top-left)
start_tile_id = corner_tiles[0]
start_tile = topleft_align(tile_lookup[corner_tiles[0]], corner_tiles[0], tiles_by_sides)
solution[0][0] = (start_tile_id, start_tile)
tiles = [t for t in tiles if t[0] != start_tile_id]
# next (very inefficiently) move through the list trying to find a tile that fits
row = 0
col = 1
while tiles:
tile_id, tile = tiles.pop(0)
aligned_tile, next_row, next_col = find_fit_alignment(solution, row, col, tile)
if aligned_tile:
solution[row][col] = (tile_id, aligned_tile)
row, col = next_row, next_col
else:
tiles.append([tile_id, tile])
# show the solution
for r in solution:
print([t[0] if t else None for t in r])
base_image = render_tiles(solution)
monster_data = get_monster_data()
for image in rotations(base_image):
monster_positions = []
for r, row in enumerate(image):
for c, col in enumerate(row):
monster_positions += monster_match(image, r, c, monster_data)
if len(monster_positions) > 0:
for r,c in monster_positions:
image[r][c] = "O"
#pprint(["".join(line) for line in image])
roughness = 0
for row in image:
for col in row:
if col == "#":
roughness += 1
return roughness
# we shouldn't get here but what the hell
return -1
assert 273 == part2(test_input_str)
part2(puzzle_input_str)
[1951, 2311, 3079] [2729, 1427, 2473] [2971, 1489, 1171] [1831, 1423, 1069, 1877, 1871, 3989, 3851, 2087, 1747, 2663, 2633, 2789] [3607, 3671, 2179, 1973, 3467, 2423, 2053, 3517, 2069, 1171, 1597, 1549] [2677, 3461, 2903, 3001, 2887, 3931, 3217, 2297, 3041, 1303, 1487, 2381] [3449, 2971, 2621, 3673, 1433, 1453, 3797, 1087, 3769, 3631, 3547, 3617] [1451, 3023, 2549, 2897, 3343, 2917, 2089, 2221, 3643, 2311, 3943, 2729] [1013, 1249, 2083, 3221, 3697, 1949, 3259, 1481, 2459, 3079, 3581, 2647] [2953, 2687, 3209, 2081, 3413, 3331, 1759, 1459, 2467, 3533, 1039, 2797] [2999, 3539, 1697, 1693, 1511, 3433, 2341, 1471, 1103, 3919, 1907, 2417] [2731, 3313, 1657, 2927, 2129, 3911, 3011, 2237, 1279, 1151, 1109, 2029] [3583, 2593, 2963, 2437, 1951, 1307, 1153, 2281, 2203, 2389, 2671, 2767] [3529, 3329, 1499, 2939, 2339, 2267, 1123, 2357, 1847, 1789, 3557, 3391] [1699, 2251, 1367, 3767, 2693, 3929, 2441, 2017, 2011, 1667, 1559, 2309]
2084