Towers of Hanoi

Lab Python Advanced 30 points

Read n and print the moves to move n disks from peg A to peg C (using B), one per line as A -> C, then the total number of moves.

Input

One integer 1–10.

Output

The moves, then the count.

Example

Input

Output

A -> B
A -> C
B -> C
3

Sample input available Sample output available

Editor

Python

Hints

Move n-1 disks out of the way, move the biggest, then move the n-1 back on top.

Solution explanation

The solution needs 2ⁿ − 1 moves — the recursion mirrors the description exactly.

Show solution

moves = []


def hanoi(n, src, via, dst):
    if n == 0:
        return
    hanoi(n - 1, src, dst, via)
    moves.append(f"{src} -> {dst}")
    hanoi(n - 1, via, src, dst)


hanoi(int(input()), "A", "B", "C")
print("\n".join(moves))
print(len(moves))

Output

Answer