"""Constraint solvers for tile assemblies.
``wave_function_collapse``
Random compatible assemblies of any size: arc consistency (each tile left in the
domain of a cell has a compatible tile in every neighbouring domain), then cells of
least entropy are given a tile at random (with the tile weights) and the choice is
propagated, backtracking on contradictions (domains are bit sets, Numba).
``TransferMatrix``
Exact counting and exact uniform sampling of the compatible assemblies of a box,
with a transfer matrix between the admissible cross-sections along x (statistical
physics). It needs few admissible cross-sections: small sections, or constrained
tile sets.
``count_polarized_blocks``
Exact number of compatible assemblies of polarized blocks, for larger boxes: the
strain sign along every line of blocks alternates, which reduces the problem to
sign variables on the faces of the box (a gauge), summed by dynamic programming.
"""
from __future__ import annotations
import math
import numpy as np
from numba import njit
from scipy import sparse
from morphogen.design.tiles import TileSet
MAX_TILES = 64 # bit sets of 64 bits
# -- wave function collapse ----------------------------------------------------------------
@njit(cache=True)
def _popcount(x):
x = x - ((x >> np.uint64(1)) & np.uint64(0x5555555555555555))
x = (x & np.uint64(0x3333333333333333)) + ((x >> np.uint64(2)) & np.uint64(0x3333333333333333))
x = (x + (x >> np.uint64(4))) & np.uint64(0x0F0F0F0F0F0F0F0F)
return int((x * np.uint64(0x0101010101010101)) >> np.uint64(56))
@njit(cache=True)
def _propagate(
dom,
sw,
swl,
nb,
allowed,
w,
wlogw,
n_tiles,
stack,
n_stack,
in_stack,
trail_c,
trail_d,
trail_w,
trail_l,
n_trail,
):
"""Arc consistency from the cells on the stack; returns (ok, n_trail)."""
one = np.uint64(1)
while n_stack > 0:
n_stack -= 1
c = stack[n_stack]
in_stack[c] = 0
dc = dom[c]
for d in range(6):
q = nb[c, d]
if q < 0:
continue
sup = np.uint64(0)
for t in range(n_tiles):
if (dc >> np.uint64(t)) & one:
sup |= allowed[d, t]
old = dom[q]
new = old & sup
if new == old:
continue
if new == 0:
# leave the stack clean for the next propagation
while n_stack > 0:
n_stack -= 1
in_stack[stack[n_stack]] = 0
return False, n_trail
trail_c[n_trail] = q
trail_d[n_trail] = old
trail_w[n_trail] = sw[q]
trail_l[n_trail] = swl[q]
n_trail += 1
removed = old & ~new
for t in range(n_tiles):
if (removed >> np.uint64(t)) & one:
sw[q] -= w[t]
swl[q] -= wlogw[t]
dom[q] = new
if not in_stack[q]:
stack[n_stack] = q
n_stack += 1
in_stack[q] = 1
return True, n_trail
@njit(cache=True)
def _undo(dom, sw, swl, trail_c, trail_d, trail_w, trail_l, n_trail, target):
while n_trail > target:
n_trail -= 1
c = trail_c[n_trail]
dom[c] = trail_d[n_trail]
sw[c] = trail_w[n_trail]
swl[c] = trail_l[n_trail]
return n_trail
@njit(cache=True)
def _wfc(dom, nb, allowed, w, n_tiles, prio, rng, max_backtracks):
"""Search from the domains ``dom`` (modified in place). Status: 1 solved, 0 gave up
(too many backtracks), -1 no solution."""
n = dom.size
one = np.uint64(1)
wlogw = np.zeros(n_tiles)
for t in range(n_tiles):
if w[t] > 0:
wlogw[t] = w[t] * math.log(w[t])
sw = np.zeros(n)
swl = np.zeros(n)
for c in range(n):
for t in range(n_tiles):
if (dom[c] >> np.uint64(t)) & one:
sw[c] += w[t]
swl[c] += wlogw[t]
size = n * (n_tiles + 1) + 1
trail_c = np.empty(size, dtype=np.int64)
trail_d = np.empty(size, dtype=np.uint64)
trail_w = np.empty(size)
trail_l = np.empty(size)
stack = np.empty(n, dtype=np.int64)
in_stack = np.zeros(n, dtype=np.uint8)
n_stack = 0
for c in range(n):
if dom[c] == 0:
return -1
stack[n_stack] = c
n_stack += 1
in_stack[c] = 1
ok, n_trail = _propagate(
dom,
sw,
swl,
nb,
allowed,
w,
wlogw,
n_tiles,
stack,
n_stack,
in_stack,
trail_c,
trail_d,
trail_w,
trail_l,
0,
)
if not ok:
return -1
n_trail = 0 # the initial reduction is never undone
dec_cell = np.empty(n, dtype=np.int64)
dec_tried = np.zeros(n, dtype=np.uint64)
dec_trail = np.zeros(n, dtype=np.int64)
depth = 0
backtracks = 0
while True:
best = -1
best_h = np.inf
for c in range(n):
if _popcount(dom[c]) > 1:
h = math.log(sw[c]) - swl[c] / sw[c] + 1e-7 * prio[c]
if h < best_h:
best_h = h
best = c
if best < 0:
return 1
dec_cell[depth] = best
dec_tried[depth] = 0
dec_trail[depth] = n_trail
depth += 1
while True:
k = depth - 1
n_trail = _undo(dom, sw, swl, trail_c, trail_d, trail_w, trail_l, n_trail, dec_trail[k])
c = dec_cell[k]
options = dom[c] & ~dec_tried[k]
total = 0.0
for t in range(n_tiles):
if (options >> np.uint64(t)) & one:
total += w[t]
if total <= 0.0:
depth -= 1
backtracks += 1
if depth == 0:
return -1
if backtracks > max_backtracks:
return 0
continue
r = rng.random() * total
choice = -1
for t in range(n_tiles):
if (options >> np.uint64(t)) & one:
choice = t
r -= w[t]
if r < 0.0:
break
bit = one << np.uint64(choice)
dec_tried[k] |= bit
trail_c[n_trail] = c
trail_d[n_trail] = dom[c]
trail_w[n_trail] = sw[c]
trail_l[n_trail] = swl[c]
n_trail += 1
dom[c] = bit
sw[c] = w[choice]
swl[c] = wlogw[choice]
stack[0] = c
in_stack[c] = 1
ok, n_trail = _propagate(
dom,
sw,
swl,
nb,
allowed,
w,
wlogw,
n_tiles,
stack,
1,
in_stack,
trail_c,
trail_d,
trail_w,
trail_l,
n_trail,
)
if ok:
break
def _neighbours(shape, periodic: bool, dims: int) -> np.ndarray:
"""Index of the neighbour of every cell in the directions -x, +x, -y, +y, -z, +z
(-1: none)."""
idx = np.arange(int(np.prod(shape))).reshape(shape)
nb = np.full((idx.size, 6), -1, dtype=np.int64)
for a in range(dims):
for side, step in ((0, 1), (1, -1)):
rolled = np.roll(idx, step, axis=a) # side 0: value at i-1; side 1: at i+1
ok = np.ones(shape, dtype=bool)
if not periodic:
edge = [slice(None)] * 3
edge[a] = 0 if side == 0 else -1
ok[tuple(edge)] = False
if shape[a] == 1 and not periodic:
ok[:] = False
nb[:, 2 * a + side] = np.where(ok, rolled, -1).ravel()
return nb
def _allowed_bits(tileset: TileSet) -> np.ndarray:
"""``allowed[d, t]``: bit set of the tiles allowed next to tile t in direction d."""
n = tileset.n_tiles
compat = tileset.compatibility()
bits = (np.uint64(1) << np.arange(n, dtype=np.uint64)).astype(np.uint64)
allowed = np.zeros((6, n), dtype=np.uint64)
for a in range(3):
allowed[2 * a + 1] = np.bitwise_or.reduce(np.where(compat[a], bits[None, :], 0), axis=1)
allowed[2 * a] = np.bitwise_or.reduce(np.where(compat[a].T, bits[None, :], 0), axis=1)
return allowed
[docs]
def initial_domains(
tileset: TileSet, shape, *, periodic: bool = True, boundary=None, allowed=None
) -> np.ndarray:
"""Boolean domains ``(n0, n1, n2, n_tiles)``: tiles of positive weight, restricted
by ``allowed`` (same shape) and, on the faces of non-periodic boxes, to tiles whose
outer faces match the label ``boundary``."""
shape = tuple(int(n) for n in shape)
dom = np.broadcast_to(tileset.weights > 0, (*shape, tileset.n_tiles)).copy()
if allowed is not None:
dom &= np.asarray(allowed, dtype=bool).reshape(dom.shape)
if boundary is not None and not periodic:
for a in range(tileset.dims):
for side in (0, 1):
face = [slice(None)] * 3
face[a] = 0 if side == 0 else shape[a] - 1
dom[tuple(face)] &= tileset.boundary_tiles(a, side, boundary)
return dom
[docs]
def wave_function_collapse(
tileset: TileSet,
shape,
rng: np.random.Generator,
*,
periodic: bool = True,
boundary: int | None = None,
allowed=None,
max_backtracks: int | None = None,
restarts: int = 5,
) -> np.ndarray:
"""A random compatible assembly of ``shape`` tiles (``(n0, n1, 1)`` for planar sets).
``allowed`` (boolean, ``shape + (n_tiles,)``) restricts the tiles of each cell, e.g.
to grade a design in space; ``boundary`` is the label the outer faces of a
non-periodic box must match. Raises ValueError when no assembly exists, or when the
search gave up after ``restarts`` attempts of ``max_backtracks`` backtracks.
"""
if tileset.n_tiles > MAX_TILES:
raise ValueError(f"wave function collapse handles up to {MAX_TILES} tiles")
shape = tuple(int(n) for n in shape)
if len(shape) != 3 or min(shape) < 1:
raise ValueError("shape: three positive numbers of tiles")
if tileset.dims == 2 and shape[2] != 1:
raise ValueError("planar tile sets: shape (n0, n1, 1)")
dom_bool = initial_domains(
tileset, shape, periodic=periodic, boundary=boundary, allowed=allowed
)
bits = np.uint64(1) << np.arange(tileset.n_tiles, dtype=np.uint64)
dom0 = np.bitwise_or.reduce(np.where(dom_bool, bits, np.uint64(0)), axis=-1).ravel()
nb = _neighbours(shape, periodic, tileset.dims)
allowed_bits = _allowed_bits(tileset)
n_cells = dom0.size
limit = 10 * n_cells + 100 if max_backtracks is None else int(max_backtracks)
w = tileset.weights.astype(float)
for _ in range(max(1, int(restarts))):
dom = dom0.astype(np.uint64).copy()
prio = rng.random(n_cells)
status = _wfc(dom, nb, allowed_bits, w, tileset.n_tiles, prio, rng, limit)
if status == 1:
tiles = np.array([int(d).bit_length() - 1 for d in dom], dtype=np.int64)
return tiles.reshape(shape)
if status == -1:
raise ValueError("no compatible assembly exists for these tiles and constraints")
raise ValueError(
f"no compatible assembly found after {restarts} restarts of {limit} backtracks"
)
# -- transfer matrices ---------------------------------------------------------------------
@njit(cache=True)
def _enumerate_slices(n1, n2, n_tiles, compat, usable, periodic, max_states, out):
npos = n1 * n2
cur = np.full(npos, -1, dtype=np.int64)
count = 0
p = 0
while p >= 0:
cur[p] += 1
if cur[p] >= n_tiles:
cur[p] = -1
p -= 1
continue
t = cur[p]
if not usable[t]:
continue
j = p // n2
k = p % n2
if j > 0 and not compat[1, cur[p - n2], t]:
continue
if k > 0 and not compat[2, cur[p - 1], t]:
continue
if periodic and j == n1 - 1 and not compat[1, t, cur[k]]:
continue
if periodic and k == n2 - 1 and not compat[2, t, cur[j * n2]]:
continue
if p == npos - 1:
if count >= max_states:
return -1
for q in range(npos):
out[count, q] = cur[q]
count += 1
continue
p += 1
return count
[docs]
class TransferMatrix:
"""Admissible cross-sections ``(n1, n2)`` of a tile set and the transfer matrix
between consecutive sections along x (``T[s, s'] = 1`` when section s' may follow
section s).
Counting and sampling use exact integer arithmetic. Periodic boxes need the closed
walks of the transfer matrix (one sum per section): keep the number of sections
modest (``max_states``).
"""
def __init__(
self, tileset: TileSet, section, *, periodic: bool = False, max_states: int = 20000
):
self.tileset = tileset
self.section = (int(section[0]), int(section[1]))
if tileset.dims == 2 and self.section[1] != 1:
raise ValueError("planar tile sets: sections (n1, 1)")
self.periodic = bool(periodic)
n1, n2 = self.section
compat = tileset.compatibility()
out = np.empty((max_states, n1 * n2), dtype=np.int64)
count = _enumerate_slices(
n1,
n2,
tileset.n_tiles,
compat,
tileset.weights > 0,
self.periodic,
int(max_states),
out,
)
if count < 0:
raise ValueError(
f"more than {max_states} admissible sections: the box is too wide for "
"exact counting (use wave_function_collapse to sample)"
)
self.states = out[:count].copy()
self.matrix = self._build(compat[0])
def _build(self, compat_x) -> sparse.csr_matrix:
s = self.states
n = len(s)
rows, cols = [], []
block = max(1, 2_000_000 // max(1, n))
for start in range(0, n, block):
ok = np.ones((min(block, n - start), n), dtype=bool)
for c in range(s.shape[1]):
ok &= compat_x[s[start : start + block, c]][:, s[:, c]]
r, q = np.nonzero(ok)
rows.append(r + start)
cols.append(q)
r = np.concatenate(rows) if rows else np.empty(0, dtype=int)
q = np.concatenate(cols) if cols else np.empty(0, dtype=int)
return sparse.csr_matrix((np.ones(len(r), dtype=np.int8), (r, q)), shape=(n, n))
@property
def n_states(self) -> int:
return len(self.states)
def _step(self, v: np.ndarray) -> np.ndarray:
"""(T v)[s] = sum of v over the sections s' allowed after s (exact integers)."""
m = self.matrix
out = np.zeros(len(v), dtype=object)
nonempty = np.diff(m.indptr) > 0
if np.any(nonempty):
out[nonempty] = np.add.reduceat(v[m.indices], m.indptr[:-1][nonempty])
return out
def _backward(self, length: int, end=None) -> list[np.ndarray]:
"""b[k][s]: number of ways to complete the sections k+1..length-1 after section s
at position k (ending at section ``end`` when given)."""
n = self.n_states
last = np.ones(n, dtype=object)
if end is not None:
last = np.zeros(n, dtype=object)
# completions must end with a section followed by `end` (periodic closure)
col = self.matrix[:, end].toarray().ravel()
last[col > 0] = 1
b = [last]
for _ in range(length - 1):
b.append(self._step(b[-1]))
return b[::-1]
[docs]
def count(self, length: int) -> int:
"""Number of compatible assemblies of ``length`` sections (exact)."""
length = int(length)
if length < 1:
raise ValueError("length: at least 1")
if not self.periodic:
return int(self._backward(length)[0].sum())
return int(sum(self._closed_walks(length)))
def _closed_walks(self, length: int) -> list[int]:
"""Number of periodic assemblies starting with each section."""
out = []
for s in range(self.n_states):
b = self._backward(length, end=s)
out.append(int(b[0][s]))
return out
[docs]
def sample(self, length: int, rng: np.random.Generator) -> np.ndarray:
"""An assembly ``(length, n1, n2)`` drawn uniformly among the compatible ones."""
length = int(length)
if self.periodic:
weights = self._closed_walks(length)
first = _choose(weights, rng)
b = self._backward(length, end=first)
else:
b = self._backward(length)
first = _choose(list(b[0]), rng)
path = [first]
m = self.matrix
for k in range(1, length):
s = path[-1]
nxt = m.indices[m.indptr[s] : m.indptr[s + 1]]
path.append(int(nxt[_choose([b[k][q] for q in nxt], rng)]))
n1, n2 = self.section
return self.states[np.array(path)].reshape(length, n1, n2)
def _choose(weights, rng: np.random.Generator) -> int:
"""Index drawn with probability proportional to non-negative integer weights."""
total = int(sum(int(w) for w in weights))
if total <= 0:
raise ValueError("no compatible assembly")
nbits = total.bit_length()
while True: # uniform integer in [0, total) by rejection
r = int.from_bytes(rng.bytes((nbits + 7) // 8), "little") >> ((8 - nbits % 8) % 8)
if r < total:
break
for i, w in enumerate(weights):
r -= int(w)
if r < 0:
return i
return len(weights) - 1 # pragma: no cover
[docs]
def count_assemblies(
tileset: TileSet, shape, *, periodic: bool = False, max_states: int = 20000
) -> int:
"""Exact number of compatible assemblies of a box of ``shape`` tiles."""
shape = tuple(int(n) for n in shape)
tm = TransferMatrix(tileset, shape[1:], periodic=periodic, max_states=max_states)
return tm.count(shape[0])
# -- polarized blocks ----------------------------------------------------------------------
@njit(cache=True)
def _polarized_sum(nx, ny, nz):
"""Sum over the signs F_x(j, k) of R_0^ceil(nx/2) R_1^floor(nx/2) (see below)."""
n_fx = 1 << (ny * nz)
total = 0.0
exact = np.int64(0)
big = False
for fx in range(n_fx):
r = np.zeros(2, dtype=np.int64)
for parity in range(2):
acc = np.int64(0)
for y in range(1 << nz):
prod = np.int64(1)
for j in range(ny):
# c = 2 - |{X_k (-1)^k : X_k = Y_k}| for the column (i, j)
seen_p = False
seen_m = False
for k in range(nz):
xk = 1 if (fx >> (j * nz + k)) & 1 else -1
if parity:
xk = -xk
yk = 1 if (y >> k) & 1 else -1
if j % 2 == 1:
yk = -yk
if xk == yk:
v = xk if k % 2 == 0 else -xk
if v > 0:
seen_p = True
else:
seen_m = True
c = 2 - (1 if seen_p else 0) - (1 if seen_m else 0)
prod *= c
if prod == 0:
break
acc += prod
r[parity] = acc
term = 1.0
term_exact = np.int64(1)
for i in range(nx):
term *= float(r[i % 2])
term_exact *= r[i % 2]
total += term
exact += term_exact
if total > 2.0**62:
big = True
return exact, total, big
[docs]
def count_polarized_blocks(shape, *, periodic: bool = False) -> int:
"""Number of compatible assemblies of polarized blocks in a box of ``shape`` blocks.
Writing the strain signs of the block (i, j, k) as ``e_x = F_x(j, k) (-1)^i``,
``e_y = F_y(i, k) (-1)^j``, ``e_z = F_z(i, j) (-1)^k`` (alternation along every
line), an assembly is a choice of the sign arrays such that no block has three equal
signs. The sum over ``F_z`` factorizes over the columns, then over ``F_y`` over the
rows i, which leaves a sum over ``F_x`` (``2^(ny nz)`` terms, the smallest section
is chosen). Periodic boxes need even numbers of blocks. Exact up to 2^62.
"""
nx, ny, nz = sorted((int(n) for n in shape), reverse=True)
if min(nx, ny, nz) < 1:
raise ValueError("shape: positive numbers of blocks")
if periodic and any(n % 2 for n in (nx, ny, nz)):
return 0
if ny * nz > 24:
raise ValueError("box too wide: the two smallest edges must hold at most 24 blocks")
exact, total, big = _polarized_sum(nx, ny, nz)
if big:
raise OverflowError(f"about {total:.4g} assemblies: beyond exact 64-bit counting")
return int(exact)