KMP string search

KMP (Knuth Morris Pratt) Pattern Searching
The naive pattern search doesn’t work well in cases where we see many matching characters followed by a mismatching character.
The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to O(n). The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of next window. We take advantage of this information to avoid matching the characters that we know will anyway match.
Link to code.

Count number of ones in binary of a number

#include <iostream>
using namespace std;
//count no of ones in binary representation
int count1(int n)
{
    int c=0;
    while(n)
    {
        n=n&(n-1);
        cout<<n;
        c++;
    }
    return c;
}
int main(){
 cout<<count1(6);
 return 0;
}

Finding all prime factors in minimum time complexity

//find all prime factors
#include <iostream>
#include<math.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    cout<<n<<endl;
    int count=0;
    for(int i=2;i<=n;i++)
    {
        count =0;
        while(n%i==0){
            n/=i;
            count++;
        }
        if(count)
            cout<<i<<"<<"<<count<<endl;
    }
    
 return 0;
}

Reversing Link List in group of n nodes without using any other data type in O(n) time

Some ways of reversing a link list using other data types are-
1.Use the stack. We can push all the elements on to the stack and then poop out each element. 
2.Similarly, we can also create a new link list. Starting from the head of the current list, we can create  new list by adding nodes in the front of the new list.

A link list can be reversed without using any other data type by using three pointers as shown in the code below.

//created by Aditya Vijayvergia

//uploaded on thecodingedge.blogspot.com

#include<stdio.h>

#include<conio.h>

struct node

{

  int data;

  struct node* next;

}*head;

typedef struct node node;

node* rev(int n)

{

  node *p,*q,*r,*t2,*t1;

  int c=0,start=1;

  t2=head;

  t1=NULL;

  p=head;

  q=head->next;

  r=q->next;

  while(q!=NULL)

  {

    //printf("c<n-1\n\t%d",p->data);

    //getch();

    if(c==n-1)

    {

      //printf("c=n-1");

      //getch();

      c=0;

      if(t1!=NULL)

    t1->next=p;

      t1=t2;

      t2=q;

      if(start==1)

      {

    start=0;

    head=p;

      }

      p=q;

      q=p->next;

      r=q->next;

    }

    q->next=p;

    p=q;

    q=r;

    r=r->next;

    c++;

  }

  t1->next=p;

  t2->next=NULL;

  return head;

}

void main()

{

  node *q;

  node* p;

  int i;

  clrscr();

  head=(node*)malloc(sizeof(node));

  p=head;

  //q->next=NULL;

  head->data=1;

  //p->next=NULL;

  for(i=2;i<15;i++)

  {

    q=(node*)malloc(sizeof(node));

    q->next=NULL;

    q->data=i;

    p->next=q;

    p=p->next;

  }

  p=head;

  printf("Initial link list is:\n");

  while(p!=NULL)

  {

    printf("%d->",p->data);

    p=p->next;

  }

  printf("\n\n\n\nUsing n=3\n");

  head=rev(6);

  p=head;

  printf("\n\n\nReversed link list is:\n");

  while(p!=NULL)

  {

    printf("%d->",p->data);

    p=p->next;

  }

  getch();

}

The output of the program is given below.

Converting Postfix Expression to Prefix Expression and Infix Expression in C

In prefix expression, the operator comes before the operands where as in postfix expression, the operator comes in the end. So to convert a postix expression to a prefix expression, we just have to 

bring the operator in the front for each sub expression.

For doing this we use a stack that stores a 2D character array. We can visualize it like a 1D character array that stores operands. The push operation pushes an operand to the stack and the pop operation returns a pointer to the last operand.

First push the operands on to the stack until an operator is encountered. When an operator is encountered we pop the last two operands and create a new character array.

 Now if we want to convert to infix expression then we store the first operand then the operator and then the second operand. Similarly for prefix expression we first store the operator and then the two operands in order.We then push this newly created character array to the stack.

The logic is that the character array that we pushed will now act as an operand for further operations.

The source code for prefix expression is given below.

//created by Aditya Vijayvergia
//uploaded on thecodingedge.blogspot.com
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define size 20
struct stack
{
  char data[size][size];
  int top;
}s;
void push(char x[20])
{
  int i;
  s.top++;
  for(i=0;i<strlen(x);i++)
   s.data[s.top][i]=x[i];
}
char* pop()
{
char *p;
if(s.top==-1)
  return NULL;
return s.data[s.top--];
}

