Tower of Hanoi

(Source: http://en.wikipedia.org/wiki/Tower_of_Hanoi)

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower,^[1] and sometimes pluralised) is a mathematical game orpuzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

• Only one disk may be moved at a time.
• Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
• No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves

namespace TowerOfHanoi
{
    class Disk: IComparable<Disk>
    {
        public int Size { get; private set; }

        public Disk(int size)
        {
            this.Size = size;
        }

        public int CompareTo(Disk other)
        {
            return this.Size - other.Size;
        }
    }
}

namespace TowerOfHanoi
{
    class Tower
    {
        private Disk[] Peck;
        private int Pointer= -1;
        public int Height { get; private set; }
        public string name { get; private set; }

        public Tower(int Height, string name)
        {
            Peck = new Disk[Height];
            this.Height = Height;
            this.name = name;

        }

        public void Push(Disk d)
        {
            if (!this.isEmpty())
            {
                if (Peck[Pointer].CompareTo(d) > 0)
                {
                    Peck[++Pointer] = d;
                }
                else
                {
                    throw new NotSupportedException("Can't put large disk on small disk");
                }
            }
            else
            {
                Peck[++Pointer] = d;
            }
        }

        public Disk Pop()
        {
            if (!isEmpty())
            {
                return Peck[Pointer--];
            }
            else
            {
                throw new NotSupportedException("Peck is empty");
            }
        }

        public bool isEmpty()
        {
            return Pointer == -1 ? true : false;
        }

        public override string ToString()
        {
            string final = name + "\n";
            for (int i = Pointer; i >= 0; i--)
            {
                string s = "";
                int space = (Peck.Length- Peck[i].Size);

                for (int x = 0; x < space; x++)
                {
                    s += "  ";
                }

                for (int x = 1; x <= Peck[i].Size; x++)
                {
                    s+="____";
                }

                final += s;
                final += "\n";
            }

            return final;
        }
    }
}

namespace TowerOfHanoi
{
    class TowerOfHanoiSolver
    {
        public void Solve(Tower from, Tower to)
        {
            Tower temp = new Tower(from.Height, "TEMP");
            this.Solve(from, to, temp, from.Height);
        }

        private void Solve(Tower from, Tower to, Tower temp, int height)
        {
            if (height == 1)
            {
                to.Push(from.Pop());
            }
            else
            {
                Solve(from, temp, to, height - 1);
                to.Push(from.Pop());
                Solve(temp, to, from, height - 1);
            }
        }
    }
}

namespace TowerOfHanoi
{
    class Program
    {
        static void Main(string[] args)
        {
            Tower from = new Tower(4, "FROM");
            Tower to = new Tower(4 , "TO");


            TowerOfHanoiSolver solver = new TowerOfHanoiSolver();

            from.Push(new Disk(4));
            from.Push(new Disk(3));
            from.Push(new Disk(2));
            from.Push(new Disk(1));

            Console.WriteLine(from.ToString());
            Console.WriteLine("SOLVING..");
            solver.Solve(from, to);
            Console.WriteLine(to.ToString());
            Console.ReadLine();
        }
    }
}

Quick Sort

Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)

(Source: http://en.wikipedia.org/wiki/Quicksort )

Tip: Randomly shuffle the array before sort to reduce the probability of the Worst case.

class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        public int[] QuickSort(int[] input)
        {
            this.QuickSort(input, 0, input.Length - 1);
            return input;
        }

        private void QuickSort(int[] input, int low, int high)
        {
            if (low < high)
            {
                int j = Partition(input, low, high);
                QuickSort(input, low, j - 1);
                QuickSort(input, j + 1, high);
            }
        }

        private int Partition(int[] input, int low, int high)
        {
            int i=low+1;
            int j = high;
            // out of the loop if low value is come to the partition point

            while (true)
            {
                while (input[i] < input[low])
                {
                    i++;
                    if (i >= high)
                    {
                        break;
                    }
                }

                while (input[j] > input[low])
                {
                    j--;
                    if (j <= low)
                    {
                        break;
                    }
                }

                if (i >= j)
                {
                    Swap(input, j, low);

                    break;
                }
                else
                {
                    Swap(input, i, j);
                }
            }

            return j;
        }



        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Quick = new int[arraySize];
         

            for (int x = 0; x < Quick.Length; x++)
            {
                Quick[x] = x;
            }

            for (int x = 0; x < Quick.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Quick[random];
                Quick[random] = Quick[x];
                Quick[x] = temp;
           
            }

            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.QuickSort(Quick);
            StopWtch.Stop();
            Console.WriteLine("QUICKSORT:   " + StopWtch.Elapsed.TotalSeconds + "sec");

            Console.ReadLine();
        }
    }

Recursive Merge Sort

