src/tile.py

"""Self-assembling tile computer (abstract tile assembly model).

Computation is the growth of a crystal. The program is a finite set of square
tiles; each edge carries a glue label with an integer strength. A seed is placed
and tiles accrete onto the assembly by one rule: a tile binds at an empty site
if the summed strength of the glues that match its already-present neighbors is
at least the temperature tau. That binding rule is a threshold gate,

    bind = H( sum_d strength_d * match_d  -  tau ),

a weighted sum of matching-glue indicators against tau, so every attachment is
decided by the same Heaviside neuron the rest of the repository is built from.
At tau = 2 the model is Turing-universal (Winfree 1998): a directed tile set
grows a unique structure, and that structure is the trace of a computation.

Sides are N,E,S,W; a tile's N glue abuts its north neighbor's S glue, and so on.
A glue label "" is the null glue (strength 0, matches nothing). Glue strengths
are a property of the label (matching glues have equal strength), held in a map.
"""
from __future__ import annotations
from typing import Dict, List, Optional, Tuple

# side -> (dx, dy, my_side, neighbor_side)
_SIDES = [(0, 1, "N", "S"), (1, 0, "E", "W"), (0, -1, "S", "N"), (-1, 0, "W", "E")]


class Tile:
    __slots__ = ("N", "E", "S", "W", "name")

    def __init__(self, N="", E="", S="", W="", name=""):
        self.N, self.E, self.S, self.W, self.name = N, E, S, W, name

    def glue(self, side):
        return getattr(self, side)


def bind_strength(A: Dict[Tuple[int, int], Tile], x: int, y: int, t: Tile,
                  strength: Dict[str, int]) -> int:
    """Summed strength of t's glues that match the abutting neighbor glues."""
    s = 0
    for dx, dy, side, opp in _SIDES:
        nb = A.get((x + dx, y + dy))
        if nb is None:
            continue
        g = t.glue(side)
        if g and g == nb.glue(opp):
            s += strength.get(g, 1)
    return s


def binds(A, x, y, t, tau, strength) -> bool:
    """The threshold-gate binding decision: H(sum strength*match - tau)."""
    return bind_strength(A, x, y, t, strength) >= tau


def grow(tileset: List[Tile], seed: Dict[Tuple[int, int], Tile], tau: int,
         strength: Dict[str, int], bounds: Tuple[int, int, int, int],
         max_tiles: int = 100000) -> Tuple[Dict[Tuple[int, int], Tile], bool]:
    """Directed growth from a seed. Returns (assembly, deterministic): at every
    site at most one tile binds when the set is directed, so the assembly is
    unique. deterministic=False flags a site where two tiles could bind."""
    x0, y0, x1, y1 = bounds
    A = dict(seed)
    deterministic = True
    changed = True
    while changed and len(A) < max_tiles:
        changed = False
        frontier = set()
        for (x, y) in list(A):
            for dx, dy, _, _ in _SIDES:
                p = (x + dx, y + dy)
                if p not in A and x0 <= p[0] <= x1 and y0 <= p[1] <= y1:
                    frontier.add(p)
        for (x, y) in frontier:
            binders = [t for t in tileset if binds(A, x, y, t, tau, strength)]
            if len(binders) == 1:
                A[(x, y)] = binders[0]
                changed = True
            elif len(binders) > 1:
                deterministic = False
    return A, deterministic


# ---------------------------------------------------------------------------
# XOR / Sierpinski tile set: value(x,y) = value(x-1,y) XOR value(x,y-1)
# ---------------------------------------------------------------------------
def rule2_tileset(fn) -> List[Tile]:
    """Rule tiles for value(x,y) = fn(W-input, S-input): four tiles, each binds
    cooperatively (S and W, strength 1 each = tau) and emits fn on N and E."""
    ts = []
    for s in (0, 1):
        for w in (0, 1):
            v = fn(w, s)
            ts.append(Tile(N=f"v{v}", E=f"v{v}", S=f"v{s}", W=f"v{w}",
                           name=f"R w{w} s{s} -> {v}"))
    return ts


def sierpinski_tileset() -> List[Tile]:
    return rule2_tileset(lambda w, s: w ^ s)


def _row_col_seed(bottom: List[int], left: List[int]):
    """Seed the bottom row (y=0) and left column (x=0) with fixed value tiles,
    presenting value glues north and east for the rule tiles above/right."""
    seed = {}
    for x, b in enumerate(bottom):
        seed[(x, 0)] = Tile(N=f"v{b}", E="", S="", W="", name=f"seedB{x}={b}")
    for y, l in enumerate(left):
        if y == 0:
            continue
        seed[(0, y)] = Tile(N="", E=f"v{l}", S="", W="", name=f"seedL{y}={l}")
    return seed


