Tower of Hanoi Problem in DSA Typescript - Build from Scratch

Tower of Hanoi Problem

📖 Scenario: Imagine you have three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest at the top, making a conical shape.Your task is to move the entire stack to another rod, obeying the following simple rules:Only one disk can be moved at a time.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.No disk may be placed on top of a smaller disk.

🎯 Goal: Build a TypeScript program that solves the Tower of Hanoi problem for 3 disks. The program should print each move step-by-step, showing which disk moves from which rod to which rod.

📋 What You'll Learn

Create variables to represent the rods and the number of disks.

Create a recursive function to solve the Tower of Hanoi problem.

Print each move in the format: 'Move disk X from rod Y to rod Z'.

💡 Why This Matters

🌍 Real World

The Tower of Hanoi problem helps understand recursion, a key concept in programming and problem solving.

💼 Career

Recursion is used in many software engineering tasks like parsing, searching, and algorithm design.

1

Setup rods and number of disks

Create a variable called numDisks and set it to 3. Also create three arrays called rodA, rodB, and rodC. Initialize rodA with disks numbered from 3 down to 1 (largest disk is 3, smallest is 1). Initialize rodB and rodC as empty arrays.

DSA Typescript

// Your code here

Hint

Use arrays to represent rods. The largest disk is 3 and should be first in rodA.

2

Create the recursive function signature

Create a function called towerOfHanoi that takes four parameters: n (number of disks), fromRod (string), toRod (string), and auxRod (string). The function should have no return value.

DSA Typescript

const numDisks = 3;
const rodA: number[] = [3, 2, 1];
const rodB: number[] = [];
const rodC: number[] = [];

// Define the towerOfHanoi function below
// Your code here

Hint

Define the function with the exact name and parameters as described.

3

Implement the recursive logic

Inside the towerOfHanoi function, implement the recursive logic: if n is 1, print Move disk 1 from rod {fromRod} to rod {toRod}. Otherwise, call towerOfHanoi recursively to move n-1 disks from fromRod to auxRod using toRod as auxiliary, then print the move of disk n from fromRod to toRod, then call towerOfHanoi recursively to move n-1 disks from auxRod to toRod using fromRod as auxiliary.

DSA Typescript

const numDisks = 3;
const rodA: number[] = [3, 2, 1];
const rodB: number[] = [];
const rodC: number[] = [];

function towerOfHanoi(n: number, fromRod: string, toRod: string, auxRod: string): void {
  // Implement recursive logic here
  // Your code here
}

Hint

Use recursion carefully to move smaller stacks first, then the largest disk, then the smaller stacks again.

4

Call the function and print the moves

Call the towerOfHanoi function with numDisks, 'A' as fromRod, 'C' as toRod, and 'B' as auxRod to print all the moves.

DSA Typescript

const numDisks = 3;
const rodA: number[] = [3, 2, 1];
const rodB: number[] = [];
const rodC: number[] = [];

function towerOfHanoi(n: number, fromRod: string, toRod: string, auxRod: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from rod ${fromRod} to rod ${toRod}`);
    return;
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod);
  console.log(`Move disk ${n} from rod ${fromRod} to rod ${toRod}`);
  towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

// Call the function below
// Your code here

Hint

Call the function with the correct arguments to see the moves printed.

Practice

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

easy

A. 6

B. 7

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 B

4. Quick Check:

   2^3 - 1 = 7 [OK]

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

Common Mistakes:

• Forgetting to subtract 1
• Using n instead of 2^n
• Confusing moves with disks

2. Which of the following is the correct TypeScript function signature for solving Tower of Hanoi recursively?

easy

A. function towerOfHanoi(n: number, from: string, to: string, aux: string): void

B. function towerOfHanoi(n: string, from: number, to: number, aux: number): number

C. function towerOfHanoi(n: number, from: number, to: number): void

D. function towerOfHanoi(n: number): string

Solution

1. Step 1: Identify parameters needed for Tower of Hanoi

   We need number of disks (number), source peg (string), destination peg (string), and auxiliary peg (string).

2. Step 2: Match with function signature

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void matches all parameters with correct types and returns void as it prints moves.

3. Final Answer:

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void -> Option A

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Check parameter types and count carefully [OK]

Common Mistakes:

• Using wrong parameter types
• Missing auxiliary peg parameter
• Wrong return type

3. What will be the output of the following TypeScript code snippet for Tower of Hanoi with 2 disks?

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}
towerOfHanoi(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 B to C
Move disk 2 from A to C
Move disk 1 from A to B

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

Solution

1. Step 1: Trace first recursive call with n=2

   Call towerOfHanoi(1, 'A', 'B', 'C') prints "Move disk 1 from A to B".

2. Step 2: Print move for disk 2

   Prints "Move disk 2 from A to C".

3. Step 3: Trace second recursive call with n=1

   Call towerOfHanoi(1, 'B', 'C', 'A') prints "Move disk 1 from B to C".

4. Final Answer:

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

5. Quick Check:

   Follow recursion steps carefully [OK]

Hint: Follow recursion calls step-by-step [OK]

Common Mistakes:

• Mixing source and auxiliary pegs
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in this Tower of Hanoi TypeScript function and select the fix:

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 0) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Change base case to if (n === 1) and print move for disk 1

B. Change base case to if (n === 0) and remove print statement

C. Remove recursive calls and only print moves

D. Change print statement to print disk 0

Solution

1. Step 1: Analyze base case condition

   Base case should be when n equals 1, not 0, because disk numbering starts at 1.

2. Step 2: Fix base case and print statement

   Change if (n === 0) to if (n === 1) and print move for disk 1.

3. Final Answer:

   Change base case to if (n === 1) and print move for disk 1 -> Option A

4. Quick Check:

   Base case must handle smallest disk [OK]

Hint: Base case is n === 1, not zero [OK]

Common Mistakes:

• Using n === 0 as base case
• Printing move for disk 1 in wrong place
• Skipping base case

5. You want to solve Tower of Hanoi for 4 disks but only print moves where disk 1 is moved. Which modification to the recursive function is correct?

hard

A. Print all moves and filter disk 1 moves after recursion

B. Remove all recursive calls except for n=1

C. Add condition to print only if disk number is 1 inside the print statement

D. Change base case to n=2 and print only disk 1 moves

Solution

1. Step 1: Understand requirement to print only disk 1 moves

   We must keep recursion intact but print moves only when disk number is 1.

2. Step 2: Modify print statement with condition

   Add if (n === 1) before printing move to filter only disk 1 moves.

3. Final Answer:

   Add condition to print only if disk number is 1 inside the print statement -> Option C

4. Quick Check:

   Filter print, keep recursion [OK]

Hint: Use if condition inside print to filter moves [OK]

Common Mistakes:

• Removing recursive calls breaks solution
• Filtering moves after recursion wastes time
• Changing base case incorrectly