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.