# Advent of Code 2020: Python Solution Day 20

This is the most hardest challenge and I again could not find solution by myself. So I had to cheat instead. And it is pretty known that today's challenge took nearly 20 minutes for fastest solution too. All the credit goes to the author.

I will update his code to make it work on NumPy because it is more faster to do transpose and indexing than general list. I will update this blog soon.

``````import math
import re

def transposed(tile):
return list(''.join(row) for row in zip(*tile))

def reversed_tile(tile):
return [''.join(reversed(row)) for row in tile]

def rotations(tile):
ans = [tile]
for _ in range(3):
ans.append(reversed_tile(transposed(ans[-1])))
return ans

def group(tile):
return rotations(tile) + rotations(transposed(tile))

tiles = {}
lines = tile.strip().split('\n')
tile_id = int(re.fullmatch(r'Tile (\d+):', lines).group(1))
rows = lines[1:]
tiles[tile_id] = group(rows)

n = int(math.sqrt(len(tiles)))
arranged = [ * n for _ in range(n)]
stack = list(reversed(list((r, c) for c in range(n) for r in range(n))))

def solve():
if not stack:
print(arranged * arranged[-1] * arranged[-1] *
arranged[-1][-1])
return True
(r, c) = stack.pop()
for tile_id in list(tiles):
tile_group = tiles[tile_id]
del tiles[tile_id]
for tile in tile_group:
if r > 0:
if arranged[r - 1][c][-1] != tile:
continue
if c > 0:
if list(row[-1] for row in arranged[r][c - 1]) != list(
row for row in tile):
continue
arranged[r][c] = (tile_id, tile)
if solve():
return True
tiles[tile_id] = tile_group
stack.append((r, c))

solve()

def remove_border(tile):
return [row[1:-1] for row in tile[1:-1]]

board = [[remove_border(tile) for tile in row] for row in arranged]
tile_n = len(board)

def get(r, c):
return board[r // tile_n][c // tile_n][r % tile_n][c % tile_n]

board = [
''.join(get(r, c) for c in range(n * tile_n)) for r in range(n * tile_n)
]
for pattern in group(
['                  # ', '#    ##    ##    ###', ' #  #  #  #  #  #   ']):
matches = 0
for dr in range(len(board) - len(pattern) + 1):
for dc in range(len(board) - len(pattern) + 1):
matches += all(pattern[r][c] == ' ' or board[r + dr][c + dc] == '#'
for r in range(len(pattern))
for c in range(len(pattern)))
if matches:
print(''.join(board).count('#') -
''.join(pattern).count('#') * matches)
break
``````