check_spine_incidence.py

#!/usr/bin/env python3
"""Finite semantic controls for growing-spine incidence, assessment205.

Literal sets and integer arithmetic are oracles, not native data-structure
primitives. This checks an exact encoding and a candidate cone restriction;
it does not implement persistent routing or establish a native lower bound.
"""
from itertools import product
import json


def mixed(bits):
    if all(bits) or not any(bits):
        return 0
    h = len(bits)//2
    return 1 + mixed(bits[:h]) + mixed(bits[h:])


def main():
    counts = dict(matrices=0, selections=0, pair_queries=0, singleton_budgets=0,
                  cone_selections=0, cone_queries=0, negative_cone_queries=0)
    parents = ('00', '01', '10')
    q = h = 3
    for mask in range(1 << (q*h)):
        rows = [{p+b for j,p in enumerate(parents) if mask >> (i*h+j) & 1
                 for b in '01'} for i in range(q)]
        inverse = {p: {i for i in range(q) if p+'0' in rows[i]} for p in parents}
        for amask in range(1 << q):
            selected = {i for i in range(q) if amask >> i & 1}
            union = set().union(*(rows[i] for i in selected))
            for j,p in enumerate(parents):
                expected = any((mask >> (i*h+j)) & 1 for i in selected)
                assert bool(selected & inverse[p]) == expected
                for b in '01':
                    assert (p+b in union) == expected
                    counts['pair_queries'] += 1
            counts['selections'] += 1
        counts['matrices'] += 1
    for L in range(1,1025):
        j = L.bit_length()
        a = 1 << (j.bit_length()-1)
        start = 1 << (j-1)
        m = mixed([n == L for n in range(start,2*start)])
        assert m == j-1 and m <= 2*a
        counts['singleton_budgets'] += 1
    # Geometry-only depth OR is false: unique route does not recover selection.
    assert len({'000','001'}) == 2
    assert '010' not in {'000','001'}
    # Candidate row restriction: one prefix cone and one occupied-depth interval.
    cones = (('',1,2),('0',2,4),('00',3,5),('01',4,5),('1',2,3))
    words = [''.join(p) for n in range(1,6) for p in product('01',repeat=n)]
    rows = [{w for w in words if w[:-1].startswith(prefix) and lo<=len(w)<=hi}
            for prefix,lo,hi in cones]
    for amask in range(1 << len(cones)):
        selected = [i for i in range(len(cones)) if amask >> i & 1]
        union = set().union(*(rows[i] for i in selected))
        for w in words:
            answer = any(w[:-1].startswith(cones[i][0]) and cones[i][1]<=len(w)<=cones[i][2]
                         for i in selected)
            assert answer == (w in union)
            counts['cone_queries'] += 1
            counts['negative_cone_queries'] += not answer
        counts['cone_selections'] += 1
    # Marked ancestor existence without its active depth interval is insufficient.
    assert '00'.startswith('0') and not (4<=len('000')<=5)
    selected_cones = (('0',3,3), ('1',2,2))
    b = '00'
    prefix_only = any(b[:-1].startswith(q) for q,lo,hi in selected_cones)
    depth_only = any(lo<=len(b)<=hi for q,lo,hi in selected_cones)
    joint = any(b[:-1].startswith(q) and lo<=len(b)<=hi for q,lo,hi in selected_cones)
    assert prefix_only and depth_only and not joint
    counts['correlation_counterexamples'] = 1
    print(json.dumps(counts,sort_keys=True))


if __name__ == '__main__':
    main()