Towes of Hanoi help (Dont understand)

[wilko1995]

Hey, does anyone think they could explain how this code works?

def hanoi(n, a='A', b='B', c='C'):
    """
    move n discs from a to c using b as middle
    """
    if n == 0:
        return
    hanoi(n-1, a, c, b)
    print a, '->', c
    hanoi(n-1, b, a, c)

hanoi(3)

[TrustyTony]

Maybe trace prints from this would clarify?:

def hanoi(n, a='A', b='B', c='C'):
    """
    move n discs from a to c using b as middle
    """
    indent = '  '*(10-n)
    print indent+'hanoi(%i, %s, %s, %s)' % (n,a,b,c)
    if n == 0:
        return
    hanoi(n-1, a, c, b)
    print indent,a, '->', c
    hanoi(n-1, b, a, c)
    print indent,'%i from %s through %s to %s moved' % (n,a,b,c)
    print

hanoi(3)

Or this as it leaves out the immediate one move calls from tracing and gives less prints:

def hanoi(n, a='A', b='B', c='C'):
    """
    move n discs from a to c using b as middle
    """
    indent = '  '*(10-n)
    if n == 0:
        return
    hanoi(n-1, a, c, b)
    print indent,a, '->', c
    hanoi(n-1, b, a, c)
    print indent,'%i from %s through %s to %s moved' % (n,a,b,c)
    print

hanoi(3)

As you can see the calls with n = 0 do nothing and moving through other peg one actually moves the disc directly without using the help peg.

Very clever code as it carries only one count instead of record of current situation of all pegs. Do the action instructions your self physically with say coins, to check that it really works.

[Gribouillis]

Another explanation is to translate in pseudo code

how to move n disks from a to c using b as middle ?
    if n is 0:
        do nothing
    else:
        move n-1 disks from a to b using c as middle
        move the last disk from a to c
        move n-1 disks from b to c using a as middle

Edit: I don't agree with tonyjv that the code is so clever, because the solution is forced: before moving the nth disk from a to c, one must have moved the n-1 top disks from a to b, and afterwards, one must move the n-1 disks from b to c. It's the only way to solve the towers of hanoi.

[TrustyTony]

Maybe it was just the use of count zero base case, but for new to programming this usually looks magic that can not work.

In the book about LISP programming similar function is given and after it says:

Problem 7-1: the above solution may not be very convincing, since everything seems to be done blindly, without checking whether disks are ever placed on smaller disks or for that matter, whether an disks are left on the pin from which they are supposed to be moved

I would though do the "move one" the base case like Winston-Horn

>>> def hanoi(n, a='A', b='B', c='C'):
    """
    move n discs from a to c using b as middle
    """
    indent = '  '*(10-n)
    if n == 1:
        print indent,a, '->', c
        return
    print indent,'GOAL: %i from %s through %s to %s' % (n,a,b,c)
    if n>2: print indent,'%i from %s through %s help peg to %s' % (n-1, a,c,b)
    hanoi(n-1, a, c, b)
    hanoi(1, a, b, c)
    if n>2: print indent,'%i from %s through %s help peg to %s' % (n-1, b,a,c)
    hanoi(n-1, b, a, c)
    print indent,'%i from %s through %s to %s moved' % (n,a,b,c)
    print

    
>>> hanoi(3)
               GOAL: 3 from A through B to C
               2 from A through C help peg to B
                 GOAL: 2 from A through C to B
                   A -> C
                   A -> B
                   C -> B
                 2 from A through C to B moved

                   A -> C
               2 from B through A help peg to C
                 GOAL: 2 from B through A to C
                   B -> A
                   B -> C
                   A -> C
                 2 from B through A to C moved

               3 from A through B to C moved