Friday, March 16, 2012

Tower of Hanoi

Code for Playing Towes of Hanoi-
A very Interesting game, which we generally played when we were kids or when we are with kids.
about the game - Tower of Hanoi
The code has been written in Python.


"""Code By Arpit Jain """

import random
import copy
import math

def int2baseTwo(x):
    """converts interger value to base of two and represents in binary"""
    binary = [] # make an empty list named bunary.
    while (x>0):
        value = x % 2  # Find the remainder on dividing by 2 as we need binary values.
        binary.append(value)  # append the binary value in the list
        x =  x//2  # Integer divide the number by 2.
    return binary
     
def randLocationR(n):
    """Creates a list of random numbers between 0 and 2 inclusive and we call it rollcall"""
    rollcall = [] # Create an empty list called roll call to return a list of random numbers between 0 and 2 inclusive.
    for i in range(0,n):
        tower = random.randint(0,2) # creates n random numbers between 0 and 2 inclusive.
        rollcall.append(tower) # adds the random number generated to the list.
    return rollcall

def rollcall2List(R):
    """converts the roll calls that we get in the above functions into a combined list of 3 lists of each tower and its elements"""
    tower1 = []     # creation of blank lists
    tower2 = []
    tower0 = []
    length = len(R)
    for i in range(0,length):   # loop to run form start to length of the list so that we can check for each and every elememt
        if(R[i]==0):
            tower0.append(i)  #if the  element is 0 then we add the value of i to tower zero similarly for the others.
            length -= 1
        if(R[i]==1):
            tower1.append(i)
            length -= 1
        if(R[i]==2):
            tower2.append(i)
            length -= 1
    tower0.sort()
    tower1.sort()
    tower2.sort()
    return [tower0,tower1,tower2]

def isLegalMove(L,a,b):
    """ this function returns a boolean value whether the move is legal or not i.e larger disc will not be allowed to go above smaller disc"""
    if(a == b):         #checks whether a and b are same if they are same then retuen false as we cannot move the disc from a post onto itself
        return False
    elif (len(L[a]) == 0):  # checks whether the length of the post a is zero or not i.e whether it has any any disc on it or not if it doesnt have any list then we can move nothing hence it should return false
        return False
    elif(len(L[b])==0): # checks for the length of the post B and returns true even if the post contains no element as it is the right condition.
        return True
    elif (L[b][0] > L[a][0]): # we movr from the post A to post B if B is zero which we checked above or if the top disc at B is larger than the disc we are moving from A else we return False
        return True
    else:
        return False

def makeMove(L,a,b):
    """Moves the disc from one tower to another if the move is legal"""
    legal = isLegalMove(L,a,b)  # calls the function isLegalMove to check if the move made is legal or not
    if (legal):
        L[b].append(L[a][0])  # if the move is legal then moves
        L[a].remove(L[a][0])  # removes the element from list a that has been transferred to tower b.
        L[b].sort() # sorts the list in tower b
        return L
    else:
        return False

def printList(L):
    """This function prints the hanaoi game in the format that we want"""
    List1 = [[],[],[]]
    length1 = len(L[0])# we find the lenght of the 3 lists inside L
    length2 = len(L[1])
    length3 = len(L[2])
    final = [length1,length2,length3]   # we add all the 3 values to a new list
    maximum = max(final)# find the maximum out of the 3

    for i in range(3):
         for j in range(maximum-len(L[i])):     # this function finds the difference between the length of the list inside L and the maximum value and appends that many number of spaces so that all the lists become of equal length.
             List1[i].append('')
         List1[i] = List1[i] + L[i]

    for i in range(maximum):
        print(str(List1[0][i]).rjust(6),str(List1[1][i]).rjust(6),str(List1[2][i]).rjust(6))# This function is used to print the list. rjust is used to give space between the two values that we have to print

    for i in range(25):
        print('-',end ='')# This loop is used to print the line. We make use of end to indicate that print on the same line until the loop is finished and end bu space.
    print('')
    print('1'.rjust(6),'2'.rjust(6),'3'.rjust(6))  