void main()
{
  char q[50],c[50];
  char *a,*b;
  int i,j,a1,b1;
  s.top=-1;
  clrscr();
  printf("\nenter postfix expression:");
  gets(q);
  for(j=0;j<strlen(q);j++)
  {
  if(q[j]>='a'&&q[j]<='z')
    {
    s.data[++s.top][0]=q[j];
    //printf("\npush %c",q[j]);
    }
  else
  {
  b=pop();
  a=pop();
  //printf("\na=%s\tb=%s",a,b);
  c[0]=q[j];
  a1=strlen(a);
  b1=strlen(b);
  for(i=0;i<a1;i++)
    {
    c[i+1]=*a;
    a++;
    }
  for(i=0;i<b1;i++)
    {
    c[a1+i+1]=*b;
    b++;
    }
  push(c);
  //printf("\npushed operand %s",c);
  }
  a=NULL;
  b=NULL;
  }
  printf("\n\nPrefix expression : %s",pop());
  getch();
}

The Snake Game in C++

It is similar to the game which was very common in mobiles few years back. The snake eats food items to increase its length and tries to avoid obstacles in order to win the game. The game has 3 modes- easy, normal and hard. Hard mode has the maximum number of obstacles. The obstacles and food items are generated at random so every time the game is different from the last time. 

The source code is given below-

#include<iostream.h>
#include<conio.h>
#include<process.h>
#include<time.h>
#include<stdlib.h>
//created by Aditya Vijayvergia 
//uploaded at thecodingedge.blogspot.com
int snake[40][2],point[20][2],dead[200][2],nd,len,n=20,m=39,pos[2];
void create()
{
   int i;
   len=5;
   srand(time(NULL));
   for(i=0;i<len;i++)
       {
  snake[i][1]=i;
       }
   for(i=0;i<20;i++)
      {
  point[i][0]=rand() %20;
  point[i][1]=rand() %40;
      }
   srand(time(NULL));
   for(i=0;i<nd;i++)
      {
  dead[i][0]=rand() %20;
  dead[i][1]=rand() %40;
      }
}

int found(int x,int y)
{
for(int i=0;i<len;i++)
   if(snake[len-1][0]==x&&snake[len-1][1]==y)
     return 2;

   else if(snake[i][0]==x&&snake[i][1]==y)
     return 1;
return 0;
}

int ifdead(int x,int y)
{

   for(int j=0;j<nd;j++)
   if(dead[j][0]==x&&dead[j][1]==y)
       return 1;
   return 0;
}
int ifpoint(int x,int y)
{
   for(int i=0;i<20;i++)
   {
   if(point[i][0]==x&&point[i][1]==y)
      return 1;
   }
   return 0;
}

void show()
{
   //cout<<"show running";
   clrscr();
   cout<<"\n";
   for(int k=0;k<m+1;k++)
   cout<<"__";
   cout<<"\n";
   for(int i=0;i<n;i++)
   {
   cout<<"|";
   for(int j=0;j<m;j++)
   {
       if(found(i,j)==2)
       cout<<" m";
       else if(found(i,j)==1)
       cout<<" o";
       else if(ifpoint(i,j))
       cout<<" *";
       else
       if(ifdead(i,j))
       cout<<" X";
       else
       cout<<"  ";
   }
   cout<<"|";
   }
   for(k=0;k<m+1;k++)
   cout<<"__";
}

void changepoint(int x,int y)
{
   for(int i=0;i<20;i++)
   if(point[i][0]==x&&point[i][1]==y)
   {
       point[i][0]=-1;
       point[i][1]=-1;
   }
}


void move(int x,int y)
{
    x=(x+n)%n;
    y=(y+m)%m;
    if(ifpoint(x,y))
    {
  pos[0]=x;
  pos[1]=y;
  changepoint(x,y);

    }
    else
    if(ifdead(x,y))
    {
      clrscr();
      cout<<"\n\n\n\t\tGAME OVER\n\n\t\tScore:"<<len-5;

      getch();
      exit(0);
    }
    for(int i=0;i<len-1;i++)
    for(int j=0;j<2;j++)
       snake[i][j]=snake[i+1][j];
    snake[i][0]=x;
    snake[i][1]=y;
    //}
    show();

    if(snake[len-1][0]==pos[0]&&snake[len-1][1]==pos[1])
    {
 len++;
  if(len-5==20)
  {
     clrscr();
     cout<<"\n\n\n\t\tVICTORY";
     exit(0);
  }
 for(i=len-1;i>0;i--)
 for(j=0;j<2;j++)
     snake[i][j]=snake[i-1][j];
 snake[0][0]=pos[0];
 snake[0][1]=pos[1];
 pos[0]=-1;
 pos[1]=-1;
    }
}

