Disjoint Set Data Structure

This post will illustrate the basic implementation of Disjoint-set data structure. We will use the two popular heuristics:
1. Union by rank
2. Path Compression

Refer this TopCoder tutorial for detailed explanation of this data structure.

To illustrate with example, we solve this problem on hackerrank.

The basic implementation using class is as follows:

#include <bits/stdc++.h>
using namespace std;


// heuristics:
//    1. Union by rank
/// 2. Path compression
class DisjointSet
{
public:
    class Node
    {
    public:
        Node*parent;
        int rank; // used for union by rank
        int associatedNodes; // maintaining the number of nodes in a group (for representative element)

        Node()
        {    
            rank = 1;
            associatedNodes = 1;
            parent = this;
        }
    };

    vector<Node*>nodes;
    DisjointSet(int n)
    {
        nodes=vector<Node*>(n);
        for(int i=0;i<n;i++)
            nodes[i]=new Node();
    }
    Node*find(Node*node) // returns the representative element of node
    {
        if(node->parent != node)
            node->parent = find(node->parent); // path compression
        return node->parent;
    }
    void merge(Node*n1,Node*n2)
    {
        Node*pn1 = find(n1);
        Node*pn2 = find(n2);
        if(pn1!=pn2)
        {
            if(pn1->rank > pn2->rank)
            {
                pn2->parent = pn1;
                pn1->associatedNodes += pn2->associatedNodes;
            }
            else 
            {
                pn1->parent = pn2;
                pn2->associatedNodes += pn1->associatedNodes;
            }
            if(pn1->rank == pn2->rank)
                pn2->rank++;
        }
    }

};

int main()
{
    int n;
    cin>>n;
    DisjointSet ds(n);

    int q;
    cin>>q;
    while(q--)
    {
        char ch;
        cin>>ch;
        if(ch=='M')
        {
            int a,b;
            cin>>a>>b;
            ds.merge(ds.nodes[a-1],ds.nodes[b-1]);
        }
        else if(ch=='Q')
        {
            int num;
            cin>>num;
            cout<<ds.find(ds.nodes[num-1])->associatedNodes<<endl;
        }
    }
    return 0;
}

But that's too much of hassle
The following code illustrates a clever implementation of Disjoint set data structure.

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010

vector<int>parent(MAXN),size(MAXN);

int find(int n) {
    if(parent[n]==n) return n;
    else return parent[n] = find(parent[n]);
}

void merge(int a,int b) {
    int pa = find(a);
    int pb = find(b);
    if(pa!=pb) {
        if(size[pa]>size[pb]) {
            parent[pb]=pa;
            size[pa]+=size[pb];
        }
        else {
            parent[pa]=pb;
            size[pb]+=size[pa];
        }
    }
}

int main()
{

    for(int i=0;i<MAXN;i++)
        parent[i] = i, size[i] = 1;

    int q,n,a,b,num;
    cin>>n>>q;

    while(q--) {
        char ch;
        cin>>ch;
        if(ch=='M') {
            cin>>a>>b;
            merge(a-1,b-1);
        }
        else if(ch=='Q') {
            cin>>num;
            cout<<size[find(num-1)]<<endl;
        }
    }
    return 0;
}

Snake Game in C++

// use following command to run : 
// g++ -std=c++14 snake.cpp -lpthread

#include <bits/stdc++.h>
#include <thread>
#include <unistd.h>
#include <termios.h>
using namespace std;

enum direction { LEFT, RIGHT, UP, DOWN };
enum tileConf { EMPTY, BLOCKED, OCCUPIED, FOOD };
enum gameState { RUNNING, OVER };

////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Tile
{
public:
 tileConf conf;
 Tile(tileConf);
};

