import numpy as np, itertools
from scipy.linalg import null_space
def step_ring(x):
    l=np.roll(x,-1); r=np.roll(x,1)          # a_k' = a_{k+1} XOR (a_k OR a_{k-1}) on a ring
    return l^(x|r)
def counts(x,r):
    n=len(x); v=np.zeros(1<<r)
    for k in range(n):
        idx=0
        for j in range(r): idx=(idx<<1)|int(x[(k+j)%n])
        v[idx]+=1
    return v
for r in (2,3,4,5):
    n=12; rows=[]; triv=[]
    for bits in itertools.product((0,1),repeat=n):
        x=np.array(bits,dtype=np.uint8)
        cx=counts(x,r); cfx=counts(step_ring(x),r)
        rows.append(cfx-cx); triv.append(cx)
    M=np.array(rows); C=np.array(triv)
    ns=null_space(M)                       # weights whose total is conserved by one step
    Cc=C-C[0]                              # weights whose total is the same for EVERY row (trivially constant)
    nt=null_space(Cc)
    print(f"patterns of {r} lanterns: conserved combinations {ns.shape[1]}, of which trivially constant {nt.shape[1]}  ->  genuine conservation laws: {ns.shape[1]-nt.shape[1]}")
# second invention: exact parity law on the half-line, N' = R + (a1 OR d) mod 2
rng=np.random.default_rng(9); ok=tot=0
for _ in range(20000):
    L=int(rng.integers(5,40)); a=rng.integers(0,2,size=L+3).astype(np.uint8); a[L:]=0; d=int(rng.integers(2))
    nxt=np.zeros_like(a)
    for k in range(L+2):
        left=a[k-1] if k>0 else d
        nxt[k]=a[k+1]^(a[k]|left) if k+1<len(a) else (a[k]|left)
    N=int(a.sum()); R=int(((a[1:]==1)&(a[:-1]==0)).sum()+(a[0]==1)); Np=int(nxt.sum())
    tot+=1; ok+=int(Np%2==(R+(int(a[0])|d))%2)
print(f"parity law  N(next) = R + (lantern1 OR lighthouse)  (mod 2): {ok}/{tot}")