void menu()
{
   int choice;
   cout<<"\n\n\tSANKE GAME";
   cout<<"\n\n\n1.easy\n2.normal\n3.hard";
   cin>>choice;
   switch(choice)
   {

   case 1:nd=50;
   break;
   case 2:nd=125;
   break;
   case 3:nd=200;
   break;
   }
}

void main()
{
    clrscr();
    menu();
    create();
    show();
    pos[0]=-1;
    pos[1]=-1;
    char m;
    while(1)
    {
    cout<<"\n\t\t";
    cout<<"enter choice:";
    cin>>m;
    switch(m)
    {
    case 'd':move(snake[len-1][0],snake[len-1][1]+1);
      break;
    case 'w':move(snake[len-1][0]-1,snake[len-1][1]);
      break;
    case 's':move(snake[len-1][0]+1,snake[len-1][1]);
      break;
    case 'a':move(snake[len-1][0],snake[len-1][1]-1);
      break;
    case 'p':exit(0);
    }
    }
}

Sample output is given below.

Generating permutations in Java using array

The following code generates all possible permutations till the entered integer integers. Similar program can be made to permute the characters of a string.

Explanation:
First we enter only 1 in a array.
Then for entering 2 we have two choices- before 1 and after 1 as- "21" and "12".
The program uses recursion so for "21" we can add 3 at 3 different places as "321", "231" and "213" i.e., at first position, between them and in the last position.

The code is given below: 

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author Aditya Vijayvergia @ thecodingedge.blogspot.com
 */
public class GeneratingPermutations {

    static int perm(int []a,int n,int m)
    {                          //n=the element that is being added in this recursive call
        int []b=new int[m];    //m=total no of elemets
        for(int i=0;i<n;i++)
            {
                System.arraycopy(a, 0, b, 0, m);//copy the state of array a to array b
                for(int j=n-1;j>i;j--)//shift values 1 step ahead
                    b[j]=b[j-1];
                b[i]=n;//store n at the empty location
                if(n==m)
                {
                    System.out.println(Arrays.toString(b));
                }
                else{    
                    perm(b,n+1,m);   
                    }
            }
        return 0;
    }
    
    public static void main(String[] args) {
        int m;
        System.out.print("enter the number of elements:");
        Scanner in=new Scanner(System.in);
        m=in.nextInt();
        int []a=new int[m];
        perm(a,1,m);
    }
}

Sample Output:

Maze Solving Algorithm

This maze solving algorithm works on the principle of Backtracking. It is implemented in Java.

The main idea is to solve the problem is move from the starting point in all the possible directions until we reach the goal. While moving in a particular direction, when ever the path splits(i.e., a node is encountered) one of the path is chosen. We move on the same path until we encounter a dead end(or a leaf). When a leaf is reached, we backtrack to the last encountered node and chose another path. This procedure is followed recursively until either we reach the goal or we reach the first encountered node again by backtracking from all possible ways and hence no solution to the maze exists. When we have reached our goal, we can mark the path used.

The code is explained with comments. Further for better understanding, i have used some print statements as comments. The code can be tested on other maze problem too by simply changing the maze array used in the code.

Open link to go to View Source Code.
Click here to download class file.

The output of the code is given under:

   

Tic-Tac-Toe Application in Java using Applet

The application runs with all the rules and it also checks which player (Blue or Red) wins. Moreover it keeps a record of the number of games won by the players. After each game the result is shown and the next game starts automatically with the score of all the previous games. In addition to the the buttons, the application also maintains an 3x3 array in order to check if a game is won or  drawn.


View Source Code
Download class file

Some of the screen shots of the application are given below.

Typing Speed Calculator Application in Java using Applet

This application calculates your typing speed. A text is shown and the amount of text you can copy in 1 minute determines your typing speed.

This application is unique as instead of using the traditional methods of using threads in applets, I have used the concept of inner classes. There are two inner classes in the main class. One class called SetFrame class extends from Frame class and the other class called Timer class extends from thread class. As the name suggests, SetFrame class creates the applet and the Timer class displays the time left.   

View Source Code
Download class file

Some screen shots of the application are given below.