check_count_class_access.py

"""Semantic checks for assessment176; no native timing or pointer implementation claim."""
from itertools import product
import json

stats = dict(states=0, gap_answers=0, equal_length_pairs=0, radial_completions=0,
             semilattice_words=0, trie_versions=0, trie_queries=0, deadline_cases=0)

def width(n):
    return max(1, (n-1).bit_length())

def setup(h):
    k, length = width(2*h), width(4*h+3)
    names = [format(i, f'0{k}b') for i in range(2*h)]
    targets = [format(i, f'0{length}b') for i in range(2**length)]
    rows = {names[2*i]: set(targets[:4*(i+1)]) for i in range(h)}
    rows.update({names[2*i+1]: set(targets[:4*(i+1)+1]) for i in range(h)})
    return names, targets, rows

def observations(names, rows):
    counts = set(map(len, rows.values()))
    result = []
    for name in names[::2]:
        c = len(rows[name])
        successors = [s for s in counts if s > c]
        result.append(bool(successors and min(successors) == c+1))
    return tuple(result)

def clause(v,w):
    return f'(-01{v},+1{w});'

def insert(root, key, value):
    if not key:
        return value
    a,b = root if root is not None else (None,None)
    return (insert(a,key[1:],value),b) if key[0]=='0' else (a,insert(b,key[1:],value))

def query(root,key):
    for digit in key:
        if root is None: return None
        root = root[int(digit)]
    return root

for h in range(1,9):
    names, targets, base = setup(h)
    k,L = len(names[0]),len(targets[0])
    preparation = sum(len(clause(v,w)) for v,ws in base.items() for w in ws)
    assert sum(map(len,base.values())) == 4*h*h+5*h
    assert preparation == (4*h*h+5*h)*(9+k+L)
    answer_vectors=set()
    for bits in product((0,1),repeat=h):
        rows={v:set(ws) for v,ws in base.items()}
        suffix=[]
        for i,bit in enumerate(bits):
            v=names[2*i+1];w=targets[4*(i+1)+1] if bit else targets[0]
            suffix.append(clause(v,w));rows[v].add(w)
        assert len(''.join(suffix)) == h*(9+k+L)
        assert all(rows[v]==base[v] for v in names[::2])
        expected=tuple(not b for b in bits)
        assert observations(names,rows)==expected
        answer_vectors.add(expected)
        stats['states']+=1;stats['gap_answers']+=h;stats['equal_length_pairs']+=h
        for v in names:rows[v].update(targets)
        assert len({frozenset(ws) for ws in rows.values()})==1
        assert all(ws==set(targets) for ws in rows.values())
        stats['radial_completions']+=1
    assert len(answer_vectors)==2**h

# Separate order/duplicate histories, computed with literal set insertion.
for h in range(1,5):
    names,targets,base=setup(h)
    for length in range(6):
        for word in product(range(h),repeat=length):
            rows={v:set(ws) for v,ws in base.items()}
            for i in word:rows[names[2*i+1]].add(targets[4*(i+1)+1])
            assert observations(names,rows)==tuple(i not in word for i in range(h))
            stats['semilattice_words']+=1

# Immutable trie demonstrates that logarithmic name-funded reads remain possible.
# Updates are NOT a real-time per-symbol construction; path copying is charged.
root=None; history=[]
for step in range(256):
    key=format((step*13)%32,'05b');value=bool((step//7)%2)
    oracle=dict(history[-1][1]) if history else {}
    oracle[key]=value;root=insert(root,key,value);history.append((root,oracle))
for root,oracle in history:
    for i in range(32):
        key=format(i,'05b');assert query(root,key)==oracle.get(key)
        stats['trie_queries']+=1
    stats['trie_versions']+=1

for m in range(1,10):
    words=[format(i,f'0{j}b') for j in range(1,m+1) for i in range(2**j)]
    q=2**(m+1)-2
    actual=sum(len(clause('0',w)) for w in words)
    assert len(set(words))==q
    assert sum(map(len,words))==(m-1)*2**(m+1)+2
    assert actual==10*q+(m-1)*2**(m+1)+2
    for rate in (1,2,8,32):
        L=max(m+1,rate*actual//q+1)
        assert q*(L+1)>rate*actual
        # Count bit lengths computed exactly; no enormous setup enumeration.
        assert all((2**L+t).bit_length()>=L+1 for t in (0,1,q))
        stats['deadline_cases']+=1
print(json.dumps(stats,sort_keys=True))