check_crossindex_routing.py

from itertools import permutations, product
import json


def walk(order):
    """Explicit single-zipper edge moves, returning to root after last leaf."""
    cursor = ''
    moves = 0
    for target in list(order) + ['']:
        while not target.startswith(cursor):
            cursor = cursor[:-1]
            moves += 1
        while cursor != target:
            cursor += target[len(cursor)]
            moves += 1
    return moves


def runs(order):
    """Count entries into each subtree, independently of zipper movement."""
    vertices = {w[:j] for w in order for j in range(1, len(w) + 1)}
    total = 0
    for v in vertices:
        inside = False
        for w in order:
            now = w.startswith(v)
            total += now and not inside
            inside = now
    return total, len(vertices)


def prefix_automorphism(domain, images):
    """Check that every source prefix class has one same-depth image prefix."""
    n = len(domain[0])
    for j in range(n + 1):
        classes = {}
        for x, y in zip(domain, images):
            classes.setdefault(x[:j], set()).add(y[:j])
        if any(len(v) != 1 for v in classes.values()):
            return False
    return True


def main():
    counts = {'permutations': 0, 'irregular_orders': 0, 'reversal_families': 0}
    extrema = []
    for n in range(1, 4):
        domain = [''.join(w) for w in product('01', repeat=n)]
        lo, hi, aligned = float('inf'), 0, 0
        for order in permutations(domain):
            work = walk(order)
            fragmentation, edges = runs(order)
            assert work == 2 * fragmentation
            assert (fragmentation == edges) == prefix_automorphism(domain, order)
            aligned += fragmentation == edges
            lo, hi = min(lo, work), max(hi, work)
            counts['permutations'] += 1
        assert (lo, hi, aligned) == (4 * 2**n - 4, 2 * n * 2**n, 2**(2**n - 1))
        extrema.append({'depth': n, 'min_moves': lo, 'max_moves': hi, 'aligned_orders': aligned})
    for leaves in [('0', '10', '11'), ('00', '01', '1'), ('0', '100', '101', '11')]:
        for order in permutations(leaves):
            fragmentation, edges = runs(order)
            assert walk(order) == 2 * fragmentation
            assert fragmentation >= edges
            counts['irregular_orders'] += 1
    for n in range(1, 11):
        domain = [format(i, '0%db' % n) for i in range(2**n)]
        assert walk([x[::-1] for x in domain]) == 2 * n * 2**n
        assert walk(domain) == 4 * 2**n - 4
        counts['reversal_families'] += 1
    counts['sparse_full_walks'] = 0
    counts['sparse_envelope_checks'] = 0
    for n in (8, 16, 32, 64):
        ell = n.bit_length() - 1
        suffixes = [format(i, '0%db' % ell) for i in range(n)]
        aa = ['0' * (n - ell) + t for t in suffixes]
        bb = [t + '1' + '0' * (n - ell - 1) for t in suffixes]
        assert not set(aa) & set(bb)
        swaps = dict(zip(aa, bb)) | dict(zip(bb, aa))
        assert len(swaps) == 2 * n
        assert all(swaps[swaps[x]] == x for x in swaps)
        for rate in range(1, n // ell):
            envelope = n - rate * ell
            assert len({swaps[x][:envelope] for x in aa}) == n
            counts['sparse_envelope_checks'] += 1
        if n <= 16:
            domain = [format(i, '0%db' % n) for i in range(2**n)]
            order = [swaps.get(x, x) for x in domain]
            assert len(set(order)) == len(domain)
            assert walk(order) <= 4 * 2**n - 4 + 8 * n * n <= 12 * 2**n - 4
            assert not prefix_automorphism(domain, order)
            counts['sparse_full_walks'] += 1
    counts['sparse_cut_checks'] = 0
    for n in (8, 16, 32, 64):
        ell = n.bit_length() - 1
        owners = [format(i, '0%db' % ell) + '1' + '0' * (n - ell - 1) for i in range(n)]
        for rate in range(1, 5):
            for punctuation in (0, 2):
                depth = n - rate * (ell + punctuation)
                if depth > ell:
                    mandatory = {w[:j] for w in owners for j in range(1, depth + 1)}
                    assert len(mandatory) == 2 * n - 2 + n * (n - ell - rate * (ell + punctuation))
                    counts['sparse_cut_checks'] += 1
    print(json.dumps({'status': 'pass', 'counts': counts, 'extrema': extrema}, indent=2))


if __name__ == '__main__':
    main()