Solve the Tower of Hanoi: move n disks from peg A to peg C, using peg B, one disk at a time, never putting a disk on a smaller one. Disk 1 is the smallest.
Input
One line: n (1 ≤ n ≤ 10).
Output
Each move on its own line, as disk d: X -> Y. Then the number of moves, as N moves. Use the standard recursive solution: there is only one shortest solution, and it is the one that solution produces.
Examples
Example 1 · Input
2
Expected output
disk 1: A -> B disk 2: A -> C disk 1: B -> C 3 moves
Example 2 · Input
3
Expected output
disk 1: A -> C disk 2: A -> B disk 1: C -> B disk 3: A -> C disk 1: B -> A disk 2: B -> C disk 1: A -> C 7 moves
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
To move n disks from A to C: move n − 1 from A to B, move disk n from A to C, move n − 1 from B to C.
Hint 2
A function hanoi(n, source, spare, target) that calls itself twice.
Hint 3
There are 2**n − 1 moves.
Solution
Show one correct solution (try it yourself first)
count = 0
def hanoi(n, source, spare, target):
global count
if n == 0:
return
hanoi(n - 1, source, target, spare)
print(f"disk {n}: {source} -> {target}")
count += 1
hanoi(n - 1, spare, source, target)
hanoi(int(input()), "A", "B", "C")
print(count, "moves")