Solving Tower Of Hanoi problem

Hello Friends,

Lets see how to solve the famous tower of Hanoi Problem.

Suppose there are three Pegs (or towers), namely Source, Middle and Destination. Initially peg A has few  disks stacked on it. The stack of the disks are such that the largest disk is at the bottom. As we move towards the top the size of the disks decreases.

The objective of this problem is to shift the disks from Source to destination using middle Peg using below rules.

Only one Disk can be shifted from one Peg to another. A Disk can not be added to the peg if the size of the disk at the top of that Stack is less than the size of the disk we wish to add.

Lets See the code below :)

For the understanding we will use a class Tower which will be implementation of Stack.

public class Tower {
  int tower[];
  int numDisks;
  int top = -1;
  String name;

  public Tower(int numDisks, String name) {
   this.numDisks = numDisks;
   tower = new int[numDisks];
   this.name = name;
  }

  public void addDisk(int disk) {
   System.out.println("adding   "+disk+" on tower   : "+name);
   tower[++top] = disk;
  }

  public int removeDiskOnTop() {
   int diskOnTop = tower[top];
   System.out.println("removing "+diskOnTop+" from tower : "+name);
   top--;
   return diskOnTop;
  }

  public void print() {
   if (top == -1) {
    System.out.println(name + " Tower is empty");
   } else {
    System.out.print(name + " tower contains... ");
    for (int i = 0; i <= top; i++) {
     System.out.print(tower[i] + " ");
    }
    System.out.println();
   }
  }
}

Now lets create a class TowerOfHanoi  and put above defined class Tower in it as an static inner class and solve Tower of Hanoi [initial version for understanding, we will see final implementation after this.]

See How tower of Hanoi is solved for number of disks  equal to 2 , or 3 or 4 and how the solution solving the Tower of Hanoi with number of disks equal to 3 is used to solve the problem for number of disks = 4. Like wise note how problem for number of disks = 2 is used to solve the problem for number of disks = 3.

package com.algorithm.recurrsion;

public class TowerOfHanoi {
 public static class Tower {
  int tower[];
  int numDisks;
  int top = -1;
  String name;

  public Tower(int numDisks, String name) {
   this.numDisks = numDisks;
   tower = new int[numDisks];
   this.name = name;
  }

  public void addDisk(int disk) {
   System.out.println("adding   "+disk+" on tower   : "+name);
   tower[++top] = disk;
  }

  public int removeDiskOnTop() {
   int diskOnTop = tower[top];
   System.out.println("removing "+diskOnTop+" from tower : "+name);
   top--;
   return diskOnTop;
  }

  public void print() {
   if (top == -1) {
    System.out.println(name + " Tower is empty");
   } else {
    System.out.print(name + " tower contains... ");
    for (int i = 0; i <= top; i++) {
     System.out.print(tower[i] + " ");
    }
    System.out.println();
   }
  }
 }

 Tower source;
 Tower middle;
 Tower destination;

 int numDisks;

 public TowerOfHanoi(int numDisks) {
  this.numDisks = numDisks;
  source = new Tower(numDisks, "source");
  middle = new Tower(numDisks, "middle");
  destination = new Tower(numDisks, "destination");
  putDisksInInitialTower();
 }

 public void putDisksInInitialTower() {
  for (int i = 0; i < numDisks; i++) {
   source.addDisk((i + 1));
  }
 }

//The idea is if we need to solve tower of Hanoi for N then we can use the solution for N-1
public void solveTOHFor2(Tower source, Tower middle, Tower destination) {
   middle.addDisk(source.removeDiskOnTop());
   destination.addDisk(source.removeDiskOnTop());
   destination.addDisk(middle.removeDiskOnTop());
 }

 public void solveTOHFor3(Tower source, Tower middle, Tower destination) {
  solveTOHFor2(source, destination, middle);
  destination.addDisk(source.removeDiskOnTop());
  solveTOHFor2(middle, source, destination);
 }

 public void solveTOHFor4(Tower source, Tower middle, Tower destination) {
  solveTOHFor3(source, destination, middle);
  destination.addDisk(source.removeDiskOnTop());
  solveTOHFor3(middle, source, destination);
 }


 public void solveTOH(int n) {
  System.out.println("SOLVING TOWER OF HANOI!!");
  if(n == 1){
   // we will see later
  }
  else if(n == 2){
   solveTOHFor2(source, middle, destination);
  }
  else if(n == 3){
   solveTOHFor3(source, middle, destination);
  }
  else if(n == 4 ){
   solveTOHFor4(source, middle, destination);
  }else{
  // a general approach for solving number of disks = n we will see later
  }
 }
 public void printDisksOnTower() {
  source.print();
  middle.print();
  destination.print();
 }

