Tower of Hanoi Problem in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tower of Hanoi moves for 2 disks

What is the printed sequence of moves when solving Tower of Hanoi with 2 disks from peg A to peg C using peg B as auxiliary?

DSA Rust

fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) {
    if n == 1 {
        println!("Move disk 1 from {} to {}", from, to);
        return;
    }
    tower_of_hanoi(n - 1, from, aux, to);
    println!("Move disk {} from {} to {}", n, from, to);
    tower_of_hanoi(n - 1, aux, to, from);
}

fn main() {
    tower_of_hanoi(2, 'A', 'C', 'B');
}

A

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

B

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B

C

Move disk 2 from A to B
Move disk 1 from A to C
Move disk 2 from B to C

D

Move disk 1 from B to C
Move disk 2 from A to C
Move disk 1 from A to B

💡 Hint

Remember the recursive steps: move n-1 disks to auxiliary, move largest disk, then move n-1 disks to target.

The Tower of Hanoi solution for 2 disks moves disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

🧠 Conceptual

intermediate

Minimum moves required for Tower of Hanoi with 4 disks

How many minimum moves are required to solve the Tower of Hanoi problem with 4 disks?

A 16

B 8

C 31

D 15

💡 Hint

The formula for minimum moves is 2^n - 1, where n is the number of disks.

For 4 disks, minimum moves = 2^4 - 1 = 16 - 1 = 15.

❓ Predict Output

advanced

Output of Tower of Hanoi moves for 3 disks with peg names X, Y, Z

What is the printed sequence of moves when solving Tower of Hanoi with 3 disks from peg X to peg Z using peg Y as auxiliary?

DSA Rust

fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) {
    if n == 1 {
        println!("Move disk 1 from {} to {}", from, to);
        return;
    }
    tower_of_hanoi(n - 1, from, aux, to);
    println!("Move disk {} from {} to {}", n, from, to);
    tower_of_hanoi(n - 1, aux, to, from);
}

fn main() {
    tower_of_hanoi(3, 'X', 'Z', 'Y');
}

A

Move disk 1 from X to Y
Move disk 2 from X to Z
Move disk 1 from Y to Z
Move disk 3 from X to Y
Move disk 1 from Z to X
Move disk 2 from Z to Y
Move disk 1 from X to Y

B

Move disk 1 from X to Z
Move disk 2 from X to Y
Move disk 1 from Z to Y
Move disk 3 from X to Z
Move disk 1 from Y to X
Move disk 2 from Y to Z
Move disk 1 from X to Z

C

Move disk 1 from X to Y
Move disk 2 from X to Z
Move disk 1 from Y to Z
Move disk 3 from X to Z
Move disk 1 from Z to Y
Move disk 2 from Z to X
Move disk 1 from Y to X

D

Move disk 1 from X to Y
Move disk 2 from X to Y
Move disk 1 from Y to Z
Move disk 3 from X to Z
Move disk 1 from Y to X
Move disk 2 from Y to Z
Move disk 1 from X to Z

💡 Hint

Follow the recursive pattern carefully for 3 disks.

The correct sequence follows the recursive steps moving n-1 disks to auxiliary, largest disk to target, then n-1 disks to target.

🔧 Debug

advanced

Identify the error in Tower of Hanoi recursive function

What error will this Rust code produce when running the Tower of Hanoi function with n=3? fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) { if n == 0 { println!("Move disk 1 from {} to {}", from, to); } tower_of_hanoi(n - 1, from, aux, to); println!("Move disk {} from {} to {}", n, from, to); tower_of_hanoi(n - 1, aux, to, from); } fn main() { tower_of_hanoi(3, 'A', 'C', 'B'); }

A Runtime panic: index out of bounds

B No output, function returns immediately

C Stack overflow due to infinite recursion

D Compilation error: mismatched types

💡 Hint

Check the base case condition for recursion termination.

The base case checks for n == 0 but prints move for disk 1, causing infinite recursion when n reaches 0.

🧠 Conceptual

expert

Number of moves for Tower of Hanoi with 10 disks

What is the minimum number of moves required to solve the Tower of Hanoi problem with 10 disks?

A 8191

B 1023

C 4095

D 2047

💡 Hint

Use the formula 2^n - 1 for n disks.

For 10 disks, minimum moves = 2^10 - 1 = 1024 - 1 = 1023.

Practice

1. What is the minimum number of moves required to solve the Tower of Hanoi problem with 3 disks?

easy

A. 7

B. 6

C. 8

D. 9