class Program
    {
        private void Swap(int[] input, int x, int y)
        {
            var temp = input[x];
            input[x] = input[y];
            input[y] = temp;
        }

        public int[] MergeSort(int[] input)
        {
            int[] temp = new int[input.Length];
            this.RecursiveMergeSort(input, temp, 0, (input.Length - 1) / 2, input.Length - 1);

            return input;
        }

        private void RecursiveMergeSort(int[] input, int[]temp, int low,int mid, int high)
        {
            if (low < high)
            {
                RecursiveMergeSort(input,temp,low, (low + mid) / 2, mid);
                RecursiveMergeSort(input, temp,mid + 1, (mid + 1 + high) / 2, high);
                Merge(input, temp, low, mid, high);

            }
        }

        private void Merge(int[] input, int[] temp, int low, int mid, int high)
        {
            for (int i = low; i <= high; i++)
            {
                temp[i] = input[i];
            }

            int l = low;
            int h = mid + 1 ;
            for (int i = low; i <= high; i++)
            {
                if (h > high)
                {
                    input[i] = temp[l++];
                }
                else if (l > mid)
                {
                    input[i] = temp[h++];
                }
                else
                {
                    if (temp[l] <= temp[h])
                    {
                        input[i] = temp[l++];

                    }
                    else
                    {
                        input[i] = temp[h++];
                    }
                }
            }

        }

       
   
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int arraySize = 10000000;
            int[] Merge= new int[arraySize];
           

            for (int x = 0; x < Quick.Length; x++)
            {
                Merge[x] = x;
            }

            for (int x = 0; x < Quick.Length; x++)
            {
                int random = r.Next(0, x);
                var temp = Merge[random];
                Merge[random] = Merge[x];
                Merge[x] = temp;
            }


            var p = new Program();
            var StopWtch = new System.Diagnostics.Stopwatch();

            StopWtch.Reset();
            StopWtch.Start();
            p.MergeSort(Merge);
            StopWtch.Stop();
            Console.WriteLine("MERGESORT:   " + StopWtch.Elapsed.TotalSeconds + "sec");
            Console.ReadLine();
        }
    }

Maze Traversal

A common problem in AI(Artificial Intelligent) is solving a Maze. There are number of algorithms to solve different type of mazes and number of Algorithms to create a random maze of a particular type.

there are number of types of mazes. They are classified according to Dimension, Hyper dimension, Topology, Tessellation, Routing, Texture, and Focus. Each have its own properties.

For more Details on Algorithms to Solve Maze go Here
for types of Mazes and maze generation and solution algorithms click here

Below I generate a random maze with Recursive backtracking and Solve it almost same algorithm call wall follower.
The basic idea of the solution is You just place your Right hand on the right side wall and just go until find the exit point. This will eventually guide you to the exit point. this method will suitable for any type of 2D Mazes but it is a little bit slow compared to other methods.

#################################################


#include <stdio.h>
#include <stdlib.h>
#include   <time.h>

#define WALL 1
#define BORDER 2
#define PATH 3

#define TEMPSOL 4
#define SOL 5

#define START 0
#define END 6

#define SIZE 30

void printMaze(int floor[][SIZE]);
void generateMaze(int floor[][SIZE],int start[]);
void solveMaze(int floor[][SIZE],int start[]);

int main(int argc, char** argv) {

    int floor[SIZE][SIZE];

    int start[2]={1,1};
    generateMaze(floor,start);
    printMaze(floor);
   
    solveMaze(floor,start);
    printMaze(floor);

    return (EXIT_SUCCESS);
}


void printMaze(int floor[][SIZE]){
    printf("\n");
    int i;
    int j;
    for(j=SIZE-1;j>=0;j--){
        for(i=0;i<SIZE;i++){
            switch(floor[i][j]){
                case BORDER:
                    printf("##");
                    break;
                case WALL:
                    printf("WW");
                    break;
                case PATH:
                    printf("  ");
                    break;
                case START:
                case TEMPSOL:
                    printf("ST");
                    break;
                case END:
                    printf("EX");
                    break;
                case SOL:
                    printf("* ");
                    break;
            }
        }
        printf("\n");
    }
}

void solveMaze(int floor[][SIZE], int start[]){
    int recursiveSolve(int floor[][SIZE],int position[]);
    recursiveSolve(floor,start);
    floor[start[0]][start[1]]=START;

}

void generateMaze(int floor[][SIZE],int startPosition[]){
    void recursiveBackTrack(int floor[][SIZE],int position[]);

    //initialize Maze Arena
    int i;
    int j;
    for(i=0;i<SIZE;i++){
        for(j=0;j<SIZE;j++){
            floor[i][j]=BORDER;
        }
    }
    for(i=1;i<SIZE-1;i++){
        for(j=1;j<SIZE-1;j++){
            floor[i][j]=WALL;
        }
    }

    //set the StartPosition
    srand(time(NULL));
    recursiveBackTrack(floor,startPosition);
    floor[startPosition[0]][startPosition[1]]=START;
    //set the EndPosition
    int endPosition[2]={SIZE-2,SIZE-2};
    floor[endPosition[0]][endPosition[1]]=END;
}

