Skip to content

Instantly share code, notes, and snippets.

@mpenkov

mpenkov/hanoi.html

Last active December 12, 2015 06:28
Show Gist options
  • Save mpenkov/4729088 to your computer and use it in GitHub Desktop.
Save mpenkov/4729088 to your computer and use it in GitHub Desktop.
Download ZIP
Coding Interview Practice: Stacks
Raw
hanoi.html
<!--
vim: shiftwidth=2
-->
<html>
<head>
<title>Tower of Hanoi</title>
</head>
<body>
<script src="hanoi.js"></script>
Number of disks:
<input id="number" type="number" value="3"/>
<input type="button" value="Initialize" onclick="initialize();"/>
<input id="btnForward" type="button" value="Step forward" disabled="true" onClick="onForward();"/>
<input id="btnBack" type="button" value="Step back" disabled="true" onClick="onBack();"/>
<br/>
<textarea id="textArea" readonly="true" rows="5" cols="50" style="display: none;"></textarea>
<br/>
<svg id="stack1" width="200" height="100" viewBox="0 0 200 100"></svg>
<svg id="stack2" width="200" height="100" viewBox="0 0 200 100"></svg>
<svg id="stack3" width="200" height="100" viewBox="0 0 200 100"></svg>
</body>
</html>
Raw
hanoi.js
// vim: shiftwidth=2
//
// Lessons learnt:
//
// - objects must be instantiated with the "new" keyword. Without it, the
// constructor won't get called properly.
// - use [] instead of new Array() (not sure why, JSFiddle told me so)
// - use === instead of == to compare with null, undefined and numeric values (ditto)
// - don't forget to end lines with semicolon (apparently it's a convention)
// - use {} instead of new Object()
var path;
var currentStep;
var N;
function initialize() {
N = document.getElementById("number").value;
document.getElementById("btnForward").disabled = false;
document.getElementById("btnBack").disabled = false;
var root = new Node(null);
root.towers = Array(3);
root.towers[0] = new Stack();
for (var i = 0; i < N; ++i)
root.towers[0].push(N-i);
root.towers[1] = new Stack();
root.towers[2] = new Stack();
var target = bfs(root);
var count = 0;
path = [];
for (var node = target; node; node = node.parentNode) {
if (node.tmp === null) {
// Ignore nodes where we've temporarily removed a ring.
path[count++] = node;
}
}
path.reverse();
currentStep = 0;
redraw();
}
function onForward() {
if (currentStep < path.length)
++currentStep;
redraw();
}
function onBack() {
if (currentStep > 0)
--currentStep;
redraw();
}
function redraw() {
var currentTowers = path[currentStep].towers;
var textArea = document.getElementById("textArea");
textArea.value = "";
for (var i = 0; i < 3; ++i)
textArea.value += (i+1) + ": " + currentTowers[i].toString() + "\n";
document.getElementById("btnForward").disabled = currentStep >= path.length - 1;
document.getElementById("btnBack").disabled = currentStep === 0;
var stack1 = document.getElementById("stack1");
var stack2 = document.getElementById("stack2");
var stack3 = document.getElementById("stack3");
redrawStack(stack1, path[currentStep].towers[0]);
redrawStack(stack2, path[currentStep].towers[1]);
redrawStack(stack3, path[currentStep].towers[2]);
}
// Clears the specified SVG element and draws the specified stack onto it
function redrawStack(svg, stack) {
var svgns = "http://www.w3.org/2000/svg";
while (svg.firstChild)
svg.removeChild(svg.firstChild);
var values = [];
for (var elt = stack.top_; elt != null; elt = elt.next)
values.push(elt.item);
values = values.reverse();
var width = svg.width.baseVal.value;
var height = svg.height.baseVal.value;
// some padding
width -= 2;
height -= 2;
var axis = document.createElementNS(svgns, "line");
axis.setAttribute("x1", width/2);
axis.setAttribute("y1", 0);
axis.setAttribute("x2", width/2);
axis.setAttribute("y2", height);
axis.setAttribute("style", "stroke: black; stroke-width: 2");
svg.appendChild(axis);
// some more padding
var width_inc = width/N/1.5;
var curr_disc = 1;
for (var i = 0; i < values.length; ++i) {
var rect = document.createElementNS(svgns, "rect");
var rect_width = values[i]*width_inc;
// leave some space at the top of each stack for the spindle
var rect_height = (height-10)/N;
rect.setAttribute("x", (width-rect_width)/2);
rect.setAttribute("y", height - (curr_disc*rect_height));
rect.setAttribute("width", rect_width);
rect.setAttribute("height", rect_height);
rect.setAttribute("style", "fill: red; stroke: black; stroke-width: 2"); // get a pallette
svg.appendChild(rect);
curr_disc += 1;
}
return svg;
}
//
// from http://stackoverflow.com/questions/122102/what-is-the-most-efficient-way-to-clone-a-javascript-object
var clone = function() {
var newObj = (this instanceof Array) ? [] : {};
for (var i in this) {
if (this[i] && typeof this[i] == "object") {
newObj[i] = this[i].clone();
} else {
newObj[i] = this[i];
}
} return newObj;
};
Object.defineProperty( Object.prototype, "clone", {value: clone, enumerable: false});
function Stack() {
this.top_ = null; // "top" seems to be a keyword
}
function Element(x) {
this.item = x;
this.next = null;
}
Stack.prototype.push = function(x) {
var elt = new Element(x);
elt.next = this.top_;
this.top_ = elt;
};
Stack.prototype.pop = function() {
var elt = this.top_;
if (elt === null)
throw new Error("stack must not be empty");
this.top_ = elt.next;
return elt.item;
};
Stack.prototype.isEmpty = function() {
return this.top_ === null;
};
Stack.prototype.toString = function() {
var arr = [];
var idx = 0;
for (var j = this.top_; j; j = j.next)
arr[idx++] = j.item;
return arr.reverse().join(" ");
};
Stack.prototype.peek = function() {
if (this.top_)
return this.top_.item;
throw new Error("stack must not be empty");
};
Stack.prototype.isEmpty = function() {
return this.top_ === null;
};
function Queue() {
this.front = null;
this.back = null;
}
Queue.prototype.push = function(x) {
var elt = new Element(x);
if (!this.front) {
this.front = elt;
this.back = elt;
} else {
this.back.next = elt;
this.back = elt;
}
};
Queue.prototype.pop = function() {
if (this.isEmpty())
throw new Error("queue must not be empty");
var front = this.front;
if (this.front == this.back) {
this.front = null;
this.back = null;
} else {
this.front = front.next;
}
return front.item;
};
Queue.prototype.isEmpty = function() {
return this.front === null;
};
Queue.prototype.length = function() {
var length = 0;
for (var i = this.front; i; i = i.next)
length += 1;
return length;
};
function Node(parentNode) {
this.parentNode = parentNode;
if (parentNode)
this.towers = parentNode.towers.clone();
else
this.towers = null;
this.tmp = null;
}
Node.prototype.getChildren = function() {
var children = [];
var ci = 0;
var i;
var child;
if (this.tmp) {
for (i = 0; i < this.towers.length; ++i) {
if (!this.towers[i].isEmpty() && this.towers[i].peek() < this.tmp) {
continue;
}
child = new Node(this);
child.towers[i].push(this.tmp);
children[ci++] = child;
}
} else {
for (i = 0; i < this.towers.length; ++i) {
if (this.towers[i].isEmpty())
continue;
child = new Node(this);
child.tmp = child.towers[i].pop();
children[ci++] = child;
}
}
return children;
};
Node.prototype.toString = function() {
var s = "";
for (var i = 0; i < 3; ++i)
s += this.towers[i].toString() + "; ";
return s + "tmp = " + this.tmp;
};
function bfs(root) {
var queue = new Queue();
var visited = new Object();
queue.push(root);
while (!queue.isEmpty()) {
var node = queue.pop();
visited[node.toString()] = true;
if (bfs_success(node.towers, node.tmp))
return node;
var children = node.getChildren();
if (children.length == 0)
continue;
for (var c = 0; c < children.length; ++c) {
if (visited[children[c].toString()] == undefined)
queue.push(children[c]);
}
}
return null;
}
function bfs_success(towers, tmp) {
return towers[0].isEmpty() && towers[1].isEmpty() && tmp === null;
}
Raw
hanoi.py
#
# Lessons learned:
#
# - copy.copy vs copy.deepcopy
# - built-in hash function can't hash lists (convert to tuples first)
#
import copy
def dfs(node, visited):
towers, tmp, path = node
if end_search(towers, tmp):
# we've reached our goal
#print "done!", towers
return path
visited.add(hash_node(node))
children = expand_node(node, visited)
if not children:
# prune the tree here -- no new children to visit
#print "pruned"
return None
for c in children:
p = dfs(c, visited)
if p:
# early exit
return p
return None
def end_search(towers, tmp):
# the search ends once the first two towers are empty.
# this implies all the rings are on the third tower.
return not (towers[0] or towers[1]) and not tmp
def expand_node(node, visited):
towers, tmp, path = node
#print towers, tmp
children = list()
if tmp:
# must push to one of the stacks
for i, t in enumerate(towers):
if t and t[0] < tmp:
# can't push here
continue
ctowers = copy.deepcopy(towers)
stack_push(ctowers[i], tmp)
children.append((ctowers, None, path + [i]))
else:
# must pop from one of the stacks
for i, t in enumerate(towers):
if not t:
# can't pop from here
continue
ctowers = copy.deepcopy(towers)
popped = stack_pop(ctowers[i])
children.append((ctowers, popped, path + [i+3]))
return filter(lambda x: hash_node(x) not in visited, children)
def stack_pop(stack):
# top of stack is front of list
return stack.pop(0)
def stack_push(stack, x):
stack.insert(0, x)
def hash_node(node):
towers, tmp, path = node
tup = (tuple(map(tuple, towers)), tmp)
return hash(tup)
if __name__ == "__main__":
# values more than this exceed the maximum allowed recursion depth...
N = 6
root = ((range(1,N+1), list(), list()), None, list())
path = dfs(root, set())
actions = {0: "push to 1", 1: "push to 2", 2: "push to 3",
3: "pop from 1", 4: "pop from 2", 5: "pop from 3"}
print "\n".join(map(lambda x: actions[x], path))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment