The Tower of Hanoi is a classic problem in computer science and programming that involves moving a series of disks from one peg to another, following specific rules. To implement this challenge effectively, we can utilize a stack data structure. In this article, we will discuss how to create a TypeScript class that represents a stack and how it can be applied to solve the Tower of Hanoi problem.
The Problem Scenario
The Tower of Hanoi consists of three pegs and a number of disks of different sizes that can slide onto any peg. The puzzle starts with the disks stacked in ascending order on one peg (the smallest disk on top). The objective is to move the entire stack to another peg, following these 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 an empty peg.
- No larger disk may be placed on top of a smaller disk.
Original Code
Here is a simple example of a TypeScript class for a stack, which can be utilized to implement the Tower of Hanoi solution:
class Stack<T> {
private items: T[];
constructor() {
this.items = [];
}
push(item: T): void {
this.items.push(item);
}
pop(): T | undefined {
return this.items.pop();
}
peek(): T | undefined {
return this.items[this.items.length - 1];
}
isEmpty(): boolean {
return this.items.length === 0;
}
size(): number {
return this.items.length;
}
}
Analyzing the Stack Class
The Stack<T> class above is a generic implementation of a stack data structure. Let's break down its functionality:
- Constructor: Initializes an empty array to store stack items.
- push: Adds an item to the top of the stack.
- pop: Removes the item from the top of the stack and returns it.
- peek: Returns the top item of the stack without removing it.
- isEmpty: Checks whether the stack is empty.
- size: Returns the number of items in the stack.
Practical Example: Solving the Tower of Hanoi
Now that we have our stack implementation, we can use it to solve the Tower of Hanoi problem. Here’s a basic approach to implement the solution using our stack:
class TowerOfHanoi {
private pegs: Stack<number>[];
constructor(numDisks: number) {
this.pegs = [new Stack<number>(), new Stack<number>(), new Stack<number>()];
for (let i = numDisks; i >= 1; i--) {
this.pegs[0].push(i);
}
}
solve(numDisks: number, source: number, target: number, auxiliary: number) {
if (numDisks === 1) {
const disk = this.pegs[source].pop();
if (disk) {
this.pegs[target].push(disk);
}
} else {
this.solve(numDisks - 1, source, auxiliary, target);
this.solve(1, source, target, auxiliary);
this.solve(numDisks - 1, auxiliary, target, source);
}
}
displayPegs() {
console.log("Pegs state:");
for (let i = 0; i < this.pegs.length; i++) {
console.log(`Peg ${i + 1}: ${this.pegs[i].size()} disks`);
}
}
}
const hanoi = new TowerOfHanoi(3);
hanoi.solve(3, 0, 1, 2);
hanoi.displayPegs();
Explanation of the Solution
- Constructor: Initializes three stacks (pegs) and populates the first peg with disks.
- solve: A recursive method that implements the algorithm for solving the Tower of Hanoi. It moves disks between pegs based on the recursive rules.
- displayPegs: A helper method to visualize the state of the pegs after solving the puzzle.
Conclusion
The Tower of Hanoi is an excellent example of recursion and data structures in programming. By using a stack in our TypeScript implementation, we can effectively manage the disks and pegs, allowing us to develop a clear and efficient solution.
This implementation highlights the power of TypeScript’s type system and its ability to create clean and reusable components. The stack class can be utilized in many other programming problems and is an essential building block for understanding more complex data structures.
Useful Resources
By understanding the basics of stacks and the Tower of Hanoi problem, developers can enhance their programming skills and tackle more complex challenges with confidence.
