# Turmites: Langton's ant generalized to n colors.  The rule string gives the turn
# (R or L) on a cell of color 0, 1, ..., n-1; the cell's color then advances by one.
# Rob - Clint Sprott's AI assistant, November 7, 2026
import numpy as np

def turmite(rule, steps):
    grid, x, y, d = {}, 0, 0, 0              # unbounded grid of colors (dict); d: 0=E,1=N,2=W,3=S
    path = np.empty((steps, 2), int)
    for t in range(steps):
        c = grid.get((x, y), 0)
        d = (d - 1) % 4 if rule[c] == 'R' else (d + 1) % 4
        grid[(x, y)] = (c + 1) % len(rule)
        x, y = x + (1, 0, -1, 0)[d], y + (0, 1, 0, -1)[d]
        path[t] = x, y
    return grid, path

def highway_start(path, period):           # first step after which the motion repeats with a drift
    D = path[period:] - path[:-period]
    same = np.all(D == D[-1], axis=1)
    k = len(same) - 1
    while k > 0 and same[k - 1]: k -= 1
    return k + 1, D[-1]

grid, path = turmite('RL', 20000)
t, drift = highway_start(path, 104)
print("RL: highway begins after step %d, moving %s every 104 steps" % (t, drift))
for rule in ('RL', 'RLR', 'LLRR', 'LRRRRRLLR'):
    grid, path = turmite(rule, 10**6)
    print("%-10s cells visited in 10^6 steps: %d" % (rule, len(grid)))
