# Solves the Tower of Hanoi problem
#
# Matt Bishop, MHI 289I, Fall 2023

# read in a number
# parameters: none
# returns: the number, if read successfully
#          0, on EOF
def getnum():
    # loop until we get good input
    while True:
        try:
            # get the input and check the type here
            n = int(input("number of disks (EOF to quit): "))
        except EOFError:        # user wants to quit, so help her
            n = 0
            break
        except ValueError:      # user didn't enter a number
            print("You have to enter a positive n or EOF")
            continue
        # now check the value we read/were given
        if n > 0:
            break
        # this is bad, so say so
        print("You have to enter a positive n or EOF")

    # it's positve to continue, -1 to quit
    return n

# solve the Tower of Hanoi
# parameters: n, number of disks to move from fromtower to totower
#             fromtower, the name of the tower with the disks
#             totower, the name of the tower where the disks are to
#                 be moved to
#             temptower, the name of the tower to be used to hold disks
#                 temporarily
# returns: nothing
def hanoi(n, fromtower, totower, temptower):
    # just in case . . .
    if n < 1:
        return 0
    # base case: only one disk, so move it directly to totower
    if n == 1:
        print("Move disk from tower", fromtower, "to tower", totower)
        return 1;
    # recursion here
    else:
        # move the top n-1 disks to the temporary tower
        count = hanoi(n-1, fromtower, temptower, totower)
        # move the leftover disk to the destination
        # note: for efficiency, we could just put a copy of the
        # base case here
        count += hanoi(1, fromtower, totower, temptower)
        # move the n-1 disks from the temporary tower to the destination
        count += hanoi(n-1, temptower, totower, fromtower)
        return count

# this puts it all together
def main():
    # print out a description of the program
    print("""
The Tower of Hanoi puzzle solver will move disks from tower A to tower C.
Tower B is in the middle and is used as a temporary tower.
""")
    # get a positive integer
    n = getnum()
    # got it!
    if n > 0:
        # solve the problem
        x = hanoi(n, "A", "C", "B")
    print("The number of moves is", x)
    
main()