Not the exercise. This draws a ruler’s tick marks: the tick in the middle is the longest, and each half is a smaller ruler. Two recursive calls, one thing done in between.
def ruler(height):
if height == 0:
return []
return ruler(height - 1) + [height] + ruler(height - 1)
print(ruler(3)) # -> [1, 2, 1, 3, 1, 2, 1]
- Before, the middle, after
The left half, then the big tick, then the right half. Hanoi has the same shape: move the smaller tower away, move one disc, move the smaller tower back.
- The size doubles each level
Each height is two copies of the one below plus one, so the length is 2**height - 1. That is exactly the number of moves Hanoi needs, for the same reason.
- You never trace it
To check ruler(3), assume ruler(2) is right and look at how it is used. Following every call down to the bottom is how people get lost.
Forget the whole tower. The biggest disc has to go from source to target, and before it can, every disc above it must be out of the way on the spare.
Moving the top n - 1 discs to the spare is the same problem with the pegs in a different order: source stays source, the spare becomes the target, and the target is free to be the spare.
Base case: n == 0 returns []. Otherwise: hanoi(n - 1, source, target, spare) + [(source, target)] + hanoi(n - 1, spare, source, target).
def hanoi(n, source="A", spare="B", target="C"): if n < 0: raise ValueError(...) if n == 0: return ____ return (hanoi(n - 1, source, ____, spare) + [(source, target)] + hanoi(n - 1, ____, source, target))
def hanoi(n, source="A", spare="B", target="C"):
if n < 0:
raise ValueError(f"a tower cannot have {n} discs")
if n == 0:
return []
return (hanoi(n - 1, source, target, spare)
+ [(source, target)]
+ hanoi(n - 1, spare, source, target))
The first call moves the small tower to the spare, so the spare is its target. The second moves it from the spare to the target. Getting the argument order right is the whole difficulty; the recursion is two lines.
The biggest disc must move at least once, and only when everything else is on the spare, so the n - 1 discs must be moved there and back. That gives 2 * moves(n - 1) + 1, which is 2**n - 1.
Stopping at 0 discs makes 1 disc fall out of the general rule for free: nothing, one move, nothing. A base case at 1 works too, but still needs hanoi(0) to return [] for the contract.
2**n grows fast: 30 discs need over a billion moves, and a list of them will not fit in memory. Yield the moves one at a time, or, if you only need the count, return 2**n - 1 without making any moves at all.
- Yield the moves instead of returning a list, and print the first ten moves of a 64-disc tower.
- Return which disc moves at each step as well as the pegs.
- Write a checker that plays a list of moves and raises if a rule is ever broken.