Challenge: Tower of Hanoi

Lab Python Intermediate 20 points

Move n discs from peg A to peg C using peg B. Only one disc moves at a time and a bigger disc can never sit on a smaller one. Print every move as Move disc <d> from <X> to <Y> (disc 1 is the smallest), then Total moves: <count>.

Input

One whole number n (1 ≤ n ≤ 6).

Output

The moves, then the total.

Example

Input

Output

Move disc 1 from A to C
Total moves: 1

Sample input available Sample output available

Editor

Python

Hints

To move n discs: first move n - 1 discs out of the way (to the spare peg).

Then move disc n to the target, then move the n - 1 discs on top of it.

Solution explanation

The puzzle is two smaller puzzles plus one move, so it takes 2ⁿ − 1 moves – a classic O(2ⁿ) algorithm.

Show solution

moves = 0

def hanoi(n, src, via, dst):
    global moves
    if n == 0:
        return
    hanoi(n - 1, src, dst, via)
    print(f"Move disc {n} from {src} to {dst}")
    moves += 1
    hanoi(n - 1, via, src, dst)

hanoi(int(input()), "A", "B", "C")
print("Total moves:", moves)

Output

Answer