Generate Tower of Hanoi moves

You are given n disks of different sizes stacked on peg A (largest at bottom). You have two other pegs, B and C. You may move one disk at a time, and you may never place a larger disk on top of a smaller disk.

Write a program that outputs a valid sequence of moves to transfer all disks from A to C. Define the move format (e.g., "A -> C"). Analyze the time complexity.

Generate Tower of Hanoi Moves

You are given n disks of different sizes stacked on peg A, with the largest disk at the bottom and the smallest at the top. You also have two other pegs, B and C.

You may move only one disk at a time, and you may never place a larger disk on top of a smaller disk.

Write a function that returns the minimum-length valid sequence of moves needed to transfer all disks from peg A to peg C, using peg B as the auxiliary peg.

Represent each move as a string in the format "X -> Y", where X is the source peg and Y is the destination peg.

Constraints

• 0 <= n <= 12
• The returned sequence must be a valid minimum-length solution
• Peg A starts with all n disks, peg C must contain all n disks at the end

Examples

Example 1

Input: (0,)
Output: []

Explanation: With no disks, no moves are needed.

Example 2

Input: (1,)
Output: ['A -> C']

Explanation: A single disk can be moved directly from A to C.

Hints

1. To move n disks, first think about what must happen to the top n-1 disks before the largest disk can move.
2. This problem naturally breaks into smaller subproblems with the same structure.