advent2020/twenty.py

#!/usr/bin/env python3
from functools import reduce
import re, sys
import math
import numpy as np

dirs = 'north west south east'.split() # for printing

monster = '''
                  # 
#    ##    ##    ###
 #  #  #  #  #  #   
'''
monster = monster.replace('\n', '')
monstermask = reduce(lambda a, b: a*2 + (b == '#'), (0, *list(monster)))
mw, mh = 20, 3
monsterbegone = np.array([c == ' ' for c in monster], dtype=int).reshape((mh, mw))

def pic2bits(pic):
    #p(pic)
    pic = pic.reshape(-1)
    return reduce(lambda a, b: a*2 + b, (0, *list(pic)))


def p(image):
    for y in range(image.shape[0]):
        for x in range(image.shape[1]):
            sys.stdout.write('.#'[image[y][x]])
        print()
    print()

def tile(p):
    '''
    pair:
        ID
        tile, as given to us
    '''
    lines = p.strip().split('\n')
    return (int(lines[0][5:-1]),
            np.asarray([[x == '#' for x in l] for l in lines[1:]], dtype=int))

def edgeid(ar):
    '''
    boolean 10-tuple -> int({0,1023})
    '''
    return reduce(lambda a, b: a*2 + b, (0, *ar))

def edges(ar):
    '''
    the four 10-tuples making up the edge of a tile
    in ANTICLOCKWISE (i.e. unique) order
    '''
    return (ar[0], ar[:,0][::-1], ar[9][::-1], ar[:,9])

def flippededgeid(id):
    #print(f'{id:b}'.zfill(19))
    #print(f'{id:b}'[::-1])
    #print(int(f'{id:b}'[::-1], base=2))
    return int(f'{id:b}'.zfill(10)[::-1], base=2)

def addedge(d, e, t):
    '''
    put tile id t
    in dictionary d
    under the heading of edge e
    (do this for the flipped edge too)
    '''
    d[edgeid(e)] += [t, ]

def findpiece(cand, north=None, west=None, south=None, east=None):
    if west:
        cand = filter(lambda c:
                c[2][1] == flippededgeid(west[2][3]) and
                c[0] != west[0],
                cand)
    else:
        cand = None
    return list(cand)

def findpieceat(cand, board, x, y):
    N, W, S, E = board[y-1][x], board[y][x-1], board[y+1][x], board[y][x+1]
    for i, d in enumerate((N, W, S, E)):
        if d:
            #print('d is %s of x=%s y=%s' % (dirs[i], x, y))
            #print('d`s %sern edge is %s so c needs %s %s' % (dirs[(i+2)%4],
            #    d[2][(i+2)%4], flippededgeid(d[2][(i+2)%4]), dirs[i]))
            cand = list(filter(lambda c:
                    c[2][i] == flippededgeid(d[2][(i+2)%4]) and
                    c[0] != d[0],
                    cand)) # convert to list immediately, for some reason
    return list(cand)

def num_monsters(image):
    tot = 0
    for y in range(image.shape[0] - mh + 1):
        for x in range(image.shape[1] - mw + 1):
            #print(pic2bits(image[y:y+mh,x:x+mw]))
            if pic2bits(image[y:y+mh,x:x+mw]) & monstermask == monstermask:
                #p(image[y:y+mh,x:x+mw])
                tot += 1
    return tot

fn = sys.argv[1] if len(sys.argv) > 1 else 'input%s' % 20
with open(fn) as f:

    pgphs = f.read().strip().split('\n\n')
    w = round(math.sqrt(len(pgphs))) # lol genericism
    tiles = {k: v for k, v in [tile(p) for p in pgphs]}

    part1dic = {k: [] for k in range(1024)} # {edge: tileid}
    for id, t in tiles.items():
        for edge in [*edges(t), *edges(t[::-1])]: # reg, flipped
            addedge(part1dic, edge, id)

    edge_by_id = {k: [] for k in range(10000)} # {tileid: edge (only one tile has edge)}
    for k, v in filter(lambda a: len(a[1]) == 1, part1dic.items()):
        iv = v[0]
        edge_by_id[iv] += [k, ]
    #print({k: v for k, v in filter(lambda a: len(a[1]) == 4, edge_by_id.items())})
    print(np.prod([k for k, v in filter(lambda a: len(a[1]) == 4, edge_by_id.items())]))

    # continued in part 2

    # make huge list containing the following:
    # [tid, image, edges (4 of them), flip=False, k=0]
    # for all 8 combos
    pile = []
    for id, t in tiles.items():
        for k in range(4):
            toy = np.rot90(t, k)
            pile += [(id, toy, [edgeid(e) for e in edges(toy)], False, k), ]
            # when doing both, flip first
            toy = t[::-1]
            toy = np.rot90(toy, k)
            pile += [(id, toy, [edgeid(e) for e in edges(toy)], False, k), ]

    print('pieces in pile:', len(pile))

    # construct puzzle, store in grid similar to pile

    # begin with a corner
    rootid = list(filter(lambda a: len(a[1]) == 4, edge_by_id.items()))[0][0]
    toy = tiles[rootid]
    puzzle = np.empty((12, 12), dtype=object)
    # rotate so that N and W are unique
    for k in range(4):
        N = edges(toy)[0]
        W = edges(toy)[1]
        if len(part1dic[edgeid(N)]) == 1 and len(part1dic[edgeid(W)]) == 1:
            puzzle[0][0] = (rootid, toy, [edgeid(e) for e in edges(toy)], False, k)
            break
        toy = np.rot90(toy) # anticlockwise, naturally
    print(puzzle[0][0])
    puzzle = np.pad(puzzle, 1, mode='empty')

    # find next pieces
    for y in range(1, w+1):
        for x in range(1, w+1):
            if y + x == 2:
                sys.stdout.write(str(puzzle[y][x][0]) + ' ')
                continue
            match = findpieceat(pile, puzzle, x, y)
            if len(match) != 1:
                print('ACHTUNG: duplicate matches: %s' % len(match))
            puzzle[y][x] = match[0]
            sys.stdout.write(str(puzzle[y][x][0]) + ' ')
        print()

    # stitch together full map
    image = np.zeros((8*w, 8*w), dtype=int)
    for (y, x), chunk in np.ndenumerate(puzzle[1:1+w,1:1+w]):
        image[y*8:(y+1)*8,x*8:(x+1)*8] = chunk[1][1:9,1:9]
    image = np.rot90(image, 2)
    for pic in image, image[::-1]:
        for rot in range(4):
            if num_monsters(np.rot90(pic, rot)) > 0:
                image = np.rot90(pic, rot)
                break
    p(image)

    print(image.sum())
    for y in range(image.shape[0] - mh + 1):
        for x in range(image.shape[1] - mw + 1):
            #print(pic2bits(image[y:y+mh,x:x+mw]))
            if pic2bits(image[y:y+mh,x:x+mw]) & monstermask == monstermask:
                image[y:y+mh,x:x+mw] &= monsterbegone
    print(image.sum())