import random
def n2(user):
    stack=0
    path=[]
    slot=2
    while user:
            first=[]
            for i in user:
                ran=i*random.randint(0,1)
                first+=[ran]

            if ((first[0]==user[0]) and (first[1]==user[1]))or((first[0]=='') and (first[1]=='')):
                slot+=2
                if((first[0]==user[0]) and (first[1]==user[1])) :
                    path.append([str(user[0])+str(user[1]),''])
                else:
                    path.append(['',str(user[0])+str(user[1])])
                continue

            if (first[0]== user[0]) and (first[1]== ''):
                path.append([user[0],user[1]])
                stack+=slot
                break
            if (first[0]== '') and (first[1]== user[1]):
                path.append([user[1],user[0]])
                stack+=slot
                break
    return([stack,path])

alluser=['A','B','C']
av=0
for k in range(1000):
    p=[]
    slot=0
    while alluser:
        first=[]
        used=[]
        last=[]
        for i in alluser:
            ran=i*random.randint(0,1)
            first+=[ran]

        if (first==alluser)or(first==['','','']):
            slot+=2
            if(first==alluser):
                p.append([str(alluser[0])+str(alluser[1])+str(alluser[2]),''])
            else:
                p.append(['',[str(alluser[0])+str(alluser[1])+str(alluser[2])]])
            continue

        for j in range(len(first)):
            if first[j]!='':
                used.append(first[j])#ถูกใช้ในfunction
            else:
                last+=[alluser[j]]#ถูกใช้ในfunction

        if len(used)==1:
            c=random.randint(0,1)
            if c==0:
                p.append([used[0],last[0]+last[1]])
            else:
                p.append([last[0]+last[1],used[0]])
            slot+=2
            stack,path= n2(last)
            av+=slot+stack
            print('slot =',slot+stack,',','path =',p+path)
            break

        if len(used)==2:
            slot+=2#p.append([used[0]+used[1],''])
            c=random.randint(0,1)
            if c==0:
                p.append([used[0]+used[1],''])
            else:
                p.append(['',used[0]+used[1]])
            slot+=2  #[last[0],'']
            stack,path= n2(used)
            av+=slot+stack
            d=random.randint(0,1)
            if d==0:
                e=[[last[0],'']]
            else:
                e=[['',last[0]]]
            print('slot =',slot+stack,',','path =',p+path+e)
            break

av/=1000
print('av_slot=',av)