Challenge: Tower of Hanoi

Lab C++ Intermediate 20 points

Move n discs from peg A to peg C using peg B; one disc at a time, never a bigger disc on a smaller one. Print each move as Move disc <d> from <X> to <Y>, 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

C++

Hints

Move n - 1 discs to the spare peg, move disc n, then move the n - 1 discs on top of it.

Solution explanation

It takes 2ⁿ − 1 moves: a classic O(2ⁿ) algorithm.

Show solution

#include <iostream>
using namespace std;

int moves = 0;

void hanoi(int n, char from, char via, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, via);
    cout << "Move disc " << n << " from " << from << " to " << to << endl;
    moves++;
    hanoi(n - 1, via, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    cout << "Total moves: " << moves << endl;
    return 0;
}

Output

Answer