int  recursiveSolve(int floor[][SIZE],int currentPosition[]){
    int neighbour[4][3]={{floor[currentPosition[0]+1][currentPosition[1]],currentPosition[0]+1,currentPosition[1]},       //right
                             {floor[currentPosition[0]][currentPosition[1]+1],currentPosition[0],currentPosition[1]+1},       //up
                             {floor[currentPosition[0]-1][currentPosition[1]],currentPosition[0]-1,currentPosition[1]},       //left
                             {floor[currentPosition[0]][currentPosition[1]-1],currentPosition[0],currentPosition[1]-1}};      //down
   
    int i;
    if(floor[currentPosition[0]][currentPosition[1]]==END){
        return 1;
    }else{
        for(i=0;i<4;i++){
            if(neighbour[i][0]==PATH||neighbour[i][0]==END){
                 int t[2]={neighbour[i][1],neighbour[i][2]};
                floor[currentPosition[0]][currentPosition[1]]=TEMPSOL;
                if(recursiveSolve(floor,t)==1){
                    floor[currentPosition[0]][currentPosition[1]]=SOL;
                    return 1;
                }
            }
        }
        floor[currentPosition[0]][currentPosition[1]]=PATH;
        return 0;
    }

}

void recursiveBackTrack(int floor[][SIZE],int currentPosition[]){
    int checkPositions(int floor[][SIZE],int position[],int comingFrom);
    floor[currentPosition[0]][currentPosition[1]]=PATH;

   
    int eachDirection[4][2]={{currentPosition[0]+1,currentPosition[1]},       //right
                             {currentPosition[0],currentPosition[1]+1},       //up
                             {currentPosition[0],currentPosition[1]-1},      //down
                             {currentPosition[0]-1,currentPosition[1]}};       //left
                            

   
    int directions[4]={0,1,2,3};
    int i;
   
    for(i=4;i>0;i--){
        int randomDirection=rand()%i;
        int tempDirection=directions[randomDirection];
        directions[randomDirection]=directions[i-1];
        if(checkPositions(floor,eachDirection[tempDirection],(3-tempDirection))==1){
            recursiveBackTrack(floor,eachDirection[tempDirection]);
        }
    }

}

int checkPositions(int floor[][SIZE],int position[],int comingFrom){
    int eachDirection[4][2]={{position[0]+1,position[1]},       //right
                             {position[0],position[1]+1},       //up
                             {position[0],position[1]-1},      //down
                             {position[0]-1,position[1]}};       //left
   
    if(floor[position[0]][position[1]]==WALL){                     //check weather the cell is unused
        int i;
        for(i=0;i<4;i++){
            if(i!=comingFrom && floor[eachDirection[i][0]][eachDirection[i][1]]==PATH){      //skip the previous cell &&
                    return 0;
            }
        }     
        return 1;
    }else{
        return 0;
    }
}

Find Palindrome

A palindrome is a word, phrase number or other sequence of units that can be read the same way in either direction
Eg:
Was it a rat I saw.     A nut for a jar of tuna.     Doc note I dissent A fast never prevents a fatness I diet on cod.    A man a plan, a canal Panama
here i try a recursive solution to find weather a sentence is a palindrome.
my solution is case sensitive and exclude spaces.
########################################################################
#include <stdio.h>
#include <stdlib.h>

int testPalindrome(char data[],int start,int end);
int main(int argc, char** argv) {
char string[]="a man a plan a canal panama";
//was it a rat I saw
//a nut for a jar of tuna
//dammit I m mad
//doc note i dissent a fast never prevents a fatness I diet on cod
int size=0;
char c;
while(c!=''){
c=string[size];
printf("%c",c);
size++;
}
printf("\n\n");
if(testPalindrome(string,0,size-2)==1){
printf("this is a Palindrome\n");
}else{
printf("this is not a Palindrome\n");
}
return (EXIT_SUCCESS);
}
int testPalindrome(char data[],int start,int end){
int i=1;
if(start>=end){
return 1;
}else if(data[start]==' '){
start++;
i=testPalindrome(data,start,end);
}else if(data[end]==' '){
end--;
i=testPalindrome(data,start,end);
}else if(data[start]==data[end]){
i=testPalindrome(data,(start+1),(end-1));
}else{
return 0;
}
return i;
}

Knight's Tour

One of the more interesting puzzlers for chess buffs is the Knight's Tour Problem, originally proposed by mathematician Euler. The question is this: Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once?

Knight's tour

