187 lines
5.9 KiB
Python
Executable File
187 lines
5.9 KiB
Python
Executable File
#!/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)
|
|
p(image)
|
|
for pic in image, image[::-1]:
|
|
for rot in range(4):
|
|
if num_monsters(np.rot90(pic, rot)) > 0:
|
|
image = np.rot90(pic, rot)
|
|
|
|
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())
|