A puzzle has three pegs and n discs of different sizes stacked on peg src, smallest on top. Discs move one at a time between pegs, and a larger disc may never sit on a smaller one. Write disc_moves(n, src, spare, dst) returning the list of moves, as (from_peg, to_peg) tuples, that transfers the whole stack from src to dst in the fewest moves, using spare as the third peg.
Examples
Input: n = 2, src = "A", spare = "B", dst = "C"
Output: [("A", "B"), ("A", "C"), ("B", "C")]
Input: n = 0, src = "A", spare = "B", dst = "C"
Output: []
Constraints
0 <= n <= 12(at most 4095 moves); peg names are single-character strings.- Recursion depth equals
n.
Goals
- Decompose a move sequence into two smaller sequences around a single move
- Pass a shared result list through the recursion
- Return an empty list for zero discs