Tower of Hanoi

Three pegs stand in a row. The source peg holds n discs, largest at the bottom and smallest on top. Move the whole pile to the target peg, using the spare peg along the way, under two rules: move one disc at a time (always the top disc of a peg), and never place a disc on a smaller one.

Write hanoi(n, source, target, spare) that returns the moves of the shortest solution, as a list of (from_peg, to_peg) tuples. The shortest solution has exactly 2**n - 1 moves, and there is only one.

Examples

hanoi(1, "A", "C", "B")  # returns [('A', 'C')]
hanoi(2, "A", "C", "B")  # returns [('A', 'B'), ('A', 'C'), ('B', 'C')]
hanoi(0, "A", "C", "B")  # returns []

With two discs, the small disc goes to the spare peg, the big disc goes to the target, and the small disc goes on top of it.

Constraints

• 0 <= n <= 16
• Peg names are short strings.