 public static void main(String[] args) {
  int numOfDisks = 2;
  TowerOfHanoi toh = new TowerOfHanoi(numOfDisks);
  toh.printDisksOnTower();
  toh.solveTOH(numOfDisks);
  toh.printDisksOnTower();
 }
}

Now lets introduce a method to solve if the number of Disks is 1

public void solveTOHFor1(Tower source, Tower middle, Tower destination) {
  destination.addDisk(source.removeDiskOnTop());
}

Now applying the idea to reuse the solution for n-1 number of disks to solve the problem 

for n disks we can modify the solveTOHFor2() method as below

public void solveTOHFor2(Tower source, Tower middle, Tower destination) {
  solveTOHFor1(source, destination, middle);
  destination.addDisk(source.removeDiskOnTop());
  middle.addDisk(destination.removeDiskOnTop());
}

And Finally we are now in a position to write a recursive method to write a general method for Tower of Hanoi for N disks.

package com.algorithm.recurrsion;

public class TowerOfHanoi {
 public static class Tower {
  int tower[];
  int numDisks;
  int top = -1;
  String name;

  public Tower(int numDisks, String name) {
   this.numDisks = numDisks;
   tower = new int[numDisks];
   this.name = name;
  }

  public void addDisk(int disk) {
   System.out.println("adding   " + disk + " on tower   : " + name);
   tower[++top] = disk;
  }

  public int removeDiskOnTop() {
   int diskOnTop = tower[top];
   System.out.println("removing " + diskOnTop + " from tower : " + name);
   top--;
   return diskOnTop;
  }

  public void print() {
   if (top == -1) {
    System.out.println(name + " Tower is empty");
   } else {
    System.out.print(name + " tower contains... ");
    for (int i = 0; i <= top; i++) {
     System.out.print(tower[i] + " ");
    }
    System.out.println();
   }
  }
 }

 Tower source;
 Tower middle;
 Tower destination;

 int numDisks;

 public TowerOfHanoi(int numDisks) {
  this.numDisks = numDisks;
  source = new Tower(numDisks, "source");
  middle = new Tower(numDisks, "middle");
  destination = new Tower(numDisks, "destination");
  putDisksInInitialTower();
 }

 public void putDisksInInitialTower() {
  for (int i = 0; i < numDisks; i++) {
   source.addDisk((i + 1));
  }
 }

 private void solveTOH(int n, Tower source, Tower middle, Tower destination) {
  if (n >= 1) {
   solveTOH(n - 1, source, destination, middle);
   destination.addDisk(source.removeDiskOnTop());
   solveTOH(n - 1, middle, source, destination);
  }
 }

 public void solveTOH() {
  System.out.println("Solving the tower of Hanoi ...");
  solveTOH(numDisks, source, middle, destination);
 }

 public void printDisksOnTower() {
  source.print();
  middle.print();
  destination.print();
 }

 public static void main(String[] args) {
  int numOfDisks = 6;
  TowerOfHanoi toh = new TowerOfHanoi(numOfDisks);
  toh.printDisksOnTower();
  toh.solveTOH();
  toh.printDisksOnTower();
 }
}

Huffman coding Algorithm

Hello friends,

I am here with yet another algorithm question.

Suppose we have an input of characters. We want to encode the characters using Huffman Coding, so that we assign least number of bits to the character having the maximum occurrence in the input.

Please find the code below...

