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 = {} for tile in open('day20.txt').read().split('\n\n'): lines = tile.strip().split('\n') tile_id = int(re.fullmatch(r'Tile (\d+):', lines[0]).group(1)) rows = lines[1:] tiles[tile_id] = group(rows) n = int(math.sqrt(len(tiles))) arranged = [[0] * 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[0][0][0] * arranged[-1][0][0] * arranged[0][-1][0] * arranged[-1][-1][0]) 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][-1] != tile[0]: continue if c > 0: if list(row[-1] for row in arranged[r][c - 1][1]) != list( row[0] 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[1]) for tile in row] for row in arranged] tile_n = len(board[0][0]) 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[0]) - len(pattern[0]) + 1): matches += all(pattern[r][c] == ' ' or board[r + dr][c + dc] == '#' for r in range(len(pattern)) for c in range(len(pattern[0]))) if matches: print(''.join(board).count('#') - ''.join(pattern).count('#') * matches) break 
Top comments (0)