check_profile_observation_cover.py

#!/usr/bin/env python3
"""Finite semantic audit of copied radial profiles, not a native simulator.

Maintained argument: docs/research-programs/name-funded-ball-reuse.md, section 9.
A depth is charged cell advances from the opaque root of one private chain.
"""
from itertools import product
import json


def profiles(depth):
    a = tuple(int(j != depth) for j in range(1, depth + 3))
    b = tuple(int(j != depth + 1) for j in range(1, depth + 3))
    return a, b


def storage(n, depth, swapped=()):
    a, b = profiles(depth)
    swapped = frozenset(swapped)
    return tuple(row for i in range(n)
                 for row in ((b, a) if i in swapped else (a, b)))


def transcript(rows, advances):
    return tuple(row[:d] for row, d in zip(rows, advances))


def membership(rows, width):
    return any(row[width - 1] for row in rows[::2])


def audit_covers():
    cases = states = hidden_alternatives = 0
    for n, depth in [(n, d) for n in range(1, 4) for d in range(2, 6)] + [(4, 2)]:
        base = storage(n, depth)
        alternatives = [storage(n, depth, (i,)) for i in range(n)]
        assert not membership(base, depth)
        assert all(membership(rows, depth) for rows in alternatives)
        assert all(sorted(rows) == sorted(base) for rows in alternatives)
        best = None
        for advances in product(range(depth + 1), repeat=2 * n):
            seen = transcript(base, advances)
            indistinguishable = [i for i, rows in enumerate(alternatives)
                                 if transcript(rows, advances) == seen]
            uncovered = [i for i in range(n)
                         if max(advances[2*i:2*i+2]) < depth]
            assert indistinguishable == uncovered
            states += 1
            hidden_alternatives += len(uncovered)
            if not indistinguishable:
                cost = sum(advances)
                best = cost if best is None else min(best, cost)
        assert best == n * depth
        cases += 1
    return dict(cover_instances=cases, prefix_transcripts=states,
                hidden_single_swap_alternatives=hidden_alternatives)


def audit_selector():
    answers = assignments = 0
    for n in range(1, 9):
        for depth in range(2, 10):
            a, b = profiles(depth)
            for bits in product((0, 1), repeat=n):
                rows = storage(n, depth, [i for i, bit in enumerate(bits) if bit])
                mask = [False, False]
                for bit in bits:
                    mask[bit] = True
                for width in range(1, depth + 3):
                    answer = ((mask[0] and a[width-1]) or
                              (mask[1] and b[width-1]))
                    assert answer == membership(rows, width)
                    answers += 1
                assignments += 1
    return dict(selector_assignments=assignments, selector_answers=answers)


def audit_deadlines():
    witnesses = []
    for rate in (1, 2, 4, 16, 64, 256):
        n = 2 * rate + 1
        ell = (2*n-1).bit_length()
        assert 2**ell >= 2*n
        # Deliberately generous syntax bound: includes names, pins, delimiters.
        syntax = 10 * n * (ell + 1) + 10
        preparation = rate * syntax
        depth = (preparation + rate * syntax) // (n-rate) + 1
        available = preparation + rate * (depth + syntax)
        assert available < n * depth
        q = rate
        fifo = 0
        for _ in range(n):
            fifo = max(0, fifo - q * ell) + depth
        assert fifo >= n*depth - (n-1)*q*ell
        assert fifo > rate * (depth + syntax)
        witnesses.append(dict(rate=rate, pairs=n, name_bits=ell, depth=depth,
                              inspection_required=n*depth,
                              inspection_available=available,
                              fifo_debt=fifo))
    return witnesses


def main():
    result = dict(status='passed', **audit_covers(), **audit_selector(),
                  deadline_witnesses=audit_deadlines())
    print(json.dumps(result, indent=2))


if __name__ == '__main__':
    main()