def list2Rollcall(L):
    """converts list into rollcall i.e checks each number and returns the tower on which it is placed"""
    rollcall = L[0]+L[1]+L[2]   # concatinating all the 3 lists with each other.
    rollcall.sort()     # Sorting the list and arranging it in ascending order.
    rollcall.reverse()  # reversing the order of the sorted list
    for i in range(0,len(rollcall)):  
        if(rollcall[i] in L[0]):  # we search for each element in the new list within the 3 lists and checks to which list does it belong.
           rollcall[i] = 0
        elif(rollcall[i] in L[1]):
           rollcall[i] = 1
        elif(rollcall[i] in L[2]):
           rollcall[i] = 2
    return rollcall

def rollcall2SA(R):
    """converts rollcall into sierpinski's address"""
    p =[]   # empty list which is used to assign numbers depending whether the len of the rollcall is even or odd.
    s = [] # represents sierpinski's address
    i = 0
    if(len(R)%2 == 1):     # checking if the list length is even or odd.
        p = [0,1,2]         # if odd
    else:
        p = [2,1,0]         # if even
    while(i<len(R)):                   # we run a loop uptil the length if the input i.e R
        if (R[i] == p[0]):      # we compare the value in R at ith position with the value in p at 0th position to check if they are same
            s.append(0)         # if they are same then we append zero in s otherwise we check the next conditions
            temp = p[1]         # now we need to swap the remaning 2 elements from the list P hence we make use of temp as a temporary variable.
            p[1] = p[2]         # we exchange the position of the elements in the list and store the new P
            p[2] = temp
            i = i+1
        elif (R[i] == p[1]):    # here we do the same as above and compare the 1st element of p with ith value of R
            s.append(1)
            temp = p[0]
            p[0] = p[2]
            p[2] = temp
            i = i+1
        elif (R[i] == p[2]):    # perform the same function as above.
            s.append(2)
            temp = p[1]
            p[1] = p[0]
            p[0] = temp
            i=i+1
    return s                    # return s

def SA2rollcall(SA):
    p = []   # empty list which is used to assign numbers depending whether the len of the rollcall is even or odd.
    R = [] # represents empty roll call list
    i = 0
    if(len(SA)%2 == 1):     # checking if the list length is even or odd.
        p = [0,1,2]
    else:
        p = [2,1,0]
    while(i<len(SA)):                
        if (SA[i] == p[0]): # we perform the same function as the function above only in this case we find the location in p which corresponds to the element in p and then return that location index
            R.append(0)
            temp = p[1]
            p[1] = p[2]
            p[2] = temp
            i = i+1
        elif (SA[i] == p[1]):
            R.append(1)
            temp = p[0]
            p[0] = p[2]
            p[2] = temp
            i = i+1
        elif (SA[i] == p[2]):
            R.append(2)
            temp = p[1]
            p[1] = p[0]
            p[0] = temp
            i=i+1

    return R

def SA2TA(SA):
    """converts Sierpinski's address to ternarty address"""
    TA = [0,0,0]    # intialize a new list to 3 elements with zero each as we need to give the output of 3 elements.
    n = len(SA)
    for i in range(0,n):
        if(SA[i] == 0): # if the ith element of the list SA is 0 then we use the formula - (0,1,1)x2^(n-1)
            TA[0] += 0*(2**(n-i-1)) # we have to add TA to itself as we need addition of the all the elemnts that get entered there.
            TA[1] += 1*(2**(n-i-1))
            TA[2] += 1*(2**(n-i-1))
         
        elif(SA[i] == 1):  # if the ith element of the list SA is 0 then we use the formula - (1,0,1)x2^(n-1)
            TA[0] += 1*(2**(n-i-1))
            TA[1] += 0*(2**(n-i-1))
            TA[2] += 1*(2**(n-i-1))

        elif(SA[i] == 2):# if the ith element of the list SA is 0 then we use the formula - (1,1,0)x2^(n-1)
            TA[0] += 1*(2**(n-i-1))
            TA[1] += 1*(2**(n-i-1))
            TA[2] += 0*(2**(n-i-1))
    return TA

