Assignment 7 - Recursion

by Mike Kerney

HTML

Mike Kerney<br/> Assignment #7- Recursion <br/>
<br/>
<br/> The complexity is 0(2^n). This is because the moves grow exponentially with each disk.<br/> It would take 584,868,233,155 years for a 64 disk solution to happen at one move per second. I, for one, am not concernced about the end of the world according
to this legend.
<br/>
<br/> Choose how many disks to use.<br/>
<select id="DiskNum" name="Disks">
                <option value="1">1</option>
                <option value="2">2</option>
                <option value="3">3</option>
                <option value="4">4</option>
                <option value="5">5</option>
                <option value="6">6</option>
                <option value="7">7</option>                
            </select>
<br/>
<input type="button" value="Set Up Disks" onclick="setDisks();" />
<input type="button" value="Tower of Hanoi" onclick="ToH(stack1.length, stack1, stack3, stack2);" />
<br/>
<div id="output1">

</div>
<div id="output2">
</div>
<div id="output3">
</div>

JavaScript

var count = 0;

var Node = function(_content) {
  this.content = _content;
  this.next = null;
  this.prev = null;
  return this;
};

var Stack = function(_content) {
  this.tail = null;
  this.head = null;
  this.length = 0;
  return this;
};

Stack.prototype.push = function(_content) {
  var newNode = new Node(_content);
  newNode.content = _content;

  if (this.head == null) {
    this.head = newNode;
    this.tail = this.head;
    this.length++;
    return this;
  }

  if (this.head == this.tail) {
    this.tail = newNode;
    this.tail.next = this.head;
    this.head.prev = this.tail;
    this.length++;
    return this;
  }

  this.tail.prev = newNode;
  newNode.next = this.tail;
  this.tail = newNode;
  this.length++;
  return this;
};

Stack.prototype.pop = function() {

  if (this.head == this.tail) {
    var node1 = this.tail;
    this.tail = null;
    this.head = null;
    this.length = 0;
    return node1;
  }

  var node2 = this.tail;
  this.tail = this.tail.next;
  this.tail.prev = null;
  this.length--;
  return node2;
};

Stack.prototype.print = function() {
  var string = "";
  var node = this.tail;

  while (node != null) {
    string += node.content;
    node = node.next;
  }
  return string;
};

var stack1 = new Stack();
var stack2 = new Stack();
var stack3 = new Stack();

function setDisks(n) {
  n = parseInt(document.getElementById("DiskNum").value);
  for (var i = n; i > 0; i--) {
    stack1.push(i);
  }
  document.getElementById('output1').innerHTML = 'Starting Tower: <br>Peg A: ' + stack1.print() + '    Peg B: ' + stack2.print() + '    Peg C: ' + stack3.print();
}

function ToH(n, peg1, peg3, peg2) {
  if (n >= 1) {
    ToH(n - 1, peg1, peg2, peg3);
    peg3.push(peg1.pop().content);
    count++;
    document.getElementById('output2').innerHTML += '<br>Peg A: ' + stack1.print() + '    Peg B: ' + stack2.print() + '    Peg C: ' + stack3.print();
    ToH(n - 1, peg2, peg3, peg1);
  }
  document.getElementById('output3').innerHTML = n + "...