forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
hanoiTower.js
84 lines (77 loc) · 2.07 KB
/
hanoiTower.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import Stack from '../../../data-structures/stack/Stack';
/**
* @param {number} numberOfDiscs
* @param {Stack} fromPole
* @param {Stack} withPole
* @param {Stack} toPole
* @param {function(disc: number, fromPole: number[], toPole: number[])} moveCallback
*/
function hanoiTowerRecursive({
numberOfDiscs,
fromPole,
withPole,
toPole,
moveCallback,
}) {
if (numberOfDiscs === 1) {
// Base case with just one disc.
moveCallback(fromPole.peek(), fromPole.toArray(), toPole.toArray());
const disc = fromPole.pop();
toPole.push(disc);
} else {
// In case if there are more discs then move them recursively.
// Expose the bottom disc on fromPole stack.
hanoiTowerRecursive({
numberOfDiscs: numberOfDiscs - 1,
fromPole,
withPole: toPole,
toPole: withPole,
moveCallback,
});
// Move the disc that was exposed to its final destination.
hanoiTowerRecursive({
numberOfDiscs: 1,
fromPole,
withPole,
toPole,
moveCallback,
});
// Move temporary tower from auxiliary pole to its final destination.
hanoiTowerRecursive({
numberOfDiscs: numberOfDiscs - 1,
fromPole: withPole,
withPole: fromPole,
toPole,
moveCallback,
});
}
}
/**
* @param {number} numberOfDiscs
* @param {function(disc: number, fromPole: number[], toPole: number[])} moveCallback
* @param {Stack} [fromPole]
* @param {Stack} [withPole]
* @param {Stack} [toPole]
*/
export default function hanoiTower({
numberOfDiscs,
moveCallback,
fromPole = new Stack(),
withPole = new Stack(),
toPole = new Stack(),
}) {
// Each of three poles of Tower of Hanoi puzzle is represented as a stack
// that might contain elements (discs). Each disc is represented as a number.
// Larger discs have bigger number equivalent.
// Let's create the discs and put them to the fromPole.
for (let discSize = numberOfDiscs; discSize > 0; discSize -= 1) {
fromPole.push(discSize);
}
hanoiTowerRecursive({
numberOfDiscs,
fromPole,
withPole,
toPole,
moveCallback,
});
}