# The initial version.

def hanoi1(n,fromPeg,tempPeg,toPeg):
    """Moves n disks from fromPeg to toPeg, according to the rules of Tower of Hanoi, and prints the moves."""

    if n == 1:
        # Base case:
        # Move top disk from fromPeg to toPeg.

        print "Moving",fromPeg[0],"from",fromPeg,"to",toPeg
        toPeg.insert(0,fromPeg[0])
        del fromPeg[0]

    else:
        # Recursive/inductive case:
        # Move n disks from fromPeg to toPeg.
        
        # Step 1: Move n-1 disks from fromPeg to tempPeg, to get them out of the way.
        hanoi1(n-1,fromPeg,toPeg,tempPeg)

        # Step 2: Move the nth disk from fromPeg to toPeg.
        print "Moving",fromPeg[0],"from",fromPeg,"to",toPeg
        toPeg.insert(0,fromPeg[0])
        del fromPeg[0]

        # Step 3: Move n-1 disks (again) from tempPeg to toPeg.
        hanoi1(n-1,tempPeg,fromPeg,toPeg)



# hanoi1 has an undesirable feature: it repeats code for moving a single disk.
# There are three simple ways of fixing that.
# 1) Create a helper function for moving one disk.   hanoi2
# 2) Use the function's base case as the helper.     hanoi3
# 3) Handle n==1 as part of the recursive case.      hanoi4


def hanoi2Helper(fromPeg,toPeg):
    """Moves 1 disk from fromPeg to toPeg, printing the move."""
    print "Moving",fromPeg[0],"from",fromPeg,"to",toPeg
    toPeg.insert(0,fromPeg[0])
    del fromPeg[0]
    
def hanoi2(n,fromPeg,tempPeg,toPeg):
    """Moves n disks from fromPeg to toPeg, according to the rules of Tower of Hanoi, and prints the moves."""

    if n == 1:
        # Base case:
        # Move top disk from fromPeg to toPeg.

        hanoi2Helper(fromPeg,toPeg)

    else:
        # Recursive/inductive case:
        # Move n disks from fromPeg to toPeg.
        
        # Step 1: Move n-1 disks from fromPeg to tempPeg, to get them out of the way.
        hanoi2(n-1,fromPeg,toPeg,tempPeg)

        # Step 2: Move the nth disk from fromPeg to toPeg.
        hanoi2Helper(fromPeg,toPeg)

        # Step 3: Move n-1 disks (again) from tempPeg to toPeg.
        hanoi2(n-1,tempPeg,fromPeg,toPeg)





def hanoi3(n,fromPeg,tempPeg,toPeg):
    """Moves n disks from fromPeg to toPeg, according to the rules of Tower of Hanoi, and prints the moves."""

    if n == 1:
        # Base case:
        # Move top disk from fromPeg to toPeg.

        print "Moving",fromPeg[0],"from",fromPeg,"to",toPeg
        toPeg.insert(0,fromPeg[0])
        del fromPeg[0]

    else:
        # Recursive/inductive case:
        # Move n disks from fromPeg to toPeg.
        
        # Step 1: Move n-1 disks from fromPeg to tempPeg, to get them out of the way.
        hanoi3(n-1,fromPeg,toPeg,tempPeg)

        # Step 2: Move the nth disk from fromPeg to toPeg.
        hanoi3(1,fromPeg,tempPeg,toPeg)

        # Step 3: Move n-1 disks (again) from tempPeg to toPeg.
        hanoi3(n-1,tempPeg,fromPeg,toPeg)




def hanoi4(n,fromPeg,tempPeg,toPeg):
    """Moves n disks from fromPeg to toPeg, according to the rules of Tower of Hanoi, and prints the moves."""

    if n == 0:
        # Base case:
        # Move no disks from fromPeg to toPeg.

        pass   # Do nothing.

    else:
        # Recursive/inductive case:
        # Move n disks from fromPeg to toPeg.
        
        # Step 1: Move n-1 disks from fromPeg to tempPeg, to get them out of the way.
        hanoi4(n-1,fromPeg,toPeg,tempPeg)

        # Step 2: Move the nth disk from fromPeg to toPeg.
        print "Moving",fromPeg[0],"from",fromPeg,"to",toPeg
        toPeg.insert(0,fromPeg[0])
        del fromPeg[0]

        # Step 3: Move n-1 disks (again) from tempPeg to toPeg.
        hanoi4(n-1,tempPeg,fromPeg,toPeg)



# The do-nothing case of hanoi4 is a bit odd.
# We could rewrite it as follows in hanoi5.


def hanoi5(n,fromPeg,tempPeg,toPeg):
    """Moves n disks from fromPeg to toPeg, according to the rules of Tower of Hanoi, and prints the moves."""

    if n > 0:
        # Recursive/inductive case:
        # Move n disks from fromPeg to toPeg.
        
        # Step 1: Move n-1 disks from fromPeg to tempPeg, to get them out of the way.
        hanoi5(n-1,fromPeg,toPeg,tempPeg)

        # Step 2: Move the nth disk from fromPeg to toPeg.
        print "Moving",fromPeg[0],"from",fromPeg,"to",toPeg
        toPeg.insert(0,fromPeg[0])
        del fromPeg[0]

        # Step 3: Move n-1 disks (again) from tempPeg to toPeg.
        hanoi5(n-1,tempPeg,fromPeg,toPeg)




# Which version is "best"?
# You could reasonably argue any of the versions, except that the repeated
# code rules out hanoi1.
# Comparing versions 2 & 3 vs. 4 & 5, having n==1 as a base case seems more
# natural, but allowing the n==0 case is more general (in addition to being
# shorter.
# Comparing version 2 vs. 3, having the base case act as a helper function
# can either be considered an odd shortcut or a keen observation.
# Comparing version 4 vs. 5, having the explicit do-nothing base case can
# either be considered pointless or a useful reminder of the important base case.
# (Personally, my preference would be hanoi4.)