Tile::Tile(tileConf tc)
{
 conf = tc;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Screen
{
public:
 int WIDTH,HEIGHT;
 vector< vector<Tile> >matrix;

 Screen();
 void print(int,int,int,int,int);
};

Screen::Screen()
{
 HEIGHT = 20;
 WIDTH = 50;
 Tile tile(EMPTY);
 matrix = vector< vector<Tile> >(HEIGHT,vector<Tile>(WIDTH,tile));
 /*
 for(int i=0;i<WIDTH;i++)
  matrix[HEIGHT-1][i].conf = matrix[0][i].conf = BLOCKED;
 for(int i=0;i<HEIGHT;i++)
  matrix[i][WIDTH-1].conf = matrix[i][0].conf = BLOCKED;
 */
}

void Screen::print(int score,int level,int snakex,int snakey,int snakeLength)
{
 system("clear");
 for(int i=0;i<WIDTH+2;i++)
  cout<<"@";
 cout<<endl;
 for(int i=0;i<HEIGHT;i++)
 {
  cout<<"@";
  for(int j=0;j<WIDTH;j++)
  {
   if(matrix[i][j].conf == OCCUPIED)
    cout<<'o';
   if(matrix[i][j].conf == BLOCKED)
    cout<<'#';
   if(matrix[i][j].conf == EMPTY)
    cout<<' ';
   if(matrix[i][j].conf == FOOD)
    cout<<'F';

  }
  cout<<"@"<<endl;
 }
 for(int i=0;i<WIDTH+2;i++)
  cout<<"@";
 cout<<endl;
 cout<<"SCORE : "<<score<<endl;
 cout<<"LEVEL : "<<level<<endl;
 cout<<"Snake_Length : "<<snakeLength<<endl;
 cout<<"Snake_head (X,Y) : "<<snakex<<","<<snakey<<endl;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Food
{
public:
 pair<int,int>coordinates;
 Food(Screen&);
};

Food::Food(Screen&screen)
{
 int x,y;
 do{
  x = rand()%screen.HEIGHT;
  y = rand()%screen.WIDTH;
 }while(screen.matrix[x][y].conf!=EMPTY);
 coordinates = make_pair(x,y);
 screen.matrix[x][y] = FOOD;
 cout<<x<<" "<<y<<endl;
 //exit(0);
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Snake
{
public:
 pair<int,int>head,tail;
 list< pair<int,int> >body;
 int currentLength;
 volatile direction headDirection;
 int speed;

 Snake(Screen&);
 Snake();

 void moveHeadLeft(Screen&,int&);
 void moveHeadRight(Screen&,int&);
 void moveHeadDown(Screen&,int&);
 void moveHeadUp(Screen&,int&);
 void moveTail(Screen&);

 void move(Screen&,int&);
 
 void eat(Screen&,int&);
 bool bitesItself(); // bites itself
 bool hitsWall(Screen&);
};



Snake::Snake()
{

}
Snake::Snake(Screen&screen)
{
 int startx = screen.HEIGHT/2;
 int starty = screen.WIDTH/2;
 int endx = startx;
 int endy = starty+2;

 head = make_pair(endx,endy);
 tail = make_pair(startx,starty);
 pair<int,int>intermediate = make_pair(startx,starty+1);

 body.push_back(head);
 body.push_back(intermediate);
 body.push_back(tail);

 currentLength = 3;
 headDirection = RIGHT;
 speed = 1;

 screen.matrix[head.first][head.second].conf = OCCUPIED;
 screen.matrix[intermediate.first][intermediate.second].conf = OCCUPIED;
 screen.matrix[tail.first][tail.second].conf = OCCUPIED;
}

void Snake::moveTail(Screen&screen)
{
 screen.matrix[tail.first][tail.second]=EMPTY;
 body.pop_back();
 tail = body.back();
}

void Snake::moveHeadLeft(Screen&screen,int &score)
{
 int newx = head.first;
 int newy = head.second-1;
 if(newy<0)
  newy+=screen.WIDTH;
 tileConf tc = screen.matrix[newx][newy].conf;
 if(tc==FOOD)
  eat(screen,score);
 else if(tc==BLOCKED || tc==OCCUPIED)
  exit(0);
 screen.matrix[newx][newy]=OCCUPIED;
 head = make_pair(newx,newy);
 body.push_front(head);
}

void Snake::moveHeadRight(Screen&screen,int &score)
{
 int newx = head.first;
 int newy = head.second+1;
 if(newy>=screen.WIDTH)
  newy%=screen.WIDTH;
 tileConf tc = screen.matrix[newx][newy].conf;
 if(tc==FOOD)
  eat(screen,score);
 else if(tc==BLOCKED || tc==OCCUPIED)
  exit(0);
 screen.matrix[newx][newy]=OCCUPIED;
 head = make_pair(newx,newy);
 body.push_front(head);
}

void Snake::moveHeadDown(Screen&screen,int &score)
{
 int newx = head.first+1;
 int newy = head.second;
 if(newx>=screen.HEIGHT)
  newx%=screen.HEIGHT;
 tileConf tc = screen.matrix[newx][newy].conf;
 if(tc==FOOD)
  eat(screen,score);
 else if(tc==BLOCKED || tc==OCCUPIED)
  exit(0);
 screen.matrix[newx][newy]=OCCUPIED;
 head = make_pair(newx,newy);
 body.push_front(head);
}

void Snake::moveHeadUp(Screen&screen,int &score)
{
 int newx = head.first-1;
 int newy = head.second;
 if(newx<0)
  newx = newx + screen.HEIGHT;
 tileConf tc = screen.matrix[newx][newy].conf;
 if(tc==FOOD)
  eat(screen,score);
 else if(tc==BLOCKED || tc==OCCUPIED)
  exit(0);
 screen.matrix[newx][newy]=OCCUPIED;
 head = make_pair(newx,newy);
 body.push_front(head);
}

void Snake::move(Screen &screen,int &score)
{
 
 if(headDirection == RIGHT)
  moveHeadRight(screen,score);
 else if(headDirection == LEFT)
  moveHeadLeft(screen,score);
 else if(headDirection == UP)
  moveHeadUp(screen,score);
 else if(headDirection == DOWN)
  moveHeadDown(screen,score);
 moveTail(screen);
}

void Snake::eat(Screen&screen,int &score)
{
 pair<int,int>tail1,tail2;
 tail1 = body.back();
 body.pop_back();
 tail2 = body.back();
 body.push_back(tail);

 direction tailDirection;
 int x1,y1,x2,y2;
 x1 = tail1.first;
 y1 = tail1.second;
 x2 = tail2.first;
 y2 = tail2.second;

 if(y1+1==y2)
 {
  body.push_back(make_pair(x1,y1-1));
  tail = body.back();
  screen.matrix[x1][y1-1].conf=OCCUPIED;
 }
 else if(y1==y2+1)
 {
  body.push_back(make_pair(x1,y1+1));
  tail = body.back();
  screen.matrix[x1][y1+1].conf=OCCUPIED;
 }
 else if(x1==x2+1)
 {
  body.push_back(make_pair(x1+1,y1));
  tail = body.back();
  screen.matrix[x1+1][y1].conf=OCCUPIED;
 }
 else if(x1+1==x2)
 {
  body.push_back(make_pair(x1-1,y1));
  tail = body.back();
  screen.matrix[x1-1][y1].conf=OCCUPIED;
 }

 currentLength++;
 score+=10;
 Food f(screen);
}

bool Snake::bitesItself()
{
 return false;
}

bool Snake::hitsWall(Screen&s)
{
 return false;
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Game
{
public:
 gameState state;
 int score;
 int level;
 Snake snake;
 Screen screen;

 Game();
 void run();
 void keepSnakeMoving(Snake&,Screen&);
};
Game::Game()
{
 state = RUNNING;
 score = 0; 
 level = 1;

 screen = Screen();
 snake = Snake(screen);
}
void Game::keepSnakeMoving(Snake &snake,Screen &screen)
{
 Food f(screen);
 while(true)
 //for(int i=0;i<10;i++)
 {
  usleep(100000);
  //cout<<"here"<<endl;
  snake.move(screen,score);
  screen.print(score,level,snake.head.first,snake.head.second,snake.currentLength);
 }
}

char getch() {
    char buf = 0;
    struct termios old = {0};
    if (tcgetattr(0, &old) < 0)
            perror("tcsetattr()");
    old.c_lflag &= ~ICANON;
    old.c_lflag &= ~ECHO;
    old.c_cc[VMIN] = 1;
    old.c_cc[VTIME] = 0;
    if (tcsetattr(0, TCSANOW, &old) < 0)
            perror("tcsetattr ICANON");
    if (read(0, &buf, 1) < 0)
            perror ("read()");
    old.c_lflag |= ICANON;
    old.c_lflag |= ECHO;
    if (tcsetattr(0, TCSADRAIN, &old) < 0)
            perror ("tcsetattr ~ICANON");
    return (buf);
}
void Game::run()
{
 thread th(&Game::keepSnakeMoving,this,std::ref(snake),std::ref(screen));
 
 while(true)
 {
  char ch = getch();
  if((ch=='w' || ch=='8') && snake.headDirection!=DOWN)
   snake.headDirection = UP;
  else if((ch=='d' || ch=='6') && snake.headDirection!=LEFT)
   snake.headDirection = RIGHT;
  else if((ch=='s' || ch=='5') && snake.headDirection!=UP)
   snake.headDirection = DOWN;
  else if((ch=='a' || ch=='4') && snake.headDirection!=RIGHT)
   snake.headDirection = LEFT;
 }
 th.join();
}


int main()
{
 srand((unsigned)time(0)); 
 Game g;
 g.run();
 return 0;
}

Ulam Spiral

The following post shows the distribution of primes when numbers are arranged in a spiral format as depicted below:

The above shown grid is a 7x7 grid.

If similarly we have a grid of 251x251 elements and highlight the primes withe red pixel, the image will look like the following:

And similarly if we randomly put a 0 or 1 on every pixel of 251x251 grid, we will get an image that will be somewhat like this:

We can clearly see that there is a pattern visible in case of Ulam Spiral where many prime numbers are present along different diagonals, where as random numbers follow no specific patterns.

If you are interested into the code of generating this ulam spiral and getting the above plots, have a look at below mentioned code. Basically I have used C++ to get a 2-D matrix where 1 represents that number is prime and 0 represents that it is composite. This all data is written into a file called ulam.txt and random data is written into random.txt.

Now these two file can be fed to the scilab code to get the above plots.

C++ code that will generate random.txt and ulam.txt :

#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<stdlib.h>
using namespace std;
#define MAX 10000000
bitset<MAX+1>isPrime;

void getPrimes()
{
    isPrime.reset();
    isPrime.flip();
    isPrime[0]=isPrime[1]=0;
    for(int i=2;i*i<=MAX;i++)
        if(isPrime[i])
            for(int j=i*i;j<=MAX;j+=i)
                isPrime[j]=0;
}

int**getUlamSpiral(int N)
{
    int **M;
    M=new int*[2*N+1];
    for(int i=0;i<2*N+1;i++)
        M[i]=new int[2*N+1];

    int r,c,current,counter;
    
    M[N][N]=1;
    r=N;
    c=N+1;
    counter=2;
    current=2;

    for(int j=0;j<N;j++,counter+=2)
    {
        for(int i=0;i<counter;i++)
            M[r--][c]=current++;
        r++;
        c--;
        for(int i=0;i<counter;i++)
            M[r][c--]=current++;
        c++;
        r++;
        for(int i=0;i<counter;i++)
            M[r++][c]=current++;
        r--;
        c++;
        for(int i=0;i<counter;i++)
            M[r][c++]=current++;
    }

    return M;
}
void printUlamSpiral(int **M,int N)
{
    for(int i=0;i<2*N+1;i++)
    {
        for(int j=0;j<2*N+1;j++)
            cout<<M[i][j]<<"\t";
        cout<<endl;
    }
}
int**filterPrimes(int**M,int N)
{
    int **M01;
    M01=new int*[2*N+1];
    for(int i=0;i<2*N+1;i++)
        M01[i]=new int[2*N+1];

    for(int i=0;i<1+2*N;i++)
    {
        for(int j=0;j<1+2*N;j++)
        {
            if(isPrime[M[i][j]])
                M01[i][j]=1;
            else M01[i][j]=0;
        }
    }
    return M01;
}
void writeToFile(string fileName,int**M,int N)
{
    FILE*fp;
    fp=fopen(fileName.c_str(),"w");
    if(fp)
    {
        fprintf(fp,"%d\n",N);
        for(int i=0;i<1+2*N;i++)
        {
            for(int j=0;j<1+2*N;j++)
            {
                fprintf(fp,"%d ",M[i][j]);
            }
            fprintf(fp,"\n");
        }
    }
    else cout<<"there is an error in opening the file\n";
}
int**fillRandom(int N)
{
    int **m;
    m=(int**)malloc(sizeof(int*)*(2*N+1));
    for(int i=0;i<2*N+1;i++)
        m[i]=(int*)malloc(sizeof(int)*(2*N+1));
    srand(time(NULL));
    for(int i=0;i<2*N+1;i++)
        for(int j=0;j<2*N+1;j++)
            m[i][j]=rand()%2;
    return m;
}
int main()
{
    int N;
    getPrimes();
    cin>>N;
    int **M=getUlamSpiral(N);
    //printUlamSpiral(M,N);
    int **M01=filterPrimes(M,N);
    int**R01=fillRandom(N);
    writeToFile("ulam.txt",M01,N);
    writeToFile("random.txt",R01,N);
    return 0;
}

Scilab Code

function DrawSpiral(filename)
    fid=mopen(filename,"r");
    [num_read,N]=mfscanf(fid, "%d");
    N
    M = hypermat([2*N+1 2*N+1]);
    for i=1:1+2*N
        for j=1:1+2*N
            [num_read,M(i,j)]=mfscanf(fid, "%d");
        end
    end
    mclose(fid);
    
    clf();
    ax = gca();//get current axes handle
    ax.data_bounds = [0, 0; 100, 100]; //set the data_bounds
    ax.box = 'on'; //draw a box
    Matplot1(M*20, [0,0,100,100])
endfunction


DrawSpiral('ulam.txt')

Steps of Execution :
First of all save the C++ code and compile it and then run it. The code will ask you to input a number N and it will create 2*N+1 by 2*N+1 matrix.

Now run the Scilab code to get the required plots.
You need to call DrawSpiral function 2 times, once with 'ulam.txt' and then with 'random.txt'.

Longest Common Subsequence

Code:

#include<bits/stdc++.h>
using namespace std;
void printLCS(string &x,string &y,int**table,int i,int j)
{
	if(i<=0 || j<=0)
		return ;
	if(x[i-1]==y[j-1])
	{
		printLCS(x,y,table,i-1,j-1);
		cout<<x[i-1];
	}
	else
	{
		if(table[i-1][j]>table[i][j-1])
			printLCS(x,y,table,i-1,j);
		else printLCS(x,y,table,i,j-1);
	}
}
int LCS(string &x,string &y) // using a 2-D table for storing solutions to subproblems
{
	int**table;
	table=new int*[x.size()+1];
	for(int i=0;i<=x.size();i++)
		table[i]=new int[y.size()+1];

	for(int i=0;i<=x.size();i++)
		table[i][0]=0;
	for(int i=0;i<=y.size();i++)
		table[0][i]=0;

	for(int i=1;i<=x.size();i++)
	{
		for(int j=1;j<=y.size();j++)
		{
			if(x[i-1]==y[j-1])
				table[i][j]=table[i-1][j-1]+1;
			else
				table[i][j]=max(table[i-1][j],table[i][j-1]);
		}
	}
	printLCS(x,y,table,x.size(),y.size());
	cout<<endl;
	int answer=table[x.size()][y.size()];
	
	for(int i=0;i<=x.size();i++)
		delete table[i];
	delete table;
	return answer;
}

int main()
{
	string x,y;
	cin>>x>>y;
	cout<<"Length of LCS is : "<<LCS(x,y)<<endl;
	return 0;
}

The following are two optimized solution that follow the same approach but are more space efficient. Instead of using a 2-D table, we can use only two 1-D arrays to store the solution to subproblems.

The following is the code:

// just swapping the pointers of the array
int LCSOptimized1(string &x,string &y) // using two 1-D arrays to store the solutions to subproblems
{
	int *table1,*table2;
	table1=new int[y.size()+1];
	table2=new int[y.size()+1];

	for(int i=0;i<=y.size();i++)
		table1[i]=0;

	for(int i=1;i<=x.size();i++)
	{
		for(int j=1;j<=y.size();j++)
		{
			if(x[i-1]==y[j-1])
				table2[j]=1+table1[j-1];
			else table2[j]=max(table2[j-1],table1[j]);
		}
		int *temp;
		temp=table1;
		table1=table2;
		table2=temp;
	}
	return max(table1[y.size()],table2[y.size()]);
}

// a more tricky solution that uses two 1-D arrays.
int LCSOptimized2(string &x,string &y)
{
	int **table;
	table=new int*[2];
	table[0]=new int[y.size()+1];
	table[1]=new int[y.size()+1];

	for(int i=0;i<=y.size();i++)
		table[0][i]=0;

	int index=0;
	for(int i=1;i<=x.size();i++)
	{
		for(int j=1;j<=y.size();j++)
		{
			if(x[i-1]==y[j-1])
				table[index^1][j]=table[index][j-1]+1;
			else
			{
				table[index^1][j]=max(table[index^1][j-1],table[index][j]);
			}
		}
		index=(index^1);
	}
	int answer=table[index][y.size()]; // answer=max(table[0][y.size()],table[1][y.size()]);
	delete table[0];
	delete table[1];
	return answer; 	
}

Largest Sum Contiguous Subarray

Kadane's Algorithm

The following code works even if all the elements of the array are negative.
Code:

#include<bits/stdc++.h>
using namespace std;
int kadane(int*arr,int n)
{
 int sum=0,max=INT_MIN;
 for(int i=0;i<n;i++)
 {
  sum=sum+arr[i];
  if(max<sum)
   max=sum;
  if(sum<0)
   sum=0; 
 }
 return max;
}
int main()
{
 int *arr,n;
 cin>>n;
 arr=new int[n];
 for(int i=0;i<n;i++)
  cin>>arr[i];
 cout<<kadane(arr,n)<<endl;
 return 0;
}

Number of Monotonic Lattice paths - Dynamic Programming

Find the number of monotonic lattice paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards.

Code:

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
ll findMonotonicLatticePaths(int n)
{
	// simple formula is Catalan number 
	// 2nCn / (n+1)
	ll**table;
	table=new ll*[n+1];
	for(int i=0;i<=n;i++)
		table[i]=new ll[n+1];
	// table[i][j] denotes the number of shortest paths to reach (0,n) from (n,0)
	table[n][0]=0;
	table[n][1]=1;
	
	for(int j=1;j<=n;j++)
	{
		table[n][j]=1; // base case
		for(int i=n-1;i+j>=n;i--)
		{
			int x=0,y=0;
			if(j-1>=0 && i+j-1>=n)
				x=table[i][j-1];
			if(i+1<=n && i+1+j>=n)
				y=table[i+1][j];
			table[i][j]=x+y;
		}
	}
	return table[0][n];
}

int main()
{
	int n;
	cin>>n;
	cout<<findMonotonicLatticePaths(n)<<endl;
}

Subset Sum Problem - Dynamic Programming

Given a set of n numbers a sum up to M , and any K ≤ M , say whether there is a subset of the numbers such that they sum to K? We assume n might be as big as 1000, but M or K is not too big.

code

#include<bits/stdc++.h>
using namespace std;

// function to print the elements of subset that forms the given sum
void printSubset(int*arr,int n,int S,bool**table,int i,int j)
{
    if(i<=0 || j<=0)
        return;

    if(table[i][j-1]) // the jth element was not taken for sure.
    {
        printSubset(arr,n,S,table,i,j-1);
    }
    else // the jth element was taken for sure.
    {
        cout<<arr[j-1]<<" ";
        printSubset(arr,n,S,table,i-arr[j-1],j-1);
    }
}

bool isSubsetSum(int *arr,int n,int S)
{
    bool **table; // table of size S x n
    table=new bool*[S+1];
    for(int i=0;i<=S;i++)
        table[i]=new bool[n+1];

    // table[i][j] will be true if sum 'i' can be achieved using first j elements of the array.

    //base cases

    // from the first 0 elements you can never achieve any sum.
    for(int i=0;i<=S;i++)
        table[i][0]=false;
    // 0 sum can be achieved by any number of elements.
    for(int i=0;i<=n;i++)
        table[0][i]=true;

    for(int i=1;i<=S;i++)
        for(int j=1;j<=n;j++)
        {
            table[i][j]=table[i][j-1];
            if(i-arr[j-1]>=0)
                table[i][j]=table[i][j] || table[i-arr[j-1]][j-1];
        }

    bool answer=table[S][n];
    if(answer)
        printSubset(arr,n,S,table,S,n);
    
    for(int i=0;i<=S;i++)
        delete table[i];
    delete table;
    
    return answer;
}

int main()
{
    int n;
    cout<<"Enter the number of elements of the array : ";
    cin>>n;
    int *arr;
    arr=new int[n];
    
    cout<<"Enter the elements of the array : ";
    for(int i=0;i<n;i++)
        cin>>arr[i];

    int S;
    cout<<"Enter the sum : ";
    cin>>S;
    cout<<endl<<isSubsetSum(arr,n,S)<<endl;;
    return 0;
}

Remark. The original idea is to use a 2 dimensional array, where each column only depends on the previous column. By a programming trick we just need one column. But we need to write the j-loop in the reversed way to avoid messing things up. 
The following code shows how to achieve this.

bool isSubsetSumOptimized(int*arr,int n,int S)
{
    bool *table;
    table=new bool[S+1];
    table[0]=1;
    for(int i=0;i<n;i++)
        for(int j=S;j>=arr[i];j--)
            table[j]=table[j]||table[j-arr[i]];
    bool answer=table[S];
    delete table;
    return answer;
}

String Formatting Question - Smartprix Coding Test

Replacement Array is an array of elements.
Format String contains conversion specifier %s, followed by optional index specifier [1], followed by optional length specifier :3.
Format String: %s[1]:3
%s is conversion specifier - mark the starting of conversion string
[1] is index specifier - corresponding index of Replacement Array
:3 is length specifier - number of characters to be taken from string



The replacement works as follows:
Example:
Replacement Array: Smart site India comparison Best
Format String: %sprix is the %s[4] online %s[3]:6 shopping %s:9 in %s
Output: Smartprix is the Best online compar shopping site in India.
If no index specifier is present with conversion specifier %s, Index 0, 1, 2, 3... are assigned to all in sequence from left to right.
In above example %sprix is %s[0]prix; %s:9 is %s[1]:9 and so on.
The specifier string is replaced by element of Replacement Array denoted by index specifier. If no element is found the specifier is not replaced.
In above example %s[4] is replaced by element at 4th index of the Replacement Array "Best". %sprix is replaced by Smartprix and so on.
%s[3]:6 is replaced by 'first 6 characters' of the element at 3rd index of the Replacement Array, i.e., "compar".
If the 'length specifier' is not present or is greater than length of the element then use whole string.
%s:9 is replaced by site, %s[4] is replaced by Best.
For any error case, specifier is not replaced.



Input:
There will be 2 lines in the input.
1st line contains space separated elements of Replacement Array
2nd line is Format String



Output:
Formatted String



INPUT 1
smart site india comaprision best
%sprix is the %s[4] online %s[3]:6 shopping %s:9 in %s
OUTPUT
smartprix is the best online comapr shopping site in india


INPUT 2
india boom startup up hub
%s %s[is] a %sing %s:5%s:5 %s[4]. and %s[6] are :4 of %s[-1].
OUTPUT
india %s[is] a booming startup hub. and %s[6] are :4 of %s[-1].


INPUT 3
hello lavish kothari
%s[2]:xyz
OUTPUT
%s[2]:xyz

#include<bits/stdc++.h>
using namespace std;

int findCase(string &b,int index)
{
    if(index+2>=b.size())
        return 1;
    /*
    if(b[index+2]!=':' && b[index+2]!='[')
        return 1;
    */
    
    if(b[index+2]==':' && index+3<b.size() && b[index+3]>='0' && b[index+3]<='9')
        return 4;
    if(b[index+2]==':')
        return 0;
    
    if(b[index+2]=='[')
    {
        int i=index+3;
        if(i>=b.size() || b[i]<='0' || b[i]>='9')
            return 0;
        while(i<b.size() && b[i]>='0' && b[i]<='9')
            i++;
        if(i==b.size())
            return 0;           // for case %s[1234
        else if(b[i]==']')
        {
            if(i+1>=b.size() || b[i+1]!=':')
                return 2;
            else if(b[i+1]==':')
            {
                if(i+2>=b.size())
                    return 0;
                else if(b[i+2]>='0' && b[i+2]<='9')
                    return 3;
                else
                    return 0;
            }
        }
        else return 1;
    }
    return 1;
}
int extract(string &b,int index)
{
    int sum=0;
    while(index<b.size() && b[index]>='0' && b[index]<='9')
    {
        sum=sum*10+b[index]-'0';
        index++;
    }
    return sum;
}
void findFormattedString(string &a,string &b)
{
    vector<string>vs;
    int start=0;int len=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==' ')
        {
            vs.push_back(a.substr(start,len));
            while(i<a.size() && a[i]==' ')
                i++;
            start=i;
            len=0;
        }
        len++;
    }
    if(a[a.size()-1]!=' ')
        vs.push_back(a.substr(start,a.size()-start));
    
    /*
    for(int i=0;i<vs.size();i++)
        cout<<"**"<<vs[i]<<endl;
    */
    int counter=0,startfrom=0;
    while(1)
    {
        int index=b.find("%s",startfrom);
        if(index<0)
            break;
        int c=findCase(b,index);
        if(c==1)
        {
            if(counter>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            b.erase(b.begin()+index,b.begin()+index+2);
            b.insert(index,vs[counter]);
            counter++;
        }
        else if(c==2)
        {
            int number=extract(b,index+3);
            if(number<0 || number>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i+1);
            b.insert(index,vs[number]);
        }
        else if(c==3)
        {
            int number1=extract(b,index+3);
            if(number1<0 || number1>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i+2);
            
            int number2=extract(b,index);
            i=index;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i);
            
            if(vs[number1].size()<=number2)
            {
                b.insert(index,vs[number1]);
            }
            else 
                b.insert(index,vs[number1].substr(0,number2));
        }
        else if(c==4)
        {
            if(counter>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int number=extract(b,index+3);
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i);
            if(vs[counter].size()<=number)
            {
                b.insert(index,vs[counter++]);
            }
            else 
                b.insert(index,vs[counter++].substr(0,number));
        }
        else if(c==0)
            startfrom=index+1;
    }
}
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    findFormattedString(a,b);
    cout<<b<<endl;
    return 0;
}

Water Jug Problem (Oracle Interview)

This problem was asked to me during my Oracle interview. The interviewer asked me to write down the code for the same.
 
Problem :

You are given three water jugs.
Let the capacity of jugs be X, Y and Z. (X >= Y >= Z).
As described in all common water jug problems, neither of the jugs has any measuring markers on it.

Initially we have only the first jug (with capacity X) fully filled up to brim (the other two jugs are initially empty).
Now you need to tell whether it is possible or not to transfer the water, in such a way that you reach to a state in which any two jugs have equal amount of water in them, and the third jug is empty.
In short, you have to divide X litre of water into two equal halves. These two equal halves can be in any of the two jugs.

Example
Suppose, X=10, Y=7, Z=3
Solution steps:
10 0 0 -> Initial State
3 7 0
0 7 3
7 0 3
7 3 0
4 3 3
4 6 0
1 6 3
1 7 2
8 0 2
8 2 0
5 2 3
5 5 0 -> Final State


C++ Program to solve this problem :

#include<bits/stdc++.h>
using namespace std;
class triplet
{
    public:
    int x,y,z;
    triplet(int x,int y,int z)
    {
        this->x=x;
        this->y=y;
        this->z=z;
    }
    
};
bool findTriplet(vector<triplet>&v,int x,int y,int z)
{
    for(int i=0;i<v.size();i++)
        if(v[i].x==x && v[i].z==z && v[i].y==y)
            return true;
    return false;
}
bool getSteps(int x,int y,int z,int X,int Y,int Z) // x y and z denotes the current capacity.
{
    static vector<triplet>v;
    if(findTriplet(v,x,y,z))
        return false;
    else 
        v.push_back(triplet(x,y,z));
    cout<<x<<" "<<y<<" "<<z<<endl;
    if(x==y && z==0)
        return true;
    if(z==y && x==0)
        return true;
    if(x==z && y==0)
        return true;
    
    /*********************************--> transferring from X <--*****************************************************/        
    if(x>0)
    {
        // transferring from x to y
        {
        int emptyy=Y-y;
        int newx,newy;
        if(emptyy>=x)
        {
            newy=y+x;
            newx=0;
        }
        else
        {
            newy=Y;
            newx=x-emptyy;
        }
        if(emptyy>0 && getSteps(newx,newy,z,X,Y,Z))
            return true;
        }
    
        // transferring from x to z
        {
        int emptyz=Z-z;
        int newx,newz;
        if(emptyz>=x)
        {
            newz=z+x;
            newx=0;
        }
        else
        {
            newz=Z;
            newx=x-emptyz;
        }
        if(emptyz>0 && getSteps(newx,y,newz,X,Y,Z))
            return true;
        }
    }
            
    /*********************************--> transferring from Y <--*****************************************************/        
    if(y>0)
    {
        // transferring from y to x
        {
        int emptyx=X-x;
        int newx,newy;
        if(emptyx>=y)
        {
            newx=x+y;
            newy=0;
        }
        else
        {
            newx=X;
            newy=y-emptyx;
        }
        if(emptyx>0 && getSteps(newx,newy,z,X,Y,Z))
            return true;
        }
    
        // transferring from y to z
        {
        int emptyz=Z-z;
        int newy,newz;
        if(emptyz>=y)
        {
            newz=z+y;
            newy=0;
        }
        else
        {
            newz=Z;
            newy=y-emptyz;
        }
        if(emptyz>0 && getSteps(x,newy,newz,X,Y,Z))
            return true;
        }
    }
            
    /*********************************--> transferring from Z <--*****************************************************/        
    if(z>0)
    {
        // transferring from z to y
        {
        int emptyy=Y-y;
        int newz,newy;
        if(emptyy>=z)
        {
            newy=y+z;
            newz=0;
        }
        else
        {
            newy=Y;
            newz=z-emptyy;
        }
        if(emptyy>0 && getSteps(x,newy,newz,X,Y,Z))
            return true;
        }
    
        // transferring from z to x
        {
        int emptyx=X-x;
        int newz,newx;
        if(emptyx>=z)
        {
            newx=z+x;
            newz=0;
        }
        else
        {
            newx=X;
            newz=z-emptyx;
        }
        if(emptyx>0 && getSteps(newx,y,newz,X,Y,Z))
            return true;
        }
    }
    return false;
}
int main()
{
    int x,y,z;
    cin>>x>>y>>z;
    if(getSteps(x,0,0,x,y,z))
        cout<<"Yes!! you got a solution!!"<<endl;
    else cout<<"No solution found!!"<<endl;
    return 0;
}

Please write comments if you find anything incorrect, or you want to share more information about the problem discussed above.

Reverse a Linked List in groups of given size

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

struct node {
	int value;
	struct node* next;
};

struct node* createnode(int no) {
	
	struct node*temp;
	
	temp = (struct node*)malloc(sizeof(struct node*));
	temp->value = no;
	temp->next = NULL;

	return temp;
}

struct node * insert(struct node*  head, int no) {

	struct node *temp, *headcp;
	temp = createnode( no);

	if(head == NULL)
		return temp;


	headcp = head;
	
	while(head->next != NULL) {
		head = head->next;
	}
	head->next = temp;
	return headcp;
}

void print (struct node*  head) {

	while(head != NULL) {
		printf("%d -> ",head->value);
		head = head->next;
	}


}
struct node*reverse(struct node*head,int k)
{
	int counter=0;
	struct node*current,*prev,*nxt;
	if(head==NULL || head->next==NULL)
		return head;
	prev=NULL;
	current=head;
	nxt=head->next;
	while(current && counter!=k)
	{
		current->next=prev;
		prev=current;
		current=nxt;
		if(nxt)
			nxt=nxt->next;
		counter++;
	}
	return prev;
}

struct node*reverseInBlocksIterative(struct node*head,int k)
{
	struct node*ret,*newhead,*prev,*current,*last;
	int counter=0,i;
	if(k==1 || !head || !(head->next))
		return head;
	
	for(i=0,ret=head;i<k-1 && ret;i++)
		ret=ret->next;
	if(!ret)
		return reverse(head,k);
	
	current=head;
	prev=head;
	last=NULL;
	while(current)
	{
		for(i=0;i<k && current;i++)
			current=current->next;
		newhead=reverse(prev,k);
		prev=current;
		if(last)
			last->next=newhead;
		while(newhead->next)
			newhead=newhead->next;
		last=newhead;
	}
	return ret;
}

struct node*reverseInBlocksRecursive(struct node*head,int k)
{
	int i;
	struct node*current,*ptr,*ret;
	if(!head)
		return NULL;
	for(i=0,current=head;i<k && current;i++)
		current=current->next;
	ret=reverse(head,k);
	for(ptr=ret;ptr->next;ptr=ptr->next);
	ptr->next=reverseInBlocksRecursive(current,k);
	return ret;
}

int main () {

	struct node*head=NULL;
	head = insert(head, 1);	
	head = insert(head, 2);	
	head = insert(head, 3);	
	head = insert(head, 4);	
	head = insert(head, 5);	
	head = insert(head, 6);	
	head = insert(head, 7);	
	head = insert(head, 8);			
	head = insert(head, 9);			
	head = insert(head, 10);			
	head = insert(head, 11);			
	head = insert(head, 12);			

	int k;
	scanf("%d",&k);
	head = reverseInBlocksRecursive(head, k);
	print(head);

	return 0;
}

Snakes and Ladders - Codechef - Solution

Problem Statement:
Bhuvesh takes out his Snakes and Ladders game and stares at the board, and wonders: If he had absolute control on the die, and could get it to generate any number (in the range 1-6) he desired, what would be the least number of rolls of the die in which he'd be able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1)?

Rules

Bhuvesh has total control over the die and the face which shows up every time he tosses it. You need to help him figure out the minimum number of moves in which he can reach the target square (100) after starting at the base (Square 1).
A die roll which would cause the player to land up at a square greater than 100, goes wasted, and the player remains at his original square. Such as a case when the player is at Square Number 99, rolls the die, and ends up with a 5.
If a person reaches a square which is the base of a ladder, (s)he has to climb up that ladder, and he cannot come down on it. If a person reaches a square which has the mouth of the snake, (s)he has to go down the snake and come out through the tail - there is no way to climb down a ladder or to go up through a snake.

Input

The first line contains the number of tests, T. T testcases follow.

For each testcase, there are 3 lines.

The first line contains the number of ladders and snakes, separated by a comma.
The second is a list of comma separated pairs indicating the starting and ending squares of the ladders. The first point is the square from which a player can ascend and the second point is his final position.
The third is a list of comma separated pairs indicating the starting and ending (mouth and tail) squares of the snakes. the first point is the position of the mouth of the snake and the second one is the tail.
Multiple comma separated pairs of snakes and ladders are separated by a single space.


Output

Output description.

For each of the T test cases, output one integer, each of a new line, which is the least number of moves (or rolls of the die) in which the player can reach the target square (Square Number 100) after starting at the base (Square Number 1). This corresponds to the ideal sequence of faces which show up when the die is rolled.


Constraints

    1 ≤ T ≤ 10
    1 ≤ Number of snakes, Number of ladders ≤ 15


Example

Input:
3
3,7
32,62 42,68 12,98
95,13 97,25 93,37 79,27 75,19 49,47 67,17
5,8
32,62 44,66 22,58 34,60 2,90
85,7 63,31 87,13 75,11 89,33 57,5 71,15 55,25
4,9
8,52 6,80 26,42 2,72
51,19 39,11 37,29 81,3 59,5 79,23 53,7 43,33 77,21

Output:
3
3
5


Solution:

/*
    Assumptions: 
        There always exists a solution - ie.. the graph formed is always connected.
        There is no chain of snakes and ladders.

*/

#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
struct Ladder_Snake
{
    int start,end;
};
class Vertex
{
    public:
    int distance,parent;
    bool isVisited;
    vector<int>adj_list;
    Vertex(){}
    Vertex(int distance,bool isVisited)
    {
        this->distance=distance;
        this->isVisited=isVisited;
    }
};
map<int , Vertex>graph;    // making the graph global
void bfs(int start)
{
    vector<int>q;
    q.push_back(start);
    
    graph[start].isVisited=true;
    graph[start].distance=0;
    graph[start].parent=0;
    
    while(q.size()!=0)
    {
        int v=q[0];
        q.erase(q.begin());
        for(int i=0;i<graph[v].adj_list.size();i++)
        {
            int u=graph[v].adj_list[i];
            if(graph[u].isVisited==false)
            {
                q.push_back(u);
                graph[u].parent=v;
                graph[u].isVisited=true;
                graph[u].distance=graph[v].distance+1;
            }
        }
    }
}

int isStart(int x,struct Ladder_Snake *arr,int n)
{
    for(int i=0;i<n;i++)
        if(arr[i].start==x)
            return arr[i].end;
    return -1;
}
void getNumbers(char*str,int *a,int *b)
{
    int flag=0,start=0,end=0;
    for(int j=0;str[j];j++)
    {
        if(str[j]==',')
            flag=1;continue;
        if(flag==0)
            start=start*10+str[j]-'0';
        else
            end=end*10+str[j]-'0';
    }
    (*a)=start;
    (*b)=end;    
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int ladders,snakes;
        char str[100];
        scanf("%s",str);
        getNumbers(str,&ladders,&snakes);
        
        struct Ladder_Snake ladder[15];
        for(int i=0;i<ladders;i++)
        {
            scanf(" %s",str);
            getNumbers(str,&(ladder[i].start),&(ladder[i].end));
        }
        
        struct Ladder_Snake snake[15];
        for(int i=0;i<snakes;i++)
        {
            scanf("%s",str);
            getNumbers(str,&(snake[i].start),&(snake[i].end));
        }
                
        for(int i=1;i<=100;i++)
        {
            if(isStart(i,snake,snakes)!=-1 || isStart(i,ladder,ladders)!=-1)
                continue;
            graph[i]=Vertex(0,false);
            for(int j=i+1;j<=100 && j<i+7;j++)
            {
                int x,y;
                x=isStart(j,snake,snakes);
                y=isStart(j,ladder,ladders);
                if(x!=-1)
                    graph[i].adj_list.push_back(x);
                else if(y!=-1)
                    graph[i].adj_list.push_back(y);
                else graph[i].adj_list.push_back(j);
            }
        }
        // graph construction completed here.
        // printing the graph.
        bfs(1);
        /*
        for(map<int,Vertex> ::iterator it=graph.begin();it!=graph.end();it++)
        {
            printf("%d -> ",it->first);
            Vertex v=it->second;
            for(int j=0;j<v.adj_list.size();j++)
            {
                printf("%d ",v.adj_list[j]);
            }
            printf("\t\t%d",v.parent);
            printf("\n");
        }
        */
        
        printf("%d\n",graph[100].distance);
        
    }
    return 0;
}