check_context_code_geometry.py

#!/usr/bin/env python3
"""Finite semantic audit for context-code geometry, not a native simulator.

No other Lab checker is imported. Integer/string/set operations are oracles.
Counts coordinate occurrences even when equal subtrees could share records.
"""
from itertools import combinations, permutations, product
import json
import random


def words(n):
    return [''.join(x) for x in product('01', repeat=n)]


def mixed_prefixes(selected, width):
    counts = {}
    for word in selected:
        assert len(word) == width
        for depth in range(width):
            prefix = word[:depth]
            counts[prefix] = counts.get(prefix, 0) + 1
    return {p for p, count in counts.items()
            if count < 2 ** (width - len(p))}


def canonical(selected, width, prefix=''):
    local = {w for w in selected if w.startswith(prefix)}
    if not local:
        return 0
    if len(local) == 2 ** (width - len(prefix)):
        return 1
    return (canonical(local, width, prefix + '0'),
            canonical(local, width, prefix + '1'))


def branches(tree):
    if isinstance(tree, int):
        return []
    return [tree] + branches(tree[0]) + branches(tree[1])


def produce(records, ordinal_width):
    contexts, codes, rows, images = [], {}, {}, {}
    for alias, target in records:
        row = rows.setdefault(alias, [])
        if target not in row:
            row.append(target)
        ordinal = row.index(target)
        owner = next((p for p in contexts if target.startswith(p)), None)
        if owner is None:
            assert len(target) >= len(alias) + 1
            owner = target[:-len(alias)-1]
            contexts.append(owner)
        residual = target[len(owner):]
        h = len(residual).bit_length() - 1
        assert abs((len(alias).bit_length()-1) - h) <= 1
        pair = owner, h
        if pair not in codes:
            codes[pair] = ''.join('00' if c == '0' else '01' for c in alias) + '11' + format(
                ordinal, f'0{ordinal_width}b')
        images[alias, target] = codes[pair] + residual
    return contexts, codes, images


def congestion(mapping, width):
    charges = {}
    for depth in range(width):
        for prefix in words(depth):
            preimage = [x for x, y in mapping.items() if y.startswith(prefix)]
            common = preimage[0]
            for x in preimage[1:]:
                while not x.startswith(common):
                    common = common[:-1]
            charges[common] = charges.get(common, 0) + 1
    return max(charges.values())


def run():
    _, smoke_codes, _ = produce([('1', '000')], 2)
    assert smoke_codes[('0', 1)] == '011100'
    family, record_count = [], 0
    for depth in range(1, 9):
        size = 2 ** depth
        order = [str(t % 2) + (format(t//2, f'0{depth-1}b')
                 if depth > 1 else '') for t in range(size)]
        initial = [p + '00' for p in order]
        universe = words(depth + 2)
        cone = {w for w in universe if w.startswith('0')}
        records = [('0', w) for w in initial]
        records += [('0', w) for w in universe if w not in initial]
        records += [('1', w) for w in sorted(cone)]
        b = (4*size).bit_length()
        contexts, codes, images = produce(records, b)
        assert contexts == order and len(codes) == size
        coded = {images['1', w] for w in cone}
        expected = {'0011' + format(t, f'0{b}b') + y
                    for t in range(0, size, 2) for y in words(2)}
        assert coded == expected
        full_branches = branches(canonical(coded, depth+9))
        assert len(mixed_prefixes(cone, depth+2)) == 1
        assert len(full_branches) == len(mixed_prefixes(coded, depth+9)) == size+6
        assert len(set(full_branches)) == depth+7
        assert len(mixed_prefixes({w[7:] for w in coded}, depth+2)) == size-1
        assert len(mixed_prefixes({'0011'+w for w in cone}, depth+6)) == 5
        assert congestion(dict(zip(order, words(depth))), depth) == size-1
        assert len(records) == 6*size
        assert sum(9+len(v)+len(w) for v, w in records) == (depth+12)*6*size
        record_count += len(records)
        family.append({'depth': depth, 'literal_mixed': 1,
                       'coded_mixed': size+6, 'distinct_branch_records': depth+7})

    rng = random.Random(213)
    transfer_checks = automorphism_checks = balanced_masks = 0
    for depth in (1, 2, 3):
        universe = words(depth)
        for chosen in combinations(range(len(universe)), len(universe)//2):
            chosen = set(chosen)
            halves = [iter([w for w in universe if w[0] == bit]) for bit in '01']
            order = [next(halves[0 if t in chosen else 1])
                     for t in range(len(universe))]
            initial = [p+'00' for p in order]
            all_targets = words(depth+2)
            records = [('0', w) for w in initial]
            records += [('0', w) for w in all_targets if w not in initial]
            records += [('1', w) for w in all_targets if w[0] == '0']
            _, _, images = produce(records, depth+3)
            mask = {images['1', w][7:] for w in all_targets if w[0] == '0'}
            assert mask == {format(t, f'0{depth}b')+y
                            for t in chosen for y in words(2)}
            balanced_masks += 1
        orders = list(permutations(universe)) if depth < 3 else [
            rng.sample(universe, len(universe)) for _ in range(128)]
        subsets = [{w for i, w in enumerate(universe) if mask >> i & 1}
                   for mask in range(2 ** len(universe))]
        for order in orders:
            mapping = dict(zip(universe, order))
            bound = congestion(mapping, depth)
            for subset in subsets:
                transformed = {mapping[w] for w in subset}
                assert len(mixed_prefixes(transformed, depth)) <= (
                    bound * len(mixed_prefixes(subset, depth)))
                transfer_checks += 1
        # All rooted-tree automorphisms, independently generated by child swaps.
        internal = [p for d in range(depth) for p in words(d)]
        for mask in range(2 ** len(internal)):
            swap = {p: (mask >> i) & 1 for i, p in enumerate(internal)}
            mapping = {w: ''.join(str(int(c) ^ swap[w[:i]])
                       for i, c in enumerate(w)) for w in universe}
            assert len(set(mapping.values())) == len(universe)
            assert congestion(mapping, depth) == 1
            for subset in subsets:
                assert len(mixed_prefixes({mapping[w] for w in subset}, depth)) == (
                    len(mixed_prefixes(subset, depth)))
                automorphism_checks += 1
    return {'status': 'passed', 'ordinary_records': record_count,
            'balanced_mask_producers': balanced_masks,
            'transfer_checks': transfer_checks,
            'automorphism_checks': automorphism_checks, 'family': family}


if __name__ == '__main__':
    print(json.dumps(run(), indent=2))