324 lines
9.7 KiB
Python
324 lines
9.7 KiB
Python
from functools import reduce
|
|
|
|
|
|
def read_tile(tile_text):
|
|
tile_split = [l for l in tile_text.split('\n') if l != '']
|
|
tile_id = int(tile_split[0][5:9])
|
|
return tile_id, tile_split[1:]
|
|
|
|
|
|
def read_tiles():
|
|
with open('day20/input') as reader:
|
|
tiles_as_text = [l for l in reader.read().split('\n\n') if l != '']
|
|
|
|
tiles = {}
|
|
for tile in map(read_tile, tiles_as_text):
|
|
tiles[tile[0]] = tile[1]
|
|
return tiles
|
|
|
|
|
|
def get_top_border(tile):
|
|
return tile[0]
|
|
|
|
|
|
def get_left_border(tile):
|
|
return ''.join([l[0] for l in tile])
|
|
|
|
|
|
def get_right_border(tile):
|
|
return ''.join([l[-1] for l in tile])
|
|
|
|
def get_bottom_border(tile):
|
|
return tile[-1]
|
|
|
|
def get_borders_without_flip(tile):
|
|
return get_top_border(tile), get_bottom_border(tile), get_left_border(tile), get_right_border(tile)
|
|
|
|
|
|
def flip_borders(borders):
|
|
return map(lambda s: ''.join(list(reversed(s))), borders)
|
|
|
|
|
|
def get_borders(tile):
|
|
borders = get_borders_without_flip(tile)
|
|
reversed_borders = flip_borders(borders)
|
|
return [*borders, *reversed_borders]
|
|
|
|
|
|
def get_all_tile_borders(tiles):
|
|
tile_borders = {}
|
|
for key, value in tiles.items():
|
|
tile_borders[key] = get_borders(value)
|
|
return tile_borders
|
|
|
|
|
|
def find_corners(tiles):
|
|
tile_borders = get_all_tile_borders(tiles)
|
|
corner_parts = {}
|
|
border_parts = {}
|
|
inner_parts = {}
|
|
for t_key, t_value in tile_borders.items():
|
|
borders = list(t_value)
|
|
for check_key, check_value in tile_borders.items():
|
|
borders_to_remove = []
|
|
if t_key == check_key:
|
|
continue
|
|
|
|
for b in borders:
|
|
if b in check_value:
|
|
borders_to_remove.append(b)
|
|
|
|
for r in borders_to_remove:
|
|
borders.remove(r)
|
|
if len(borders) == 4:
|
|
corner_parts[t_key] = borders
|
|
elif len(borders) == 2:
|
|
border_parts[t_key] = borders
|
|
else:
|
|
inner_parts[t_key] = borders
|
|
return corner_parts, border_parts, inner_parts
|
|
|
|
|
|
def rotate_right(tile_image):
|
|
r_len = len(tile_image)
|
|
c_len = len(tile_image[0])
|
|
rotated = []
|
|
for col in range(c_len):
|
|
rotated.append(''.join([tile_image[row][col] for row in reversed(range(r_len))]))
|
|
return rotated
|
|
|
|
|
|
def flip_left_to_right_image(tile_image):
|
|
r_len = len(tile_image)
|
|
flipped = []
|
|
for row in range(r_len):
|
|
flipped.append(''.join(reversed(tile_image[row])))
|
|
return flipped
|
|
|
|
|
|
def is_top_border(tile, check_border):
|
|
return get_top_border(tile) == check_border
|
|
|
|
|
|
def is_left_border(tile, check_border):
|
|
return get_left_border(tile) == check_border
|
|
|
|
|
|
def top_left_border(tile, borders):
|
|
return sum(map(lambda b: is_top_border(tile, b), borders)) == 1 and sum(map(lambda b: is_left_border(tile, b), borders)) == 1
|
|
|
|
|
|
def top_border(tile, borders):
|
|
return sum(map(lambda b: is_top_border(tile, b), borders)) == 1
|
|
|
|
|
|
def orientation_corner_top_left(tile, borders):
|
|
while not top_left_border(tile, borders):
|
|
tile = rotate_right(tile)
|
|
return tile
|
|
|
|
|
|
def orientation_border_top(tile, borders):
|
|
while not top_border(tile, borders):
|
|
tile = rotate_right(tile)
|
|
return tile
|
|
|
|
|
|
def orientation_all_border_top(tiles, border_tiles):
|
|
changed_orientation_borders = {}
|
|
for key, value in border_tiles.items():
|
|
border_tile_image = tiles[key]
|
|
orientation_border_tile_image = orientation_border_top(border_tile_image, value)
|
|
changed_orientation_borders[key] = orientation_border_tile_image
|
|
return changed_orientation_borders
|
|
|
|
|
|
def build_top_from_left(tiles, starting_title, border_tiles, corners):
|
|
current = tiles[starting_title]
|
|
current_right = get_right_border(current)
|
|
changed_orientation_borders = orientation_all_border_top(tiles, border_tiles)
|
|
border_keys = list(changed_orientation_borders.keys())
|
|
|
|
top = [starting_title]
|
|
while True:
|
|
found_next_key = None
|
|
flip = False
|
|
for bk in border_keys:
|
|
if current_right == get_left_border(changed_orientation_borders[bk]):
|
|
found_next_key = bk
|
|
break
|
|
if current_right == get_right_border(changed_orientation_borders[bk]):
|
|
found_next_key = bk
|
|
flip = True
|
|
break
|
|
|
|
if found_next_key is not None:
|
|
if flip:
|
|
tiles[found_next_key] = flip_left_to_right_image(changed_orientation_borders[found_next_key])
|
|
else:
|
|
tiles[found_next_key] = changed_orientation_borders[found_next_key]
|
|
|
|
current_right = get_right_border(tiles[found_next_key])
|
|
top.append(found_next_key)
|
|
border_keys.remove(found_next_key)
|
|
else:
|
|
# top done, except last corner
|
|
break
|
|
|
|
for c_key in corners.keys():
|
|
if current_right in get_borders(tiles[c_key]):
|
|
top.append(c_key)
|
|
top_right_corner_tile = tiles[c_key]
|
|
for i in range(4):
|
|
if current_right != get_left_border(top_right_corner_tile):
|
|
top_right_corner_tile = rotate_right(top_right_corner_tile)
|
|
else:
|
|
break
|
|
|
|
if current_right != get_left_border(top_right_corner_tile):
|
|
top_right_corner_tile = flip_left_to_right_image(top_right_corner_tile)
|
|
for i in range(4):
|
|
if current_right != get_left_border(top_right_corner_tile):
|
|
top_right_corner_tile = rotate_right(top_right_corner_tile)
|
|
else:
|
|
break
|
|
tiles[c_key] = top_right_corner_tile
|
|
break
|
|
|
|
return top
|
|
|
|
|
|
def find_tile_for_bottom_border(tiles, bottom_border, remaining):
|
|
found_key = None
|
|
for r_key in remaining:
|
|
if bottom_border in get_borders(tiles[r_key]):
|
|
found_key = r_key
|
|
found_tile = tiles[r_key]
|
|
for i in range(4):
|
|
if bottom_border != get_top_border(found_tile):
|
|
found_tile = rotate_right(found_tile)
|
|
else:
|
|
break
|
|
|
|
if bottom_border != get_top_border(found_tile):
|
|
found_tile = flip_left_to_right_image(found_tile)
|
|
for i in range(4):
|
|
if bottom_border != get_top_border(found_tile):
|
|
found_tile = rotate_right(found_tile)
|
|
else:
|
|
break
|
|
tiles[r_key] = found_tile
|
|
break
|
|
return found_key
|
|
|
|
|
|
def build_image_from(tiles, image_tiles):
|
|
tile_size = 10
|
|
lines = []
|
|
for rows in image_tiles:
|
|
for t in range(tile_size-2):
|
|
lines.append(''.join([tiles[col][t+1][1:-1] for col in rows]))
|
|
return lines
|
|
|
|
|
|
def build_image(tiles, corners, border_tiles, inner):
|
|
corner_keys = list(corners.keys())
|
|
first_corner_key = corner_keys[0]
|
|
first_corner_tile = tiles[first_corner_key]
|
|
first_corner_borders = corners[first_corner_key]
|
|
del corners[first_corner_key]
|
|
|
|
first_corner_tile = orientation_corner_top_left(first_corner_tile, first_corner_borders)
|
|
tiles[first_corner_key] = first_corner_tile
|
|
|
|
top_tiles = build_top_from_left(tiles, first_corner_key, border_tiles, corners)
|
|
|
|
width = len(top_tiles)
|
|
height = len(tiles) // width
|
|
|
|
remaining = set(tiles.keys()).difference(set(top_tiles))
|
|
|
|
image_tiles = [top_tiles]
|
|
|
|
for h in range(height-1):
|
|
row = []
|
|
for w in range(width):
|
|
cur_above_key = image_tiles[h][w]
|
|
cur_above = tiles[cur_above_key]
|
|
bottom_border = get_bottom_border(cur_above)
|
|
|
|
key = find_tile_for_bottom_border(tiles, bottom_border, remaining)
|
|
remaining.remove(key)
|
|
row.append(key)
|
|
|
|
image_tiles.append(row)
|
|
|
|
image = build_image_from(tiles, image_tiles)
|
|
# image = flip_left_to_right_image(image)
|
|
# image = rotate_right(rotate_right(rotate_right(image)))
|
|
#
|
|
# for i in image:
|
|
# print(i)
|
|
return image
|
|
|
|
|
|
sea_monster = [' # ',
|
|
'# ## ## ###',
|
|
' # # # # # # ']
|
|
|
|
def sea_monster_as_offset():
|
|
global sea_monster
|
|
sea_monster_offset = []
|
|
for row in range(len(sea_monster)):
|
|
for col in range(len(sea_monster[row])):
|
|
if sea_monster[row][col] == '#':
|
|
sea_monster_offset.append((row, col))
|
|
return sea_monster_offset
|
|
|
|
|
|
def find_sea_monster(image, sea_monster_offsets):
|
|
rows = len(image)
|
|
cols = len(image[0])
|
|
sm_rows = len(sea_monster)
|
|
sm_cols = len(sea_monster[0])
|
|
for row in range(rows - sm_rows):
|
|
for col in range(cols - sm_cols):
|
|
if all([image[row + offset[0]][col + offset[1]] in ('#', 'O') for offset in sea_monster_offsets]):
|
|
for offset in sea_monster_offsets:
|
|
# image[row + offset[0]][col + offset[1]] = 'O'
|
|
temp = list(image[row + offset[0]])
|
|
temp[col + offset[1]] = '0'
|
|
image[row + offset[0]] = ''.join(temp)
|
|
return image
|
|
|
|
|
|
def check_all_orientations_for_sm(image, sea_monster_offsets):
|
|
for i in range(4):
|
|
image = find_sea_monster(image, sea_monster_offsets)
|
|
image = rotate_right(image)
|
|
image = flip_left_to_right_image(image)
|
|
for i in range(4):
|
|
image = find_sea_monster(image, sea_monster_offsets)
|
|
image = rotate_right(image)
|
|
return image
|
|
|
|
|
|
tiles = read_tiles()
|
|
|
|
corners, borders, inner = find_corners(tiles)
|
|
|
|
res = reduce(lambda x, y: x * y, [key for key in corners.keys()])
|
|
|
|
print(res)
|
|
|
|
image = build_image(tiles, corners, borders, inner)
|
|
sea_monster_offsets = sea_monster_as_offset()
|
|
|
|
image = check_all_orientations_for_sm(image, sea_monster_offsets)
|
|
|
|
res = 0
|
|
for line in image:
|
|
res += sum([c == '#' for c in line])
|
|
|
|
print(res)
|