def TA2SA(TA):
    """converts Ternary Address back into Sierpinski's Address"""
    total = TA[0]+TA[1]+TA[2]       # Total consist of addition of all the elements or values in the TA
    power = int2baseTwo(total)  # We send the total to the int2baseTwo function to find out power of 2 and then we subtract
    SA = []     # Empty SA list
    temp = TA   # Storing the TA in a new varibale called Temp
    mod = [0,0,0]   # we initialize the list for mod with 3 elements all zero's as we need to store the addition of the elements in this list hence it is initialzed to zero.
    i = 0
    for i in range(0,len(power)-1):
        if(i>0):
            temp[0] = temp[0]//2    # We do Integer division of the value in temp[0] by 2 and then in the next step we mod it by 2 and store the result in mod.
            temp[1] = temp[1]//2    # we do Integer division by 2 as we need to know how many 2's it has.
            temp[2] = temp[2]//2


        mod[0] = temp[0]%2
        mod[1] = temp[1]%2
        mod[2] = temp[2]%2

        if( mod == [0,1,1] ):   # now we have the value of mod. we check whether the current value if mod and append 0,1 or 2 accordingdly in the emplty list SA.
            SA.append(0)
        elif(mod == [1,0,1]):
            SA.append(1)
        elif(mod == [1,1,0]):
            SA.append(2)
    SA.reverse()
    return SA

def reduceTA(A,B):
    """ It takes in 2 ternary addresses and removes the large discs with the same value at the same position from both the SA's. But the large discs should be in a proper order.
    If 7 is the highest and is at the same location but 6 is at different locations and then again 5 is at the same location then we remove only 7 and not 5 because 6 is not in the same location."""

    SA= TA2SA(A)    #Converts the Ternary Address into sierpinski's
    SA1=[]
    SB = TA2SA(B)
    SB1=[]
    length1 = len(SA) #we find the length of the SA formed as we need the loop to run to this length.
    k = 0

    for i in range(0,length1):
        if(SA[i]==SB[i]):   #we compare the two values of SA and SB and if they are same then we change that value to "Equal" stating both are same
            SA[i]= 'Equal'
            SB[i]= 'Equal'
        elif(SA[i]!=SB[i]): # if the two are not at the same location then we break the loop as if the higher disc is not at the same location then we dont worry about the other discs.
            break
    while(k<length1): # Now we append the values which are not Equal into another lists SA1 and SB1. we only append the values which are not 'Equal'
        if (SA[k]!= 'Equal'):
            SA1.append(SA[k])
        if (SB[k]!= 'Equal'):
            SB1.append(SB[k])
        k = k+1

    TA1= SA2TA(SA1) # convert SA back into TA
    TB1= SA2TA(SB1)
    for i in range(0,3): # changing the original Array as we donot return anything explicitly.
       A[i] = TA1[i]
       B[i] = TB1[i]

def distTA(A_in,B_in):
    """This function is used to calculate the distance between two ternary address."""
    total = 0
    indexA = []
    indexB = []
    final = []
    Acopy = copy.deepcopy(A_in) # we make a deep copy of the first input. we make deep copy as we dont want the original list to change.
    Bcopy = copy.deepcopy(B_in)
    if(A_in == B_in):   # if the 2 inputs are the same then we retrn 0 as the distance between them.
        return 0
    else:
        reduceTA(Acopy,Bcopy)   # if the 2 inputs are not same then we find the reduced TA of the 2 inputs.

        minA = Acopy.index(min(Acopy))  # this function first finds the minimum value in Acopy and then finds the index of that value in Acopy and stores it in minA
        minB = Bcopy.index(min(Bcopy))# we find the index of the lost value so that we donot subtract the lowest valued index with 2^(n-1)

        for i in range(0,len(Acopy)): # we add all the elements in Acopy and then find its int2BaseTwo value as we need to find the number of times o appears in the loop.
            total +=Acopy[i]  
        total = (total+2)//2 # once we add all the values we divide it by 2 and then send that value to find the power.
        power = int2baseTwo(total)
        n = power.count(0)  # n stores the number of times 0 appears in power as that will be the value that we will use

        for i in range(0,len(Acopy)):
            if (i!=minA): # while the value of i is not minimun i.e while the index is not that of the lowest value subtract 2^(n-1) from all the values
                Acopy[i] = Acopy[i] - (2**(n-1))
                indexA.append(i)# we append the indexes that we have changed into a new list.

            if (i!=minB): # performs the same function as the above
                Bcopy[i] = Bcopy[i] - (2**(n-1))
                indexB.append(i)
             
        difference = 3-(minA+minB)  # now to find the 3rd point in the triangle we subtract the addition of the 2 min indexes with the 3. we use this value for option 2
        option1 = Acopy[minB] + 1 + Bcopy[minA] # for option 1 we add the values at index minB in A and minA in B and add '1' to to, this 1 is for the bridge.
        final.append(option1)   # we append this result into final list.

        option2 = Acopy[difference] + 2 + Bcopy[difference] + (2**(n-1))-1 # This is the longer route. we add the 2 values at index 'difference' and add the length of 1 side and 2 bridges.
        final.append(option2)

        required = min(final)# this gives the minimum of the 2.
     
        return required

