check_normalized_composition.py

"""Finite semantic model of paid target normalization; not native timing evidence."""
from itertools import product
import json
import check_pending_substitution as n
from check_frozen_row_composition import B, lookup


def key(word):
    at = word.find('1')
    return word[at+1:] if at >= 0 and at+1 < len(word) else None


def prepare(pairs, k=2, d=2, s=0):
    targets, counts = {}, {}
    lanes = (B,) * k
    global_rows = B
    for v,w in pairs:
        z = key(w)
        if z is None:
            return None
        global_candidate = n.add_right(global_rows, v, z, d, s)
        if global_candidate is None:
            return None
        global_rows = global_candidate
        # All lane builders consume the same actual record before slot discovery.
        candidates = tuple(n.add_right(root, v, z, d, s) for root in lanes)
        fresh = w not in targets
        slot = counts.get(z, 0) if fresh else targets[w]
        if slot >= k or candidates[slot] is None:
            return None
        targets = dict(targets); counts = dict(counts)
        targets[w] = slot
        if fresh:
            counts[z] = slot + 1
        lanes = tuple(candidates[i] if i == slot else root for i,root in enumerate(lanes))
    return targets, lanes


def condition(pairs, k, d, s):
    # Independent explicit sets, preserving the declared first-occurrence order.
    fibres, rows = {}, {}
    for v,w in pairs:
        z = key(w)
        if z is None or abs(n.cls(v)-n.cls(z)) > s:
            return False
        fibre = fibres.setdefault(z, [])
        if w not in fibre:
            fibre.append(w)
        if len(fibre) > k:
            return False
        slot = fibre.index(w)
        rows.setdefault(v, set()).add(z)
    return all(len(row) <= d for row in rows.values())


def audit(pairs, queries, k=2, d=2):
    packed = prepare(pairs,k,d)
    assert (packed is not None) == condition(pairs,k,d,0)
    if packed is None:
        return 0,0
    targets, frozen = packed
    rows=(B,)*k; marks=set(); snapshots=[(rows,marks)]
    names=sorted({v for v,w in pairs})
    for i,v in enumerate(names+names[:1]):
        u=str(i%2)
        rows=tuple(n.add_left(root,f,u,v,d,0) for root,f in zip(rows,frozen))
        marks=marks|{(u,v)}
        snapshots.append((rows,marks))
    checks=0
    for old, marked in snapshots:
        for u in ('0','1','00'):
            for w in queries:
                z=key(w)
                answers=[n.index_contains(lookup(root,u) or {},z) for root in old] if z else [False]*k
                got=w in targets and answers[targets[w]]
                want=any((u,v) in marked and ww==w for v,ww in pairs)
                assert got==want,(pairs,u,w,marked)
                checks+=1
    return len(snapshots),checks


def main():
    edges=[('0','10'),('1','10'),('0','010'),('1','0010'),('0','11'),('1','011'),('00','100'),('01','0101'),('00','10')]
    queries=['10','010','0010','00010','11','011','100','0101','0','1','111']
    cases=versions=checks=0
    for mask in range(1<<len(edges)):
        pairs=[e for i,e in enumerate(edges) if mask>>i&1]
        for k,d in ((1,1),(2,1),(2,2),(3,2)):
            for ordered in (pairs,list(reversed(pairs))):
                vv,qq=audit(ordered+ordered[:1],queries,k,d)
                cases+=1;versions+=vv;checks+=qq
    assert prepare([('0','0')]) is None  # Outside normalizer domain.
    assert prepare([('0','1')]) is None  # Empty normalized key.
    # Terminal guard and lane distinction cannot be dropped.
    assert key('10')==key('010')
    assert prepare([('0','10'),('1','010')],1) is None
    packed=prepare([('0','10'),('1','010')],2)
    assert packed[0]['10'] != packed[0]['010']
    rectangle_cases = 0
    for mask in range(1 << len(edges)):
        relation = {e for i,e in enumerate(edges) if mask >> i & 1}
        groups = {}
        for v,w in relation:
            groups.setdefault(key(w), set()).add((v,w))
        rectangle = all(g == {(v,w) for v,_ in g for _,w in g} for g in groups.values())
        safe = all(((v,w) in relation) == any(vv == v and key(ww) == key(w) for vv,ww in relation)
                   for v in {v for v,w in relation} for w in {w for v,w in relation})
        assert rectangle == safe
        rectangle_cases += 1
    # Far-expanded reversal under one fixed erasing normalizer.
    examples=[]
    for h in range(2,9):
        words=[''.join(x) for x in product('01',repeat=h)]
        pairs=[(v,'0'*(h*h)+'1'+v[::-1]) for v in words]
        vv,qq=audit(pairs,[pairs[0][1],pairs[-1][1],'0'*(h*h+1)+'1'+words[0]],1,1)
        versions+=vv;checks+=qq
        r=h//2
        # A prefix fixing r reversed bits leaves all first h-r bits independent.
        possible=[v for v in words if v[::-1].startswith('0'*r)]
        for ticks in range(r,h+2):
            width=len({(v+'P'*ticks)[:ticks] for v in possible})
            assert width>=2**r
        examples.append({'h':h,'target_length':h*h+1+h,'minimum_midpoint_width':2**r})
    print(json.dumps({'contract_cases':cases,'retained_versions':versions,'query_comparisons':checks,'expanded_reversal':examples,'rectangle_equivalence_cases':rectangle_cases,'native_timing_evidence':False},indent=2))

if __name__=='__main__': main()