mpenkov/hanoi.html

## 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>

## 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;
}

## 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))
	<!--
	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>
	// 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;
	}
	#
	# 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))