public class HuffmanCode {

static public class HashSet {
static public class EntrySet {
public char key;
public String code;
public int frequency = 1;
public EntrySet next;

public EntrySet(char key, EntrySet next) {
this.key = key;
this.next = next;
}

public static int getHashCodeForChar(char c) {
int result = 1;
result = 31 * c;
return result;

}

@Override
public int hashCode() {
return getHashCodeForChar(key);
}
}

public static class KeyNode {
KeyNode next;
char key;

public KeyNode(char key, KeyNode next) {
this.key = key;
this.next = next;
}
}

KeyNode keyList;
int keyCounter;
private int maxSize = 97;
private int size = 0;
private EntrySet[] set = new EntrySet[maxSize];

public boolean add(char data) {
EntrySet node = new EntrySet(data, null);
int index = calculateIndex(EntrySet.getHashCodeForChar(data));
EntrySet temp = set[index];
while (temp != null) {
if (data == temp.key) {
temp.frequency++;
return false;
}
temp = temp.next;
}
keyList = new KeyNode(data, keyList);
keyCounter++;
node.next = set[index];
set[index] = node;
size++;
return true;
}

public int calculateIndex(int hash) {
int index = hashCode() % maxSize;
return index;
}

public int getFrequency(char key) {
int hashcode = EntrySet.getHashCodeForChar(key);
int index = calculateIndex(hashcode);
if (set[index] == null) {
return 0;
} else {
EntrySet node = set[index];
while (node != null) {
if (key == node.key) {
return node.frequency;
}
node = node.next;
}
return 0;
}
}

public EntrySet getEntrySet(char key){
int hashcode = EntrySet.getHashCodeForChar(key);
int index = calculateIndex(hashcode);
if (set[index] == null) {
return null;
} else {
EntrySet node = set[index];
while (node != null) {
if (key == node.key) {
return node;
}
node = node.next;
}
return null;
}
}

public char[] getKeys() {
KeyNode temp = keyList;
char[] retValue = new char[keyCounter];
int retCount = 0;
while (temp != null) {
retValue[retCount++] = temp.key;
temp = temp.next;
}
return retValue;
}
}

public static void main(String[] args) {
char inputChars[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'a', 'a', 'a', 'b', 'a',
'b', 'a', 'z', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
'a', 'a', 'a' };
HashSet set = new HashSet();
for (char c : inputChars) {
set.add(c);
}
char keys[] = set.getKeys();
int n = keys.length;
PQ pq = new PQ(n);
for (char c : keys) {
pq.add(c, set.getFrequency(c));
}
while (pq.size > 1) {
HuffmanNode left = pq.remove();
HuffmanNode right = pq.remove();
HuffmanNode parent = new HuffmanNode(left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.add(parent);
}
HuffmanNode top = pq.remove();
StringBuilder code = new StringBuilder();
while(!top.isProcessed){
HuffmanNode temp = top;
code.replace(0, code.length(), ""); // reset
// now traverse till one of the leaf or a node with left and right both processed
while(true){
if(temp.left == null && temp.right == null){
// leaf node
temp.isProcessed = true;
set.getEntrySet(temp.c).code = code.toString();
break;
}
else if(!temp.left.isProcessed){
code.append(0);
temp = temp.left;
}
else if(!temp.right.isProcessed){
code.append(1);
temp = temp.right;
}
else{
// both processed
temp.isProcessed = true;
break;
}
}

}
for (char key : keys) {
System.out.println(key+" has code "+set.getEntrySet(key).code+" freq "+set.getEntrySet(key).frequency);
}
}

static class HuffmanNode {
HuffmanNode left;
HuffmanNode right;
char c;
int freq;
boolean isProcessed = false;

public HuffmanNode(char c, int freq) {
this.freq = freq;
this.c = c;
}

public HuffmanNode(int freq) {
this.freq = freq;
}
}

static public class PQ {
int maxSize;
int size = 0;;
HuffmanNode[] nodes;

public PQ(int maxSize) {
this.maxSize = maxSize;
nodes = new HuffmanNode[maxSize];
}

public void add(char c, int freq) {
HuffmanNode node = new HuffmanNode(c, freq);
nodes[size++] = node;
addNHeapify();
}

public void add(HuffmanNode node) {
nodes[size++] = node;
addNHeapify();
}

public void addNHeapify() {
int currentIndex = size - 1;
int currentData = nodes[currentIndex].freq;
int parentIndex = currentIndex / 2;
int parentData = nodes[parentIndex].freq;
while (currentData < parentData) {
swap(currentIndex, parentIndex);
currentIndex = parentIndex;
currentData = nodes[currentIndex].freq;
parentIndex = currentIndex / 2;
parentData = nodes[parentIndex].freq;
}
}

public HuffmanNode remove() {
HuffmanNode node = nodes[0];
swap(0, size - 1);
nodes[size - 1] = null;
size--;
if(size != 0){
removeNHeapify();
}
return node;
}

public void removeNHeapify() {
int currentIndex = 0;
int currentData = nodes[currentIndex].freq;
int childIndex;
int childData;
if (2 * currentIndex + 1 > size - 1) {
return;
}
if (2 * currentIndex + 2 < size) {
if (nodes[2 * currentIndex + 1].freq < nodes[2 * currentIndex + 2].freq) {
childIndex = 2 * currentIndex + 1;
} else {
childIndex = 2 * currentIndex + 2;
}
} else {
childIndex = 2 * currentIndex + 1;
}
childData = nodes[childIndex].freq;
while (currentData > childData) {
swap(childIndex, currentIndex);
currentIndex = childIndex;
currentData = nodes[currentIndex].freq;
if (2 * currentIndex + 1 > size - 1) {
return;
}
if (2 * currentIndex + 2 < size) {
if (nodes[2 * currentIndex + 1].freq < nodes[2 * currentIndex + 2].freq) {
childIndex = 2 * currentIndex + 1;
} else {
childIndex = 2 * currentIndex + 2;
}
} else {
childIndex = 2 * currentIndex + 1;
}
}
}

public void swap(int index1, int index2) {
HuffmanNode temp = nodes[index1];
nodes[index1] = nodes[index2];
nodes[index2] = temp;
}
}
}