Yesterday I wanted to try code some challenge. I chose the Tower of Hanoi.
Rules
Tee goal is to move discs from left tower to right tower with those rules:
- Only one disc can be moved at the time
- Each move moves the upper disc to another tower
- Disc can't be put on a smaller disc
Tower data structure
Because in every move you must take a top disc and put it as a top disc on another tower, the tower is stack.
class Tower {
constructor(stack, level) {
this._stack = stack || new Array();
this._level = level || 0;
}
push(value) {
const { length } = this._stack;
if (length && value > this._stack[length - 1]) {
throw new TypeError(
`Could not put bigger disk(${value}) on smaller(${
this._stack[length - 1]
})`
);
}
this._stack.push(value);
}
pop() {
if (this.isEmpty()) {
throw new TypeError("Tower is empty");
}
return this._stack.pop();
}
isEmpty() {
return this.getSize() <= 0;
}
getSize() {
return this._stack.length - this._level;
}
getUpperTower() {
return new Tower(this._stack, this._level + 1);
}
toArray() {
return [...this._stack];
}
}
Explanation
this._stack is an array that works as an inner stack.
this._level is level where tower starts.
In the algorithm, I will need to create sub towers without lower levels that share stack but start at different levels.
In the push method, I test if I am not putting a smaller disc on a bigger one and in the pop method I could not pop from an empty tower.
Methods isEmpty and getSize reflects the level where the tower starts.
Method getUpperTower returns the same tower that starts at a higher level.
And the last method toArray return stack as array from bottom to top for printing tower to console.
Solution
For the solution, I created a class TowerOfHanoi that creates the source tower with discs from n to 1 and two empty towers.
Method _print prints tower. Method solve is used to solve this puzzle.
Method _solve is a place where I will explain and implement a solution.
class TowerOfHanoi {
constructor(size) {
this._destinationTower = new Tower();
this._sourceTower = new Tower();
this._temporaryTower = new Tower();
this._printLength = String(size).length;
for (let i = size; i > 0; i--) {
this._sourceTower.push(i);
}
}
_print() {
const destinationArray = this._destinationTower.toArray();
const sourceArray = this._sourceTower.toArray();
const temporaryArray = this._temporaryTower.toArray();
const arrays = [sourceArray, temporaryArray, destinationArray];
const maxHeight = Math.max(
...[destinationArray.length, sourceArray.length, temporaryArray.length]
);
console.log("");
for (let i = maxHeight - 1; i >= 0; i--) {
const row = arrays
.map(array => String(array[i] || "").padStart(this._printLength, " "))
.join(" | ");
console.log(`| ${row} |`);
}
console.log("_".repeat(3 * this._printLength + 10));
}
_solve({ destinationTower, sourceTower, temporaryTower }) {}
solve() {
this._print();
this._solve({
destinationTower: this._destinationTower,
sourceTower: this._sourceTower,
temporaryTower: this._temporaryTower
});
}
}
Base case
If the source tower contains only 1 disc, the solution is moving this disc to the destination tower and the puzzle is solved.
_solve({ destinationTower, sourceTower, temporaryTower }) {
if (sourceTower.getSize() == 1) {
destinationTower.push(sourceTower.pop());
this._print();
return;
}
}
This works for size == 1.
Move upper discs
If all upper discs are move to the temporary tower then is possible to move the biggest disc to the destination tower.
Moving the upper disc to the temporary tower is the same as solving this puzzle for moving the source tower containing discs without the lowest disc to temporary disc.
The new source tower is the upper tower of the actual source tower that starts one level higher. The destination and temporary tower are exchanged.
_solve({ destinationTower, sourceTower, temporaryTower }) {
if (sourceTower.getSize() == 1) {
destinationTower.push(sourceTower.pop());
this._print();
return;
}
this._solve({
destinationTower: temporaryTower,
sourceTower: sourceTower.getUpperTower(),
temporaryTower: destinationTower
});
destinationTower.push(sourceTower.pop());
this._print();
}
This works for sizes 1 and 2.
Last step
After these steps, the source tower is empty, the temporary tower contains discs from n-1 to 1 and the destination tower contains n.
It looks like an original puzzle, but the source and the temporary towers are swapped. Because the destination tower contains only the biggest disc it is possible to ignore this disc and solve it as an original puzzle for n-1.
_solve({ destinationTower, sourceTower, temporaryTower }) {
if (sourceTower.getSize() == 1) {
destinationTower.push(sourceTower.pop());
this._print();
return;
}
this._solve({
destinationTower: temporaryTower,
sourceTower: sourceTower.getUpperTower(),
temporaryTower: destinationTower
});
destinationTower.push(sourceTower.pop());
this._print();
this._solve({
destinationTower: destinationTower.getUpperTower(),
sourceTower: temporaryTower,
temporaryTower: sourceTower
});
}
Top comments (0)