Tower of Hanoi Move Sequence

You are given N disks stacked in decreasing size order (disk N is the largest, disk 1 the smallest) on rod A. Using the classic three-rod puzzle rules - move exactly one disk at a time, only ever move the topmost disk of a rod, and never place a larger disk on top of a smaller one - move all N disks from rod A to rod C, using rod B as an auxiliary. Print the minimum number of moves required, followed by each move in order.

Input: A single line containing the integer N. Output: The first line contains a single integer, the minimum number of moves (2^N - 1). Each following line describes one move in the format "Move disk D from X to Y", where D is the disk number and X, Y are rod names among A, B, C.

1 <= N <= 12.

This is one of the most famous illustrations of how a recursive definition can directly mirror a problem's own self-similar structure - the puzzle 'naturally wants' to be described recursively, which is exactly why the recursive solution feels so elegant compared to any iterative alternative.

Move a stack of differently-sized disks from one rod to another, using a third as a helper, printing every move needed. Brute force: There isn't really a simpler non-recursive way to generate the exact optimal move sequence directly - the recursive three-step structure (move N-1 aside, move the biggest disk, move N-1 back) IS the natural, minimal solution. Optimised: The recursive definition directly captures the puzzle's OWN self-similar structure: solving the N-disk puzzle reduces to solving TWO smaller (N-1)-disk puzzles (with a different auxiliary rod each time) plus one single disk move - this recursive decomposition is both the SIMPLEST way to think about the problem and provably produces the MINIMUM number of moves (2^N - 1).

1. To move N disks from rod A to rod C: FIRST move the top N-1 disks from A to B (using C as the temporary auxiliary). 2. THEN move disk N (the single largest, now-exposed disk) directly from A to C. 3. FINALLY move the N-1 disks from B to C (using A as the temporary auxiliary this time) - this recursive three-step structure directly produces the entire move sequence.

Time: O(2^N) - the total number of moves printed, since each additional disk roughly doubles the required move count. Space: O(N), for the recursion call stack (depth proportional to the number of disks).

N = 1 requires exactly 1 move: "Move disk 1 from A to C". N = 12 requires 4095 moves and is the largest input this problem is tested with.

Be ready to derive the minimum move count formula (2^N - 1) from the recurrence moves(N) = 2*moves(N-1) + 1 - a common follow-up alongside actually generating the sequence.