def play():
    """This Function is used to call all the remaining functions and play the game"""
    value = 0
    print(" Welcome to the game of Tower of Hanoi")
    n = int(input("Enter the number of disc you would like to play with = ")) # input of the number of discs by the user.
    rollcall = randLocationR(n)# calling all the function from above. finding rollcall and SA and TA
    List = rollcall2List(rollcall)
    SA = rollcall2SA(rollcall)
    TA = SA2TA(SA)
    printList(List)
    print("Your Goal is to move everything to tower 3. (Q or q quits)")
    TA2 = (2**n)-1   # we know when we reach the final state the TA of the 2 positions are the same and its value is 2^(n-1)
    if(n%2!=0):   # but the position of the TA2 is not same for all the values its different for odd and even values of n.
        distance1 = distTA(TA,[TA2,TA2,0])# by this we calculate the miminum distance between the current position and the final state.
    elif(n%2==0):
        distance1 = distTA(TA,[0,TA2,TA2])
    print("Fastest Path is " ,distance1," moves")
    while(value != 1 or distance != 0): #loop to run the game until the user quits or finishes the game.
        stack1 = input("Take from stack")
        if (stack1 == '1'):  # user inputs values as 1,2 or 3 and we refer to them as 0,1,2 in our code hence we convert the input accordingly. i.e 1 to 0, 2 to 1, 3 to 2.
            stack1 = 0
        elif (stack1 == '2'):
            stack1 = 1
        elif (stack1 == '3'):
            stack1 = 2
        if(stack1 == 'q' or stack1 =='Q'):  # if user enters 'q' and 'Q' then the game quits.
            value = 1
            return "Quitter"
        stack2 = input("place on stack ")
        if (stack2 == '1'):
            stack2 = 0
        elif (stack2 == '2'):
            stack2 = 1
        elif (stack2 == '3'):
            stack2 = 2
        if(stack2 == 'q' or stack2 =='Q'):
            value = 1
            return "Quitter"
        else:
            check = isLegalMove(List,int(stack1),int(stack2))  #we check if the the move that user is doing is legal or not.
            if(check == True):  # if the isLegalMove true then we make move
                makeMove(List,int(stack1),int(stack2))
                rollcall2 = list2Rollcall(List) #now we convert the new list formed again into new TA and find its distance from the final state
                SA1 = rollcall2SA(rollcall2)
                TA1 = SA2TA(SA1)
                printList(List)
                if(n%2!=0):
                    distance2 = distTA(TA1,[TA2,TA2,0])
                elif(n%2==0):
                    distance2 = distTA(TA1,[0,TA2,TA2])
                print("Fastest Path is " ,distance2," moves")
                if(distance2!=0): # if the distance is not zero then we continue to play
                    value = 0
                    continue
                elif(distance2==0): # if distance is zero we stop playing
                    value =1
                    print("Puzzle Solved great work!!!")
                    break
            else:
                print("wrong Input") # if the move that user is trying to make is illegal we say the move is incorrect and ask him to press enter to continue playing or Q to quit.
                enter = input("Press enter to continue")
                if (enter == 'q' or enter == 'Q'):
                    value = 1
                    break
                else:
                    value = 0
                    continue


     
         
 

No comments:

Post a Comment