DEV Community

loading...

Advent of Code 2020: Python Solution Day 20

Viper
Passionate ML and Game Dev learner from Nepal who loves sharing what he knows via blogging.
・2 min read

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
Enter fullscreen mode Exit fullscreen mode

Discussion (0)