check_pattern_dispatch.py

"""Finite controls for literal pattern-matching dispatch, not a native bound."""
from itertools import product


def prefixes(words):
    return {w[:i] for w in words for i in range(len(w) + 1)}


def transition(states, state, bit):
    """Semantic completed transition: longest suffix that is a prefix."""
    text = state + bit
    return max((s for s in states if text.endswith(s)), key=len)


def reports(words, text):
    return {w for w in words if text.endswith(w)}


def check(k):
    chain = prefixes({'0' * k})
    # Count proper-suffix failure steps, separately from completed transitions.
    state, failures = '0' * k, 0
    while state and state + '1' not in chain:
        state = max((s for s in chain if len(s) < len(state)
                     and state.endswith(s)), key=len)
        failures += 1
    assert failures == k
    assert transition(chain, '0' * k, '1') == ''

    words = {'0' * i + '1' for i in range(1, k + 1)}
    text = '0' * k + '1'
    assert all(not reports(words, text[:i]) for i in range(k + 1))
    assert len(reports(words, text)) == k

    extended = prefixes({'0' * k, '1'})
    changes = [(s, b) for s in chain for b in '01'
               if transition(chain, s, b) != transition(extended, s, b)]
    assert set(changes) == {(s, '1') for s in chain}
    assert len(changes) == k + 1

    zeros = {'0' * i for i in range(1, k + 1)}
    n = 2 * k
    assert sum(len(reports(zeros, '0' * j)) for j in range(1, n + 1)) == (
        k * n - k * (k - 1) // 2)


def exhaustive():
    # Independently compare completed-state outputs with direct text suffixes.
    universe = [''.join(s) for n in (1, 2) for s in product('01', repeat=n)]
    cases = 0
    for mask in range(1, 1 << len(universe)):
        words = {w for i, w in enumerate(universe) if mask >> i & 1}
        states = prefixes(words)
        for bits in product('01', repeat=5):
            text, state = '', ''
            for bit in bits:
                text += bit
                state = transition(states, state, bit)
                assert reports(words, state) == reports(words, text)
                cases += 1
    return cases


if __name__ == '__main__':
    for k in range(1, 65):
        check(k)
    print(f'PASS: four families for k=1..64; {exhaustive()} exhaustive output comparisons')