rectangle and a list of the (x, y) coordinates
# of occupied unit squares within it, return a dictionary of the
# other squares that are edge connected to each square
def adjacent(m, n, sqs):
adj = dict()
for (x, y) in sqs:
s = set()
for xx in (x - 1, x + 1):
if 0 <= xx < m and (xx, y) in sqs:
s.add((xx, y))
for yy in (y - 1, y + 1):
if 0 <= yy < n and (x, yy) in sqs:
s.add((x, yy))
adj[(x, y)] = s
return adj
# normalise a set of (x, y) coordinates for a piece so that the
# minimum x and y values are both zero and record the x and y
# sizes of the enclosing rectangle
def normalise(piece):
x_min = min(x for (x, y) in piece)
x_max = max(x for (x, y) in piece)
y_min = min(y for (x, y) in piece)
y_max = max(y for (x, y) in piece)
return (tuple(sorted(((x - x_min, y - y_min) for (x, y) in piece))),
(x_max - x_min + 1, y_max - y_min + 1))
# generate and return a tuple giving the data for each different
# orientation of a piece; only orintations that put pieces in
# different positions are recorded but flags are added to denote
# the orientations to which the recorded data applies - flags of
# 1, 2, 4 and 8 apply to rotations of 0, 90, 180 and 270 degrees
# and 16, 32, 64 and 128 to the same rotations after being turned
# over; these flags are added together for orientation data that
# represents more than one orientation
def orientate(piece, two_sided=False):
v = defaultdict(int)
t, m = tm = normalise(piece)
v[tm] |= 1
# rotate the shape into three 90 degree positions
for i in range(3):
t, m = tm = normalise(tuple((y, -x) for (x, y) in t))
v[tm] |= 2 * 2 ** i
u = v.copy()
# turn it over
t, m = tm = normalise(tuple((x, -y) for (x, y) in piece))
v[tm] |= 16
# and rotate this shape into three 90 degree positions
for i in range(3):
t, m = tm = normalise(tuple((y, -x) for (x, y) in t))
v[tm] |= 32 * 2 ** i
# the piece is chiral if turning it over adds orientations
ff = 0 if v.keys() == u.keys() else CH
# only include 'turned over' orientations if two_sided
w = v if two_sided else u
return tuple(sorted((tm + (f|ff,) for tm, f in w.items()), key=lambda x:x[2]))
# given a set of (x, y) positions for unit squares arranged
# on a rectangular grid, return true if the set of squares form
# a connected region
def connected(p, adj):
# if two sets of squares in a list of such sets have
# any squares that are connected, combine the two sets
def combine(s):
for s1, s2 in combinations(s, 2):
if any(y in adj[x] for x in s1 for y in s2):
s[s.index(s1)].update(s2)
s.remove(s2)
return True
return False
sets = [set([n]) for n in p]
# combine any sets that have connected members
while combine(sets):
pass
# are all squares connected?
return len(sets) == 1
# compile a list of connected shapes that can be formed
# from an by grid of unit squares
def generate_pieces(m, n, use_all=True, two_sided=False, max_sq=0):
pieces = set()
mx = m * n + (1 if use_all else 0)
if max_sq:
mx = min(mx, max_sq + 1)
for n_sq in range(1, mx):
sq_list = [(x, y) for x in range(m) for y in range(n)]
for sqs in combinations(sq_list, n_sq):
adj = adjacent(m, n, sqs)
if connected(sqs, adj):
# have we seen this piece before?
tc, mc = normalise(sqs)
for p in pieces:
if any(t == tc and m == mc for t, m, f in p):
break
else:
pieces.add(orientate(sqs, two_sided))
dsh = dict()
for i, s in enumerate(sorted(pieces, key=lambda t: len(t[0][0]))):
dsh[chr(ord('A') + i)] = s
return dsh
def print_pieces(pieces, text=False, pad=''):
s = []
for p in pieces.keys():
if text:
s.append(f"{p}:\n")
for t, mn, f in pieces[p]:
fs = []
for i in range(9):
if f & 2 ** i:
fs.append('R0 R1 R2 R3 M0 M1 M2 M3 CH'.split()[i])
s.append(f" {t}, {mn}, {'|'.join(fs)}\n")
else:
t, mn, f = pieces[p][0]
s.append(f"{p}:{'CH' if f & CH else 'AC'}\n")
g = [[' ' for x in range(mn[0])] for y in range(mn[1])]
for x, y in t:
g[y][x] = p
for y in range(mn[1]):
s.append(' |' + pad.join(f'{g[y][x]}' for x in range(mn[0])) + '|\n')
print(''.join(s), end='')
# generate sets of that are described in the
# dictionary whose combined area is and,
# if and are set as keyword inputs, all fit
# have in an by rectangle; sets the
# minimum number of pieces used (default 1), max_pc
# sets the maximum (default all)
def select_pieces(area, pieces, dsh, min_pc=1, max_pc=None, **kw):
mn = None
if kw:
if (m := kw.get('m', None)) and (n := kw.get('n', None)):
mn = sorted((m, n))
max_pc = len(pieces) if max_pc is None else max_pc
for np in range(min_pc, max_pc + 1):
for cp in combinations(pieces, np):
t = sum(len(dsh[i][0][0]) for i in cp)
if t == area and (mn is None or
all(min(s) <= mn[0] and max(s) <= mn[1]
for s in dsh[i][0][1]) for i in cp):
yield cp
# fit a set of pieces specifed in the directory
# into a rectangle of size by and return filled
# rectangles as one dimensional arrays in which the name
# of the piece at (x, y) is in array element (x + m * y)
def solve_rect(pieces, m, n, dsh, gr=None):
if gr == None:
gr = [0] * m * n
# look for an empty point in the grid - check at (x, y)
# points rather than checking in g as a one-dimensional
# array as this gives much better performance
for x, y in product(range(m), range(n)):
if not gr[x + m * y]:
break
else:
# the grid is full
yield tuple(gr)
return
z = x + m * y
for p in pieces:
for lsq, (mx, my), _ in dsh[p]:
# check that the card lies within the rectangle
if x + mx > m or y + my > n:
continue
# check all grid squares the piece will cover are empty
if any(gr[z + dx + m * dy] for dx, dy in lsq):
continue
# place the piece in the grid
for dx, dy in lsq:
gr[z + dx + m * dy] = p
# continue to the next pieces
nu = tuple(x for x in pieces if x != p)
yield from solve_rect(nu, m, n, dsh, gr)
# remove the piece from the grid
for dx, dy in lsq:
gr[z + dx + m * dy] = 0
# Donald Knuth's Algorithm X ('dancing links') for cover problems
# see https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
def dance(X, Y, solution=[]):
if not X:
yield list(solution)
else:
c = min(X, key=lambda c: len(X[c]))
for r in list(X[c]):
solution.append(r)
# select columns
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
for s in dance(X, Y, solution):
yield s
# deselect columns
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
solution.pop()
# using Donald Knuth's Algorithm X, fit a set of pieces
# specifed in the directory into a rectangle of
# size by and return filled rectangles as one
# dimensional arrays in which the name of the piece at
# (x, y) is in array element (x + m * y)
def solve_rectx(pieces, m, n, dsh):
pieces = list(pieces)
np = len(pieces)
mn = m * n
Y = list()
for i, p in enumerate(pieces, start=mn):
for q, (mx, my), _ in dsh[p]:
for y in range(n - my + 1):
for x in range(m - mx + 1):
s = []
for dx, dy in q:
u, v = x + dx, y + dy
s.append(u + m * v)
s.append(i)
Y.append(s)
X = {k:set() for k in range(np + mn)}
for i, s in enumerate(Y):
for k in s:
X[k].add(i)
for rs in dance(X, Y, []):
g = [None] * mn
for r in rs:
piece = pieces[Y[r][-1] - mn]
for i in Y[r][:-1]:
g[i] = piece
yield tuple(g)
# output a filled grid with lines having
# as a prefix, as a suffix and grid
# points being separated with
def print_rect(g, m, n, pfx = '', pad='', sfx=''):
s = []
for y in range(n):
l = ''.join(f'{g[x + m * y]}{pad}' for x in range(m))
s.append(''.join((pfx, l, sfx, '\n')))
print(''.join(s))