You can learn some algorithms to solve the problem here
Here I include the source code for a small Game using number keys(1,2,3,4,5,6,7,8) to move knights to eight positions around it.
1 :   Up 2  and Right 1
2:    Up 2 and  Left   1
3:   Left 2 and  Up   1
and so on..
8 : hint
In the hint i used "Warnsdorff's algorithm" to solve the problem. according to the algorithm you have to move knight to a legal square with minimum value specified in the table.
##############################################################################
#include <stdio.h>
void placeKnight(int position[],int board[][8][3]);
int moveKinght(int moveTo,int currentPosition[],int board[][8][3]);
void printBoard(int board[][8][3],int selection);
void heuristic(int board[][8][3]);
int isLegal(int moveTo,int currentPosition[],int board[][8][3]);
int main(){
int board[8][8][3]={0};
int currentPosition[2]={0,0};
heuristic(board);
placeKnight(currentPosition,board);
printBoard(board,0);
int input=0;
while(input>=0){
scanf("%d",&input);
if(input>=0&&input<8){
moveKnight(input,currentPosition,board);
heuristic(board);
printBoard(board,1);
}else if(input==8){
int selection=0;
printf("enter the selection :\n 0---> find legal moves\n 1---> find path you traveled\n 2--> hint\n");
scanf("%d",&selection);
if(selection>=0&&selection<=2){
printBoard(board,selection);
}else{
printf("invalied selection\n");
}
}
}
return 0;
}
void heuristic(int board[][8][3]){
int i;
int j;
int count=0;
int tempPosition[2];
for(i=0;i<8;i++){
for(j=0;j<8;j++){
tempPosition[0]=j;
tempPosition[1]=i;
int move;
for(move=0;move<8;move++){
count+=isLegal(move,tempPosition,board);
if(isLegal(move,tempPosition,board)==0){
//printf("%d , %d , moveto : %d\n",tempPosition[1],tempPosition[0],move);
}
}
board[i][j][2]=count;
count=0;
}
}
}
void printBoard(int board[][8][3],int selection){
int i;
int j;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
printf(" %2d",board[i][j][selection]);
}
printf("\n");
}
}
void placeKnight(int position[],int board[][8][3]){
int i;
int j;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
board[i][j][0]=0;
board[i][j][1]=0;
}
}
board[position[1]][position[0]][0]=1;
board[position[1]][position[0]][1]=1;
printf("The knight is initialized at ROW=%d   COLUMN=%d\n",position[1],position[0]);
}
int isLegal(int moveTo,int currentPosition[],int board[][8][3]){
int i;
int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
int vertical[8]={-1,-2,-2,-1,1,2,2,1};
int count=board[currentPosition[1]][currentPosition[0]][1];
if((currentPosition[0]+horizontal[moveTo])<8&&
(currentPosition[0]+horizontal[moveTo])>=0&&
(currentPosition[1]+vertical[moveTo])<8&&
(currentPosition[1]+vertical[moveTo])>=0&&
board[currentPosition[1]+vertical[moveTo]][currentPosition[0]+horizontal[moveTo]][0]==0){
return 1;
}
else {
return 0;
}
}
int moveKnight(int moveTo,int currentPosition[],int board[][8][3]){
int i;
int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
int vertical[8]={-1,-2,-2,-1,1,2,2,1};
int count=board[currentPosition[1]][currentPosition[0]][1];
if(isLegal(moveTo,currentPosition,board)){
currentPosition[0]+=horizontal[moveTo];
currentPosition[1]+=vertical[moveTo];
board[currentPosition[1]][currentPosition[0]][0]++;
board[currentPosition[1]][currentPosition[0]][1]=count+1;
}
else {
printf("the move is illegal\n");
}
}

Selection Sort

SELECTION SORT.  (Recursive)
1.Selection Sort search array and looking for the smallest element in the array and swap it with the first element.
2.Again Search balance array without using the first element. (recursive part)


######################################################################
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
void printArray(int data[]){
int i;
printf("\n\n");
for(i=0;i<SIZE;i++){
printf("%d \n",data[i]);
}
}
void selectionSort(int data[],int start);
int main(int argc, char** argv) {
int data[SIZE];
//fill the array with random data
srand(time(NULL));
int i;
for(i=0;i<SIZE;i++){
data[i]=rand()%(1000);
}
printf("before Sort");
printArray(data);
//sort Array
selectionSort(data,0);
printf("after Sort");
printArray(data);
return (EXIT_SUCCESS);
}
void selectionSort(int data[],int start){
int i;
int temp=start;
for(i=start;i<SIZE;i++){
if(data[temp]>data[i]){
temp=i;
}
}
int value=data[temp];
data[temp]=data[start];
data[start]=value;
//recursive
if(start<=SIZE){
selectionSort(data,(start+1));
}
}