My class has recently introduced us to tuples, and quite quickly thrown us a problem on creating a problem of the renowned "Tower of Hanoi". Essentially, we are supposed to create a tuple of (source, destination) for each movement of a plate in the Tower of Hanoi. The professor has given us this code, without much explanation:
def hanoi(n, src, des, aux):
if n == 1:
return ((src, des),)
else:
return hanoi(n-1, src, aux, des) + (((src, des),) + hanoi(n-1, aux, des, src))
I'm almost at a complete loss. (The poles are labelled Pole 1, 2 and 3 respectively. A sample input of hanoi(1,1,3,2)
would yield ((1, 3),)
, indicating movement from Pole 1 to Pole 3 for that step.)
Ok, I know what the base case is. If I only have 1 plate, I move it directly from the source pole to the destination pole. Beyond that, I know that hanoi(n-1, src, aux, des)
is the recursive step, intended to simulate when n-1 discs are left in the original stack. But I'm bummed by why hanoi(n-1, aux, des, src)
swaps the positions of aux, des and src.
I also cannot quite understand why the else:
statement is arranged as hanoi(n-1, src, aux, des) + (((src, des),) + hanoi(n-1, aux, des, src))
?
Any tips and advice would be appreciated! I have tried for hours to see the pattern, and I know the rules of the game via drawing it out, but I am unable to comprehend how it is converted to computer (Python) logic.
Thank you!
at level n, you have to move n-1 plates from src to aux (an intermediate storage pole) :
hanoi(n-1, src, aux, des)
Then you are left with the largest plate on src, you can move it from src to dest :
(((src, des),)
And finally you have to move all the n-1 plates from aux to dest (using src as the new intermediate pole) :
hanoi(n-1, aux, des, src))
hence the need to swap the positions.
The function computes the list of all moves as shown below for
hanoi(2,'pole1-src','pole2-dest','pole3-aux')