Disc Tower Moves
Problem
Three pegs are named A, B and C. Peg A holds n discs of different sizes, largest at the bottom. Move the whole stack to peg C, one disc at a time, never placing a larger disc on a smaller one. Return the moves in order, each written as the peg moved from and the peg moved to.
Examples
Input: n = 1, src = "A", dst = "C", spare = "B"
Output: [("A", "C")]
Why: a single disc goes straight acrossInput: n = 2, src = "A", dst = "C", spare = "B"
Output: [("A", "B"), ("A", "C"), ("B", "C")]
Why: park the small disc on the spare peg, move the big one, put it backInput: n = 0, src = "A", dst = "C", spare = "B"
Output: []
Why: edge case, an empty stack needs no movesHints
0 / 3
Think about the largest disc only. There is exactly one situation in which it is allowed to move.
To free the largest disc, the other n-1 discs must all sit somewhere that is not its destination. That is the same problem with one fewer disc.
Move n-1 discs to the spare peg, move the largest disc to the destination, then move those n-1 discs from the spare peg onto it. The roles of the two non-source pegs swap between the two recursive calls.
Solution
The largest disc can only move when every smaller disc is out of the way on the spare peg, so the problem splits into two copies of itself around a single move. The recursion writes itself once the roles are named: destination and spare trade places in the first call and source and spare trade places in the second. The base case is an empty stack, which needs no moves. The move count doubles with each disc plus one, so time is O(2 to the n) and the stack depth is O(n).
def moves(n, src, dst, spare):
if n == 0:
return [] # nothing left to move
above = moves(n - 1, src, spare, dst) # clear the smaller discs first
return above + [(src, dst)] + moves(n - 1, spare, dst, src)
print(moves(1, "A", "C", "B")) # -> [('A', 'C')]
print(moves(2, "A", "C", "B")) # -> [('A', 'B'), ('A', 'C'), ('B', 'C')]
print(len(moves(3, "A", "C", "B"))) # -> 7Stuck on the idea rather than the code? The Call Stack covers it.