Skip to content

Instantly share code, notes, and snippets.

@voila voila/hanoi.js
Last active Jul 3, 2019

Embed
What would you like to do?
Hanoi Tower recursive to iterative
// recursive
const hanoi0 = (n, a, b, c) => {
if (n > 0) {
hanoi0(n - 1, a, c, b);
console.log(`${a} ==> ${c}`);
hanoi0(n - 1, b, a, c);
}
}
hanoi0(3, "a", "b", "c");
console.log("--------------------");
// CPS style
const hanoi1 = (n, a, b, c, k) => {
if (n > 0) {
hanoi1(n - 1, a, c, b,
() => {
console.log(`${a} ==> ${c}`);
hanoi1(n - 1, b, a, c, k);
});
}
else {
k();
}
}
hanoi1(3, "a", "b", "c", () => { });
console.log("--------------------");
// CPS style
const hanoi2 = (n, a, b, c, k) => {
if (n > 0) {
hanoi2(n - 1, a, c, b,
() => {
console.log(`${a} ==> ${c}`);
hanoi2(n - 1, b, a, c, k);
});
}
else {
k();
}
}
hanoi2(3, "a", "b", "c", () => { });
console.log("--------------------");
// Defunctionalising the continuation
// type cont = {n:int , a:string, b:string, c:string, next:cont} | null
const hanoi3 = (n, a, b, c, k) => {
while (true) {
if (n > 0) {
k = { n: n, a: a, b: b, c: c, next: k }; // new cont (stack push)
[a, b, c] = [a, c, b];
n = n - 1;
} else {
if (k != null) {
console.log(`${k.a} ==> ${k.c}`);
[a, b, c] = [k.b, k.a, k.c];
n = k.n - 1;
k = k.next; // (stack pop)
}
else {
return;
}
}
}
}
hanoi3(3, "a", "b", "c", null);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.