Tower of Hanoi

Deep under the Doom Tower, monks are moving a stack of golden disks from one peg to another. Every disk has a different size, and they all start on peg src, biggest at the bottom. The monks follow two rules: move one disk at a time (the top disk of a peg), and never put a bigger disk on a smaller one. A third peg, via, is there to help. The legend says the world ends when the last disk lands on dst.

Write hanoi_moves(n: int, src: str, via: str, dst: str) -> list[tuple[str, str]] that returns the shortest list of moves that carries all n disks from src to dst. Each move is a pair (from_peg, to_peg).

hanoi_moves(1, "A", "B", "C")   # [("A", "C")]
hanoi_moves(2, "A", "B", "C")   # [("A", "B"), ("A", "C"), ("B", "C")]
hanoi_moves(3, "A", "B", "C")   # [("A", "C"), ("A", "B"), ("C", "B"), ("A", "C"),
                                #  ("B", "A"), ("B", "C"), ("A", "C")]
hanoi_moves(0, "A", "B", "C")   # []

• 0 <= n <= 20. src, via and dst are three different peg names (non-empty strings).
• The shortest solution has exactly 2^n - 1 moves, and there is only one, so the tests compare your list move by move. They also replay it to check the two rules.
• 20 disks is about a million moves, and the tests time a 20-disk tower. Any solution that makes each move once is fast enough.