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)``````
3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by pyTony

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.

Edited by pyTony: n/a

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.

Edited by Gribouillis: n/a

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``````

Edited by pyTony: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.