check_indexed_preparation_readout.py

#!/usr/bin/env python3
"""Finite oracles for assessment154, not a native machine simulation."""
from itertools import product
import json
import random


def schedule(lengths, a=3):
    slots = {}
    history = []
    supplied = 0
    used = 0
    for n in lengths:
        before = tuple(sorted(slots.items()))
        history.append((slots, before))
        for p in range(1, n + 1):
            j = (p - 1).bit_length()
            quantum = a if j == 0 else 2 * a
            supplied += quantum
            old = slots.get(j, 0)
            used += min(old, quantum)
            slots = dict(slots)
            slots[j] = max(0, old - quantum)
        j = n.bit_length() - 1
        assert slots.get(j, 0) == 0, (lengths, n, slots)
        slots = dict(slots)
        slots[j] = a * (1 << j)
        assert sum(v > 0 for v in slots.values()) <= max(lengths).bit_length()
    assert supplied <= 2 * a * sum(lengths)
    assert used <= supplied
    for snapshot, contents in history:
        assert tuple(sorted(snapshot.items())) == contents
    return len(history)


def main():
    schedules = 0
    records = 0
    for k in range(1, 5):
        for ns in product(range(1, 9), repeat=k):
            records += schedule(ns)
            schedules += 1
    rng = random.Random(154)
    for _ in range(100):
        ns = [rng.randint(1, 256) for _ in range(30)]
        records += schedule(ns)
        schedules += 1
    for j in range(1, 11):
        ns = [1 << j] + [1] * 100 + [1 << j, (1 << j) - 1, 1 << j]
        records += schedule(ns)
        schedules += 1
    fifo = 0
    for q in range(1, 9):
        b = 4 * q + 4
        for m in range(1, 10):
            ns = [b**k for k in range(m, -1, -1)]
            assert 4 * q * sum(ns[1:]) < ns[0]
            remaining = ns[0]
            backlog = 1
            for n in ns[1:]:
                remaining -= q * n
                assert remaining > 0
                backlog += 1
            assert backlog == m + 1
            fifo += 1
    words = [''.join(w) for n in range(1, 5) for w in product('01', repeat=n)]
    rows = counts_checked = full_checked = duplicate_checks = 0
    for _ in range(100):
        row = set()
        counters = {}
        snapshots = []
        for w in [rng.choice(words) for _ in range(60)]:
            snapshots.append((counters, dict(counters)))
            prior = dict(counters)
            updated = dict(counters)
            if w not in row:
                for d in range(len(w) + 1):
                    key = (len(w), w[:d])
                    updated[key] = updated.get(key, 0) + 1
            else:
                assert updated == prior
                duplicate_checks += 1
            row.add(w)
            counters = updated
            for n in range(1, 5):
                for d in range(n + 1):
                    for p in map(''.join, product('01', repeat=d)):
                        expected = sum(len(x) == n and x.startswith(p) for x in row)
                        actual = counters.get((n, p), 0)
                        assert actual == expected
                        counts_checked += 1
                        full = all(p + ''.join(z) in row for z in product('01', repeat=n-d))
                        assert (actual == 2**(n-d)) == full
                        full_checked += 1
        for snapshot, expected in snapshots:
            assert snapshot == expected
        rows += 1
    print(json.dumps(dict(schedules=schedules, records=records, fifo_witnesses=fifo,
                         rows=rows, prefix_counts=counts_checked,
                         fullness_checks=full_checked, duplicate_checks=duplicate_checks), sort_keys=True))


if __name__ == '__main__':
    main()