aoc-2020/20.py

from math import sqrt
lines = []

with open("20.input") as f:
    for line in f.readlines():
        lines.append(line.strip())

def parse(lines):
    tiles = []
    fragments = []
    id = None
    for line in lines:
        if line.startswith("Tile"):
            id = int(line[5:-1])
        elif line == "":
            if fragments == []:
                continue
            tiles.append((id, fragments))
            fragments = []
        else:
            fragments.append(list(line))
    return tiles


def column(fragments, i):
    return [row[i] for row in fragments]


def rotate_90(fragments):
    return [reverse_of(column(fragments, i)) for i in range(0, len(fragments))]


def all_rotations(grid):
    rotations = []
    for i in range(0, 4):
        grid = rotate_90(grid)
        rotations.append(grid)
    return rotations


def all_orientations(grid):
    return all_rotations(grid) + all_rotations(reverse_of(grid))


def all_sides(fragments):
    sides = [fragments[0], fragments[-1], column(fragments, 0), column(fragments, -1)]
    sides += [reverse_of(side) for side in sides]
    return sides


def reverse_of(l):
    l2 = list(l)
    l2.reverse()
    return l2


def valid_orientations(tile, left, right, top, bottom):
    result = []
    for orientation in all_orientations(tile[1]):
        if left != None and column(orientation, 0) not in left:
            continue
        elif right != None and column(orientation, -1) not in right:
            continue
        elif top != None and orientation[0] not in top:
            continue
        elif bottom != None and orientation[-1] not in bottom:
            continue
        else:
            result.append(orientation)
    return result


def possible_orders(prefix, width, tiles, uniq_sides):
    index = len(prefix)
    if index == width * width:
        return [prefix]
    left = None
    right = None
    top = None
    bottom = None
    result = []
    if index >= width:
        # Must match above tile
        top = [prefix[index - width][-1]]
    if index % width != 0:
        # Must match left tile
        left = [column(prefix[-1], -1)]
    if index in [0, width - 1, width * (width - 1), width * width - 1]:
        key = "corner"
    elif index < width or index > width * (width - 1) or index % width in [0, width - 1]:
        key = "edge"
    else:
        key = "center"
    for tile in tiles[key]:
        if index % width == 0:
            left = uniq_sides[tile[0]]
        if int(index / width) == 0:
            top = uniq_sides[tile[0]]
        if index % width == width - 1:
            right = uniq_sides[tile[0]]
        for valid in valid_orientations(tile, left, right, top, bottom):
            tiles_next = dict(tiles)
            tiles_next[key] = [t for t in tiles[key] if t != tile]
            result += possible_orders(prefix + [valid], width, tiles_next, uniq_sides)
    return result


tiles = parse(lines)

sides = [(side, tile[0]) for tile in tiles for side in all_sides(tile[1])]
uniq_sides = {}
counts = {}
for (side, tile_id) in sides:
    same_side = len([1 for (s, id) in sides if s == side])
    if same_side == 1:
        count = counts.get(tile_id, 0)
        count += 1
        counts[tile_id] = count
        uniq = uniq_sides.get(tile_id, [])
        uniq.append(side)
        uniq_sides[tile_id] = uniq

corners = []
edges = []
prod = 1

for (k, v) in counts.items():
    if v == 4:
        prod *= k
        corners += [tile for tile in tiles if tile[0] == k]
    elif v == 2:
        edges += [tile for tile in tiles if tile[0] == k]

print("Answer 1:", prod)

center = [tile for tile in tiles if tile not in corners and tile not in edges]
width = int(sqrt(len(tiles)))
first_corner = corners.pop()
valid_corner = valid_orientations(first_corner, uniq_sides[first_corner[0]], None, uniq_sides[first_corner[0]], None)[0]
orders = possible_orders([valid_corner], width, {'center': center, 'edge': edges, 'corner': corners}, uniq_sides)
assert len(orders) == 1

def strip_borders(frags):
    return [row[1:-1] for row in frags[1:-1]]

assert strip_borders([[1, 2, 3], [4,5,6], [7,8,9]]) == [[5]]

map = []
order = orders[0]
while len(order) > 0:
    row = [strip_borders(frags) for frags in order[0:width]]
    for i in range(0, len(row[0])):
        map.append(list(''.join([''.join(frags[i]) for frags in row])))
    del order[0:width]

sea_monster = ["                  # ",
               "#    ##    ##    ###",
               " #  #  #  #  #  #   "]

sea_monster = [list(row) for row in sea_monster]

def check_monster(map, x, y, monster):
    for local_x in range(0, len(monster[0])):
        for local_y in range(0, len(monster)):
            if monster[local_y][local_x] == '#' and map[y + local_y][x + local_x] != '#':
                return False
    return True

def paint_monster(map, x, y, monster):
    for local_x in range(0, len(monster[0])):
        for local_y in range(0, len(monster)):
            if monster[local_y][local_x] == '#':
                map[y + local_y][x + local_x] = 'O'
    return map

def search_map(map):
    map_width = len(map[0])
    map_height = len(map)
    monster = sea_monster

    found = False
    for x in range(0, map_width - len(monster[0])):
        for y in range(0, map_height - len(monster)):
            if check_monster(map, x, y, monster):
                found = True
                map = paint_monster(map, x, y, monster)
    if found:
        return map
    else:
        return None

def print_map(map):
    for row in map:
        print(''.join(row))

for map in all_orientations(map):
    map = search_map(map)
    if map != None:
        print("Answer 2:", len([1 for row in map for c in row if c == '#']))