def _test_binding_gate():
    """The binding decision is exactly the Heaviside threshold gate."""
    strength = {"v0": 1, "v1": 1}
    ts = sierpinski_tileset()
    A = {(1, 0): Tile(N="v1"), (0, 1): Tile(E="v0")}
    bad = 0
    for t in ts:
        for x, y in [(1, 1)]:
            w = sum(strength.get(t.glue(side), 1)
                    for dx, dy, side, opp in _SIDES
                    if A.get((x + dx, y + dy)) and t.glue(side)
                    and t.glue(side) == A[(x + dx, y + dy)].glue(opp))
            gate = 1 if (w - 2) >= 0 else 0                # H(sum*match - tau)
            if gate != int(binds(A, x, y, t, 2, strength)):
                bad += 1
    print(f"  binding decision == Heaviside gate H(sum-tau): {'OK' if bad == 0 else 'FAIL'}")
    return bad == 0


def _test_rule2(fn, name, n=24):
    strength = {"v0": 1, "v1": 1}
    bottom = [1 if x == 0 else 0 for x in range(n)]
    left = [1 if y == 0 else 0 for y in range(n)]
    seed = _row_col_seed(bottom, left)
    A, det = grow(rule2_tileset(fn), seed, 2, strength, (0, 0, n - 1, n - 1))

    def val(x, y):
        t = A.get((x, y))
        return None if t is None else (1 if t.N == "v1" else 0)

    ref = {(x, 0): bottom[x] for x in range(n)}
    ref.update({(0, y): left[y] for y in range(n)})
    for y in range(1, n):
        for x in range(1, n):
            ref[(x, y)] = fn(ref[(x - 1, y)], ref[(x, y - 1)])

    filled = bad = 0
    for y in range(1, n):
        for x in range(1, n):
            v = val(x, y)
            if v is not None:
                filled += 1
                bad += v != ref[(x, y)]
    tag = "OK" if (det and bad == 0 and filled > 0) else "FAIL"
    print(f"  rule-tile CA fn={name:3s}: directed={det}  placed={filled}  "
          f"every tile = fn(W,S) {tag}")
    return det and bad == 0 and filled > 0


# ---------------------------------------------------------------------------
# Binary counter: each row is the row below plus one. LSB is the right column;
# carry propagates west by cooperative binding (S = bit below, E = carry in).
# ---------------------------------------------------------------------------
def counter_tileset() -> List[Tile]:
    ts = []
    for b in (0, 1):
        for c in (0, 1):
            ts.append(Tile(N=f"b{b ^ c}", E=f"c{c}", S=f"b{b}", W=f"c{b & c}",
                           name=f"C b{b} c{c} -> b{b ^ c} carry{b & c}"))
    ts.append(Tile(N="edge", E="", S="edge", W="c1", name="edge(+1 injector)"))
    return ts


def counter_seed(n: int):
    """Bottom row (y=0) all zero, plus the right-edge +1 injector column base."""
    seed = {}
    for x in range(n):
        seed[(x, 0)] = Tile(N="b0", name=f"seed b0 col{x}")
    seed[(n, 0)] = Tile(N="edge", W="c1", name="seed edge")
    return seed


def _test_counter(n=6, rows=None):
    rows = rows or (1 << n) - 1
    strength = {"edge": 2}                       # value/carry glues default 1
    A, det = grow(counter_tileset(), counter_seed(n), 2, strength,
                  (0, 0, n, rows))

    def rowval(y):
        bits = []
        for x in range(n):
            t = A.get((x, y))
            if t is None:
                return None
            bits.append(1 if t.N == "b1" else 0)
        return sum(bit << (n - 1 - x) for x, bit in enumerate(bits))

    bad = filled = 0
    for y in range(1, rows + 1):
        v = rowval(y)
        if v is not None:
            filled += 1
            if v != (y & ((1 << n) - 1)):
                bad += 1
    print(f"  binary counter {n}-bit: directed={det}  rows grown={filled}  "
          f"row y encodes the integer y {'OK' if bad == 0 else f'FAIL({bad})'}")
    return det and bad == 0 and filled == rows


if __name__ == "__main__":
    print("Self-assembling tile computer")
    a = _test_binding_gate()
    b = all(_test_rule2(fn, nm) for fn, nm in
            [(lambda w, s: w ^ s, "XOR"), (lambda w, s: w & s, "AND"),
             (lambda w, s: w | s, "OR")])
    c = _test_counter()
    print("PASS" if (a and b and c) else "FAIL")