Solution

1. Step 1: Understand the formula for minimum moves

   The minimum moves required for n disks is 2^n - 1.

2. Step 2: Calculate for 3 disks

   For 3 disks, minimum moves = 2^3 - 1 = 8 - 1 = 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Calculating 2*n - 1 instead of 2^n - 1
• Confusing number of disks with moves
• Choosing the next integer after 7

2. Which of the following Rust function signatures correctly represents the Tower of Hanoi recursive function for moving disks?

easy

A. fn tower_of_hanoi(n: i32, from: String, to: String)

B. fn tower_of_hanoi(n: u32, from: char, to: char, aux: char)

C. fn tower_of_hanoi(n: u32, from: i32, to: i32, aux: i32)

D. fn tower_of_hanoi(n: u32, from: char, to: char)

Solution

1. Step 1: Identify correct parameter types

   The function needs number of disks (u32) and three rods (chars) to represent pegs.

2. Step 2: Check function signature options

   fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) uses u32 for disks and char for rods, matching common Tower of Hanoi implementations.

3. Final Answer:

   fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) -> Option B

4. Quick Check:

   Correct parameter types and count [OK]

Hint: Use u32 for disks and char for rods in signature [OK]

Common Mistakes:

• Using String instead of char for rods
• Missing auxiliary rod parameter
• Using signed integer for disk count

3. What will be the output sequence of moves for the Tower of Hanoi function call tower_of_hanoi(2, 'A', 'C', 'B')?

medium

A. Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B

B. Move disk 2 from A to B
Move disk 1 from A to C
Move disk 2 from B to C

C. Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

D. Move disk 1 from B to C
Move disk 2 from A to C
Move disk 1 from A to B

Solution

1. Step 1: Understand the recursive steps for 2 disks

   Move disk 1 from source to auxiliary, move disk 2 from source to target, then move disk 1 from auxiliary to target.

2. Step 2: Apply to given rods

   From 'A' to 'B' (aux), then 'A' to 'C' (target), then 'B' to 'C' (target).

3. Final Answer:

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C -> Option C

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: For 2 disks, move small to aux, big to target, small to target [OK]

Common Mistakes:

• Swapping auxiliary and target rods
• Reversing move order
• Confusing disk numbers

4. Identify the error in this Rust Tower of Hanoi recursive function snippet:

fn tower_of_hanoi(n: u32, from: char, to: char, aux: char) {
    if n == 0 {
        return;
    }
    tower_of_hanoi(n - 1, from, to, aux);
    println!("Move disk {} from {} to {}", n, from, to);
    tower_of_hanoi(n - 1, aux, to, from);
}

medium

A. The recursive calls have incorrect rod parameters swapped

B. The println! macro syntax is incorrect

C. The function does not return any value but should return an integer

D. The base case should be n == 1, not n == 0

Solution

1. Step 1: Recall standard Tower of Hanoi recursion

   To move n disks from src to dst using aux: move n-1 src->aux using dst; move n src->dst; move n-1 aux->dst using src.

2. Step 2: Check first recursive call

   Code has tower_of_hanoi(n-1, from, to, aux); but should be tower_of_hanoi(n-1, from, aux, to); dst and aux swapped in first call.

3. Step 3: Other parts correct

   Base case n==0 fine for u32; println! syntax correct; second recursive call correct.

4. Final Answer:

   The recursive calls have incorrect rod parameters swapped -> Option A

5. Quick Check:

   First call: dst/aux swapped [OK]

Hint: Check order of rods in recursive calls carefully [OK]

Common Mistakes:

• Confusing base case condition
• Mixing up source, target, auxiliary rods
• Expecting return value in void function

5. You want to solve the Tower of Hanoi problem for 4 disks but only have 2 rods available. What is the minimum number of moves required?

hard

A. 15

B. 31

C. 7

D. Impossible to solve with 2 rods

Solution

1. Step 1: Understand Tower of Hanoi rod requirements

   The classic Tower of Hanoi problem requires 3 rods to move disks following the rules.

2. Step 2: Check if 2 rods suffice

   With only 2 rods, it is impossible to move all disks without breaking the rules (no larger disk on smaller disk).

3. Final Answer:

   Impossible to solve with 2 rods -> Option D

4. Quick Check:

   Minimum rods needed = 3 [OK]

Hint: Tower of Hanoi needs 3 rods; 2 rods can't solve it [OK]

Common Mistakes:

• Applying formula 2^n - 1 without checking rods
• Assuming fewer rods still work
• Confusing rods with disks