Tower of Hanoi Problem in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to print the move from source to destination peg.

DSA Rust

println!("Move disk from peg [1] to peg B");

Drag options to blanks, or click blank then click option'

A"destination"

B"source"

C"C"

D"A"

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable names instead of peg labels.

Confusing source and destination pegs.

The source peg is labeled "A" in the Tower of Hanoi problem, so the move is from peg "A" to peg B.

2fill in blank

medium

Complete the code to recursively call the function to move n-1 disks.

DSA Rust

hanoi([1] - 1, source, auxiliary, destination);

Drag options to blanks, or click blank then click option'

An

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n - 1.

Using n + 1 which is incorrect.

To move n-1 disks, we subtract 1 from n in the recursive call.

3fill in blank

hard

Fix the error in the base case condition to stop recursion when no disks remain.

DSA Rust

if [1] == 0 { return; }

Drag options to blanks, or click blank then click option'

Adestination

Bsource

Cn

Dauxiliary

Attempts:

3 left

💡 Hint

Common Mistakes

Checking pegs instead of number of disks.

Using wrong variable names in condition.

The base case checks if n (number of disks) is zero to stop recursion.

4fill in blank

hard

Fill both blanks to print the move from source to destination peg correctly.

DSA Rust

println!("Move disk from peg [1] to peg [2]");

Drag options to blanks, or click blank then click option'

Asource

Bdestination

C"A"

D"B"

Attempts:

3 left

💡 Hint

Common Mistakes

Using string literals instead of variables.

Swapping source and destination.

The move is from the source peg to the destination peg, so print source and destination variables.

5fill in blank

hard

Fill all four blanks to complete the recursive Tower of Hanoi function call correctly.

DSA Rust

hanoi([1] - 1, [2], [3], [4]);

Drag options to blanks, or click blank then click option'

An

Bsource

Cauxiliary

Ddestination

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up auxiliary and destination pegs.

Using wrong values for n or pegs.

To move n-1 disks from auxiliary to destination using source, call hanoi(n-1, auxiliary, destination, source).

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