############################################################################
#
#                    ***  post1921_binary-input.py ***
#
#    Problema dei "tag" di Emil Post (1921). Data una parola arbitraria W,
#    di lunghezza L, W = (w_(L-1) w_(L-2)....w_0) con w_i in {0,1},
#    la si trasforma in W' = (w_(L-4) w_(L-5)....w_0 1 1 0 1) se w_(L-1)=1,
#    e in W' = (w_(L-4) w_(L-5)....w_0 0 0) se w_(L-1)=0.
#    Nel primo caso la parola si allunga di 1 (L = L-3+4 = L+1), nel secondo
#    si accorcia di 1 (L = L-3+2 = L-1). Il processo termina (ma non e'
#    garantito: dipende dalla W iniziale!) quando L diventa 0.
#
#                     data creazione : 4 novembre 2022
#                     ultima modifica: 4 novembre 2022
#
#############################################################################
   

############################# main() ########################################

max_count = 1000000

print('\n')

exit_flag = 0
while(exit_flag == 0):
    
    Wstr = input("initial binary word [0 to exit]: ")
    W = [int(ws) for ws in Wstr]
    L = len(W)

    print('**************************************************')
    print('N = {} (L = {})'.format(int(Wstr, 2),L))
    print('**************************************************') 

    count = 0
    while( L > 0 and count < max_count):
        if( W[0] == 1):
            W = W[3:]+[1,1,0,1]
            L += 1
        else: 
            W = W[3:]+[0,0]
            L -= 1

        Wstr = "".join(str(wi) for wi in W)
        print('#{:05d}: W = {} = {} (L = {})'.format(count,Wstr,int(Wstr, 2),L))
        count += 1

    print('')
    print('\n')