check_scale_sparse_band_independent.py

#!/usr/bin/env python3
"""Independent finite audit of scale-sparse producer transition identities.

Exhaustive set oracles check band-local updates and global defect counters;
these are semantic checks, not native timing or literal completeness checks.
No primary producer/checker implementation is imported.
"""
import json
from random import Random


def band(n):
    return n.bit_length()


def group(j):
    return j.bit_length()


def summarize(points):
    data = {}
    for j in range(1, 5):
        a, z = 1 << (j - 1), (1 << j) - 1
        inside = sorted(n for n in points if a <= n <= z)
        runs = sum(i == 0 or inside[i - 1] + 1 != n for i, n in enumerate(inside))
        partial = bool(inside) and len(inside) < a
        data[j] = (a - len(inside), runs, partial,
                   inside[0] if inside else None, inside[-1] if inside else None)
    return data


def main():
    transitions = thresholds = offsets = weighted = 0
    for mask in range(1 << 12):
        points = frozenset(n for n in range(1, 13) if mask & (1 << (n - 1)))
        old = summarize(points)
        old_pop = {g: sum(v[2] for j, v in old.items() if group(j) == g)
                   for g in range(1, 4)}
        for n in range(1, 13):
            j = band(n); a = 1 << (j - 1); z = 2 * a - 1
            new = summarize(points | {n})
            cap, runs, partial, lower, upper = old[j]
            fresh = n not in points
            p = n > a and n - 1 in points
            s = n < z and n + 1 in points
            next_cap = cap - int(fresh)
            next_runs = runs + (1 - int(p) - int(s) if fresh else 0)
            next_partial = next_cap > 0
            assert next_cap >= 0
            assert new[j][:3] == (next_cap, next_runs, next_partial)
            assert sum(v[1] >= 2 for v in new.values()) == (
                sum(v[1] >= 2 for v in old.values())
                + int(next_runs >= 2) - int(runs >= 2))
            delta = int(next_partial) - int(partial)
            for r in range(4):
                new_pop = {g: sum(v[2] for k, v in new.items() if group(k) == g)
                           for g in range(1, 4)}
                g = group(j)
                assert new_pop[g] == old_pop[g] + delta
                assert sum(x > r for x in new_pop.values()) == (
                    sum(x > r for x in old_pop.values())
                    + int(old_pop[g] + delta > r) - int(old_pop[g] > r))
                thresholds += 1
            if lower is not None:
                min_remaining = max(0, lower - a - (n - a))
                max_remaining = max(0, upper - a - (n - a))
                chosen_min = lower if min_remaining == 0 else n
                chosen_max = n if max_remaining == 0 else upper
                assert new[j][3:] == (chosen_min, chosen_max)
                offsets += 1
            else:
                assert new[j][3:] == (n, n)
            assert all(new[k] == old[k] for k in old if k != j)
            transitions += 1
    rng = Random(199)
    for r in range(5):
        for _ in range(100):
            partial = set()
            for ell in range(1, 9):
                block = list(range(1 << (ell - 1), 1 << ell))
                partial.update(rng.sample(block, min(r, len(block))))
            for k in range(1, 256):
                debt = sum(j + 1 for j in partial if j <= k)
                assert debt <= 4 * r * k
                assert r == 0 or debt < 4 * r * k
                weighted += 1
    print(json.dumps(dict(occupancy_transitions=transitions,
                          global_threshold_checks=thresholds,
                          offset_endpoint_checks=offsets,
                          weighted_cutoff_checks=weighted)))


if __name__ == '__main__':
    main()