Towers of Hanoi

Lab Java Advanced 30 points

Read n and print the moves for Towers of Hanoi from A to C via B (A -> C), then the 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

Java

Hints

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

Solution explanation

The number of moves is 2ⁿ − 1. Collecting output in a StringBuilder is much faster than many small prints.

Show solution

import java.util.Scanner;

public class Main {
    static int moves = 0;
    static StringBuilder out = new StringBuilder();

    static void hanoi(int n, char from, char via, char to) {
        if (n == 0) {
            return;
        }
        hanoi(n - 1, from, to, via);
        out.append(from).append(" -> ").append(to).append('\n');
        moves++;
        hanoi(n - 1, via, from, to);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        moves = 0;
        out.setLength(0);
        hanoi(sc.nextInt(), 'A', 'B', 'C');
        System.out.print(out);
        System.out.println(moves);
    }
}

Output

Answer