Fast Python implementation of the hat walks from hatwalk.html, for
running experiments. The tiling is an exact port of the HTML’s substitution
system (after Kaplan’s hatviz and Smith–Myers–Kaplan–Goodman-Strauss 2023),
so hat indices, side labels and patch sizes match the browser version.
from hatwalk import build_tiling, walk, Dynamics
t = build_tiling(5) # H root, level 5: 54,289 hats
print(walk(t, "9")) # one walk from the central hat, full path
print(walk(t, "1,2a,3,4", start=123))
dyn = Dynamics(t, "1,2a,3,4") # one run from EVERY hat, vectorized
print(dyn.summary())
dyn.run_length # (n,) steps per run
dyn.escaped # (n,) left the patch vs closed orbit
dyn.end_hat, dyn.end_counts # the HTML's "where runs end" map
dyn.visit_counts # the HTML's "times hit" map (exact match)
dyn.sink_id, dyn.n_sinks # basins
dyn.garden_of_eden # hats no walk can step onto
dyn.exit_hats # hats that can shed the walker
Dynamics(t, "9", confine_order=2) # walks confined to order-2 supertiles
Rather than simulating each run, Dynamics treats the rule as a functional
graph on (hat, phase) states and resolves all sinks/distances at once by
pointer doubling.
Hat counts are squared Fibonacci numbers (×6.854 per level). Timings on an M1 Max, full all-starts analysis = run length + basins + visit counts + GoE:
| level | hats | build | analysis | builder |
|---|---|---|---|---|
| 5 | 54,289 | 0.15 s | 0.05 s | direct, full geometry |
| 6 | 372,100 | 0.8 s | 0.6 s | direct, full geometry |
| 7 | 2,550,409 | 6 s | 4 s | direct, full geometry |
| 8 | 17,480,761 | 43 s (13 s hier.) | 31 s | direct, no geometry |
| 9 | 119,814,916 | 15 s | 22 s (L=1) | hierarchical by default |
| 10 | 821,223,649 | supported | L ≤ 2 | hierarchical |
At level 8 you can pass hierarchical=True for the 13 s build; the direct
default keeps the full metatile hierarchy (confinement at every order),
while a hierarchical build only confines at orders ≥ 7.
The direct builder expands the substitution level-synchronously with numpy
(no per-hat Python objects) and pairs sides via exact integer lattice keys.
keep_geometry=False skips the (n, 14, 2) vertex array — walks and analysis
only need neighbours — and defaults off past ~3M hats.
Levels 9–10 use a hierarchical builder (hatwalk/big.py): all level-7
subtrees of the same kind (H/T/P/F) have identical internal adjacency, so
the four level-7 type patches are built once, the top levels of the
hierarchy place transformed instances, and only subtree-boundary sides get
stitched (millions of keys instead of billions). The resulting BigTiling
has the same hat indices and the same neighbors/ancestors/interior
interface walk() and Dynamics consume; confine_order is available for
orders ≥ 7, and there is no per-hat geometry to plot at that scale.
hatwalk/sweep.py analyzes thousands of rules per second by batching their
independent functional graphs into one pointer-doubling solve. Per-rule cost
is O(n·L·log n·L); measured for length-8 rules: 21 µs/rule at level 1,
168 µs at level 2, 1.4 ms at level 3. Search-space sizes: 14⁸ ≈ 1.48G raw
sequences, 184M up to rotation (the sweep keeps one per rotation class —
rotations share orbit structure), 8⁸ = 16.8M. So all of 8⁸ takes ~6 min at
level 1 / ~47 min at level 2, and every rotation class of 14⁸ is ~1 h at
level 1. The intended workflow is staged: screen small, promote the
interesting rules to Dynamics at level 5–8.
python3 -m hatwalk.sweep --level 2 --length 8 --sample 1000000
python3 -m hatwalk.sweep --level 1 --length 8 --all # every class
python3 -m hatwalk.sweep --level 2 --length 4 --all --out len4.npz
Reported per rule: escaped fraction, distinct sinks, mean/max run length,
largest closed-orbit period; results save to .npz and the CLI prints top
rules by several criteria.
python3 view.py --level 4 --rule 9 opens an interactive window: click a
hat to run the walk from there, keys 0–9 toggle detailed metatile boundary
overlays per order (traced along actual hat edges, coloured by kind: H navy,
T wine, P olive, F green, matching the HTML), b toggles basin colouring,
c clears the walk. --save out.png renders headlessly.
from hatwalk import plot_patch, plot_walk, plot_boundaries, basin_colors
ax = plot_patch(t, basin_colors(dyn)) # or any per-hat array
plot_walk(t, walk(t, "9").path, ax)
plot_boundaries(t, 2, ax) # order-2 supertile outlines
python3 example.py runs a demo and writes hatwalk_demo.png.
Modules: tiling.py (substitution geometry, neighbours, hierarchy),
big.py (hierarchical assembly for levels 9–10), walk.py (single walks),
analysis.py (all-starts dynamics), sweep.py (batched rule search),
plot.py (rendering), view.py (interactive viewer).
Verified: patch sizes match the HTML (1,156 / 7,921 / 54,289 hats at levels 3–5); the vectorized builder is bit-identical to a straight port of the HTML’s traversal; the hierarchical builder matches the direct one exactly (all 14 neighbour columns, reflections, interior, ancestors, dynamics) at small levels; per-start run lengths, outcomes, end hats and exact visit counts match step-by-step simulation.