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;
}

Chinese Remainder Theorem - Program in C

#include<stdio.h>
#include<stdlib.h>
long long int modularMultiplicativeInverse_BruteForce(long long int e,long long int mod)
{
    long long int i;
    for(i=1;i<mod;i++)
        if((e*i)%mod==1)
            return i;
}
int main()
{
    long long int i,n,*a,*b,*m,M,*Marray,answer;
    printf("Enter the number of Equations : \n");
    scanf("%lld",&n);
    a=(long long int*)malloc(sizeof(long long int)*n);
    m=(long long int*)malloc(sizeof(long long int)*n);
    Marray=(long long int*)malloc(sizeof(long long int)*n);
    printf("Enter the array a :\n");
    for(i=0;i<n;i++)
        scanf("%lld",&a[i]);
    printf("Enter the array m (all the elements of m should be pairwise co-prime) :\n");
    for(i=0;i<n;i++)
        scanf("%lld",&m[i]);
    M=1;
    for(i=0;i<n;i++)
        M*=m[i];
    for(i=0;i<n;i++)
        Marray[i]=M/m[i];
    answer=0;
    for(i=0;i<n;i++)
        answer = (answer + ((a[i] * Marray[i])%M * modularMultiplicativeInverse_BruteForce(Marray[i],m[i]))%M)%M;
    printf("x = %lld\n",answer);
    return 0;
}

Euclidean Algorithm for finding GCD of two numbers - Program in C

#include<stdio.h>

long long int gcd_Euclid_Recursive(long long int a,long long int b)
{
    if(b==0)
        return a;
    return gcd_Euclid_Recursive(b,a%b);
}


long long int gcd_Euclid_NonRecursive(long long int a,long long int b)
{
    long long int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    long long int a,b;
    printf("Enter two number : ");
    scanf("%lld%lld",&a,&b);
    printf("gcd(%lld,%lld) = %lld\n",a,b,gcd_Euclid_Recursive(a,b));
    printf("gcd(%lld,%lld) = %lld\n",a,b,gcd_Euclid_NonRecursive(a,b));
    return 0;
}

Rail Fence Cipher - Program in C

In the rail fence cipher, the plaintext is written downwards and diagonally on successive "rails" of an imaginary fence, then moving up when we reach the bottom rail. When we reach the top rail, the message is written downwards again until the whole plaintext is written out. The message is then read off in rows. For example, if we have 3 "rails" and a message of 'WE ARE DISCOVERED. FLEE AT ONCE', the cipherer writes out:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Then reads off to get the ciphertext:

WECRL TEERD SOEEF EAOCA IVDEN

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char *plainTextToCipherText(char plainText[],int n)
{
    int i,j,counter,limit,index=0,len;
    char *cipherText;
    len=strlen(plainText);
    cipherText=(char*)malloc(sizeof(char)*(len+1));
    for(i=0;i<n;i++)
 {
  counter=0;
  for(j=i;j<len;j+=limit)
  {
   cipherText[index++]=plainText[j];
   if(i==0 || i==n-1)
       limit=2*n-2;
   else if(counter%2==0)
    limit=2*(n-i-1);
   else
    limit=2*i;
   if(limit<=0)
       break;
   counter++;
  }
 }
 cipherText[index]='\0';
 return cipherText;
}
int main()
{
 int n;
 char plainText[100];
 printf("Enter the plain text : ");
 scanf("%s",plainText);
 printf("Enter the value of n : ");
 scanf("%d",&n);
    printf("%s\n",plainTextToCipherText(plainText,n)); 
 return 0;
}

RSA Algorithm - Program in C

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, theencryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames ofRon Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977. 

The RSA algorithm involves three steps: key generation, encryption and decryption.

Key generation

RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
   • For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
   • n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function. This value is kept private.
4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
   • e is released as the public key exponent.
   • e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 2¹⁶ + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.^[5]
5. Determine d as d ≡ e⁻¹ (mod φ(n)); i.e., d is the modular multiplicative inverse of e (modulo φ(n)).

• This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n))
• This is often computed using the extended Euclidean algorithm. Using the pseudocode in the Modular integers section, inputs a and n correspond to e and φ(n), respectively.
• d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and φ(n) must also be kept secret because they can be used to calculate d.

Encryption

Alice transmits her public key (n, e) to Bob and keeps the private key d secret. Bob then wishes to send message M to Alice.

He first turns M into an integer m, such that 0 ≤ m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to

This can be done efficiently, even for 500-bit numbers, using Modular exponentiation. Bob then transmits c to Alice.

Note that at least nine values of m will yield a ciphertext c equal to m,^{[note 1]}

Decryption[edit]

Alice can recover m from c by using her private key exponent d via computing

Given m, she can recover the original message M by reversing the padding scheme.

(In practice, there are more efficient methods of calculating c^d using the precomputed values below.)

A worked example[edit]

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

1. Choose two distinct prime numbers, such as

    and 

2. Compute n = pq giving

   

3. Compute the totient of the product as φ(n) = (p − 1)(q − 1) giving

   

4. Choose any number 1 < e < 3120 that is coprime to 3120. Choosing a prime number for e leaves us only to check that e is not a divisor of 3120.

   Let 

5. Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding,

   

   Worked example for the modular multiplicative inverse:

   

   

The public key is (n = 3233, e = 17). For a padded plaintext message m, the encryption function is

The private key is (d = 2753). For an encrypted ciphertext c, the decryption function is

For instance, in order to encrypt m = 65, we calculate

To decrypt c = 2790, we calculate

Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real-life situations the primes selected would be much larger; in our example it would be trivial to factor n, 3233 (obtained from the freely available public key) back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.

/*
    Sample test case 1 :
        Choose p = 3 and q = 11
        Compute n = p * q = 3 * 11 = 33
        Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
        Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
        Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
        Public key is (e, n) => (7, 33)
        Private key is (d, n) => (3, 33)
        The encryption of m = 2 is c = 27 % 33 = 29
        The decryption of c = 29 is m = 293 % 33 = 2
        
    Sample test case 2 :
        Choose p = 61 and q = 53
        Compute n = p * q = 61 * 53 = 3233
        Compute φ(n) = (p - 1) * (q - 1) = 60 * 52 = 3120
        Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 17
        Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 2753 [(2753 * 17) % 20 = 1]
        Public key is (e, n) => (17, 3233)
        Private key is (d, n) => (2753, 3233)
        The encryption of m = 65 is c = 2790
        The decryption of c = 2790 is m = 65
*/
#include<stdio.h>
/*
    Exponentiation by squaring
        http://en.wikipedia.org/wiki/Exponentiation_by_squaring
*/
long long int power(long long int a,long long int b,long long int mod)
{
    long long int t;
    if(b==0)
        return 1;
    else if(b==1)
        return a;
    t=power(a,b/2,mod);
    if(b%2==0)
        return (t*t)%mod;
    else
        return (((t*t)%mod)*a)%mod;
}

/*
    Euler's theorem may be used to compute modular inverse:
    According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
        
        inverse of a = power(a,m-2) % m 
        
    but for Euler's m must be prime.
        and our mod will never be prime.
            because mod is phi(n) = (p-1)*(q-1) ... so this is never prime.
    so we cant apply Eulers Theorem to find multiplicative inverse of e
*/
/*
long long int modularMultiplicativeInverse_Euler(long long int e,long long int mod)
{
    return power(e,mod-2,mod);
}
*/
/*
long long int modularMultiplicativeInverse_ExtendedEuclideantheorem(long long int e,long long int mod)
{
    
}
*/
long long int modularMultiplicativeInverse_BruteForce(long long int e,long long int mod)
{
    long long int i;
    for(i=1;i<mod;i++)
        if((e*i)%mod==1)
            return i;
}
long long int encrypt(long long int m,long long int e,long long int n)
{
    return power(m,e,n);
}
long long int decrypt(long long int c,long long int d,long long int n)
{
    return power(c,d,n);
}
int main()
{
 long long int p,q,n,phin,d,e,m,c;
 // p and q should be prime numbers of similar bit length.
 printf("Enter the value of p and q (p and q should be primes of similar bit length) :\n");
 scanf("%lld%lld",&p,&q);
 n=p*q;
 phin=(p-1)*(q-1);

 printf("Enter an integer e such that 1 < e < %lld, and gcd(e,%lld)=1 : ",phin,phin);
 scanf("%lld",&e);

 printf("NOTE : %lld,%lld is your public key.\n",e,n);
 // e is called the public key exponent
 
 d=modularMultiplicativeInverse_BruteForce(e,phin);
 printf("NOTE : %lld,%lld is your private key.\n",d,n);
 // d is called the private key exponent
    
    printf("\nEnter the number to be encrypted : ");
    scanf("%lld",&m);
    c=encrypt(m,e,n); // sending the message to be encrypted and the public key.
    printf("the encrypted message is : %lld\n",c);
    
    printf("\nEnter the number to be decrypted : ");
    scanf("%lld",&c);
    m=decrypt(c,d,n); // sending the cipher message to be decrypted and the private key.
    printf("the decrypted message is : %lld\n",m);
 return 0;
}

Diffie Hellman Key Exchange Algorithm - Program in C

Diffie–Hellman establishes a shared secret that can be used for secret communications while exchanging data over a public network. The crucial part of the process is that Alice and Bob exchange their secret colors in a mix only. Finally this generates an identical key that is computationally difficult (impossible for modern supercomputers to do in a reasonable amount of time) to reverse for another party that might have been listening in on them. Alice and Bob now use this common secret to encrypt and decrypt their sent and received data. 

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. Here is an example of the protocol, with non-secret values in blue, and secret values in red.

1. Alice and Bob agree to use a prime number p = 23 and base g = 5 (which is a primitive root modulo 23).
2. Alice chooses a secret integer a = 6, then sends Bob A = g^a mod p
   • A = 5⁶ mod 23 = 8
3. Bob chooses a secret integer b = 15, then sends Alice B = g^b mod p
   • B = 5¹⁵ mod 23 = 19
4. Alice computes s = B^a mod p
   • s = 19⁶ mod 23 = 2
5. Bob computes s = A^b mod p
   • s = 8¹⁵ mod 23 = 2
6. Alice and Bob now share a secret (the number 2).

/*
 this program calculates the Key
 for two persons
 using the Diffie Hellman Key exchange algorithm
*/
#include<stdio.h>
long long int power(int a,int b,int mod)
{
 long long int t;
 if(b==1)
  return a;
 t=power(a,b/2,mod);
 if(b%2==0)
  return (t*t)%mod;
 else
  return (((t*t)%mod)*a)%mod;
}
long long int calculateKey(int a,int x,int n)
{
 return power(a,x,n);
}
int main()
{
 int n,g,x,a,y,b;
 // both the persons will be agreed upon the common n and g
 printf("Enter the value of n and g : ");
 scanf("%d%d",&n,&g);

 // first person will choose the x
 printf("Enter the value of x for the first person : ");
 scanf("%d",&x);
 a=power(g,x,n);

 // second person will choose the y
 printf("Enter the value of y for the second person : ");
 scanf("%d",&y);
 b=power(g,y,n);

 printf("key for the first person is : %lld\n",power(b,x,n));
 printf("key for the second person is : %lld\n",power(a,y,n));
 return 0;
}

Reversing a Linked List using Recursion

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

struct Node
{
	int data;
	struct Node*next;
};
struct Node*head;
struct Node*makeNode(int data)
{
	struct Node*node;
	node=(struct Node*)malloc(sizeof(struct Node));
	node->data=data;
	node->next=NULL;
	return node;
}
struct Node*insert(struct Node*start,struct Node*newNode)
{
	struct Node*ptr;
	if(start==NULL)
		return newNode;
	for(ptr=start;ptr->next;ptr=ptr->next);
	ptr->next=newNode;
	return start;
}
void printList(struct Node*start)
{
	struct Node*ptr;
	for(ptr=start;ptr;ptr=ptr->next)
		printf("%d ",ptr->data);
	printf("\n");
}
struct Node* reverseWithReturn(struct Node*node)
{
	struct Node*temp;
	if(node==NULL)
		return NULL;
	if(node->next==NULL)
		return node;
	temp=reverseWithReturn(node->next);
	node->next->next=node;
	node->next=NULL;
	return temp;
}
void reverseWithoutReturn(struct Node*node)
{
	/**
		for this function we need to maintain a global head
		this global head will be the head of new reversed list.

		this function will update the variable head
		now the head variable will store the start of newly formed list.
	*/
	if(node==NULL)
		return;
	if(node->next==NULL)
	{
		head=node;
		return ;
	}
	reverseWithoutReturn(node->next);
	node->next->next=node;
	node->next=NULL;
}
void reversePrint(struct Node*node)
{
	if(node==NULL)
		return;
	reversePrint(node->next);
	printf("%d ",node->data);
}
int main()
{
	struct Node*start;
	start=NULL;
	start=insert(start,makeNode(5));
	start=insert(start,makeNode(6));
	start=insert(start,makeNode(5));
	start=insert(start,makeNode(3));
	start=insert(start,makeNode(51));
	start=insert(start,makeNode(9));
	start=insert(start,makeNode(78));

	printList(start);
	start=reverseWithReturn(start);
	printList(start);

	return 0;
}

Hill Cipher - Program in C

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int **matrixMultiply(int**a,int r1,int c1,int **b,int r2,int c2)
{
 int **resultMatrix;
 int i,j,k,r,c;
 r=r1;c=c2;
 resultMatrix=(int**)malloc(sizeof(int*)*r);
 for(i=0;i<r;i++)
  resultMatrix[i]=(int*)malloc(sizeof(int)*c);
 for(i=0;i<r;i++)
 {
  for(j=0;j<c;j++)
  {
   resultMatrix[i][j]=0;
   for(k=0;k<c1;k++)
    resultMatrix[i][j]+=a[i][k]*b[k][j];
  }
 }
 return resultMatrix;
}
void printMatrix(int**matrix,int r,int c)
{
 int i,j;
 for(i=0;i<r;i++)
 {
  for(j=0;j<c;j++)
   printf("%d ",matrix[i][j]);
  printf("\n");
 }
}
int plainTextToCipherText(char plainText[],int**matrix)
{
 int len,**plainTextMatrix,**resultMatrix,i,j;
 // The matrix will be of dimensions strlen(plainText) by strlen(plainText)
 char *cipherText;
 len=strlen(plainText);
 cipherText=(char*)malloc(sizeof(char)*1000);

 // plainTextMatrix should be of dimension strlen(plainText) by 1
 // allcating memory to plainTextMatrix
 plainTextMatrix=(int**)malloc(sizeof(int*)*len);
 for(i=0;i<len;i++)
  plainTextMatrix[i]=(int*)malloc(sizeof(int)*1);

 // populating the plainTextMatrix
 for(i=0;i<len;i++)
  for(j=0;j<1;j++)
   plainTextMatrix[i][j]=plainText[i]-'a';

 resultMatrix=matrixMultiply(matrix,len,len,plainTextMatrix,len,1);
 
 // taking mod 26 of each element of the result matrix
 for(i=0;i<len;i++)
  for(j=0;j<1;j++)
   resultMatrix[i][j]%=26;

 // Printing the cipher text
 printf("The cipher text is as follows : ");
 for(i=0;i<len;i++)
  for(j=0;j<1;j++)
   printf("%c",resultMatrix[i][j]+'a');
 printf("\n");
 //printMatrix(resultMatrix,len,1);
}
int main()
{
 int len,i,j,**matrix;
 char plainText[1000];
 printf("Enter the word to be encrypted : ");
 scanf(" %s",plainText);
 len=strlen(plainText);

 // allocating memory to matrix
 matrix=(int**)malloc(sizeof(int*)*len);
 for(i=0;i<len;i++)
  matrix[i]=(int*)malloc(sizeof(int)*len);

 printf("Enter the matrix of %d by %d to be used in encryption process : \n",len,len);
 for(i=0;i<len;i++)
  for(j=0;j<len;j++)
   scanf("%d",&matrix[i][j]);

 plainTextToCipherText(plainText,matrix);
 return 0;
}

Caesar Cipher - Program in C

#include<stdio.h>
#include<stdlib.h>
char*plainTextToCipherText(char plainText[],int n)
{
 char *cipherText;
 int i;
 cipherText=(char*)malloc(sizeof(char)*1000);
 for(i=0;plainText[i];i++)
 {
  if(plainText[i]!=' ')
   cipherText[i]=((plainText[i]-'a'+n)%26)+'a';
  else
   cipherText[i]=plainText[i];
 }
 cipherText[i]='\0';
 return cipherText;
}
char*cipherTextToPlainText(char cipherText[],int n)
{
 char *plainText,c;
 int i;
 plainText=(char*)malloc(sizeof(char)*1000);
 for(i=0;cipherText[i];i++)
 {
  if(cipherText[i]!=' ')
  {
   c=(cipherText[i]-'a'-n)%26;
   if(c<0)
    c+=26;
   c+='a';
   plainText[i]=c;
  }
  else
  {
   plainText[i]=cipherText[i];
  }
 }
 plainText[i]='\0';
 return plainText;
}
int main()
{
 int n;
 char plainText1[1000],*cipherText1,cipherText2[1000],*plainText2;

 // Encoding Cipher Text
 printf("Enter the Plain Text (in lower case): ");
 scanf(" %[^\n]s",plainText1);
 printf("Enter the number of characters to be shifted : ");
 scanf("%d",&n);
 cipherText1=plainTextToCipherText(plainText1,n);
 printf("Cipher Text is : %s\n",cipherText1);


 // Decoding Plain Text
 printf("\nEnter the Cipher Text (in lower case) : ");
 scanf(" %[^\n]s",cipherText2);
 printf("Enter the number of charaters to be shifted : ");
 scanf("%d",&n);
 plainText2=cipherTextToPlainText(cipherText2,n);
 printf("The Plain Text is : %s\n",plainText2);
 return 0;
}

Generic Representation of Graph - Generic List of Vertices and Edges

LinkedList_Generic.h

struct LinkedList_Generic
{
 struct ListNode_Generic*start;
 int elementSize;
 /*
  elementSize, will store the size of each element. 
  The element size is important, because generics in C are limited to void pointers, 
  in order to let the compiler know the amount of memory needed by malloc/memcpy. 
  This information should always be supplied dynamically. The caller should use sizeof(int) rather than 4.
 */
};
struct ListNode_Generic
{
 void *data;
 struct ListNode_Generic*next;
};
struct LinkedList_Generic *makeAndInitialiseLinkedList();
struct ListNode_Generic *makeAndInitialiseListNode(struct LinkedList_Generic *list,void*element);
void addElement(struct LinkedList_Generic*list,struct ListNode_Generic*element);
void removeElement(struct LinkedList_Generic*list,struct ListNode_Generic*node);
struct ListNode_Generic*getNodeReferenceWithGivenData(struct LinkedList_Generic*list,void*data);

LinkedList_Generic.c

#include<stdlib.h>
#include<string.h>
#include"LinkedList_Generic.h"

struct LinkedList_Generic *makeAndInitialiseLinkedList(int elementSize)
{
 struct LinkedList_Generic *list;
 list=(struct LinkedList_Generic*)malloc(sizeof(struct LinkedList_Generic));
 list->start=NULL;
 list->elementSize=elementSize;
 return list;
}
struct ListNode_Generic *makeAndInitialiseListNode(struct LinkedList_Generic *list,void*element)
{
 struct ListNode_Generic*listNode;
 listNode=(struct ListNode_Generic*)malloc(sizeof(struct ListNode_Generic));
 listNode->data=element;
 //listNode->data=malloc(sizeof(list->elementSize));
 //memcpy(listNode->data,element,list->elementSize);
 listNode->next=NULL;
 return listNode;
}
void addElement(struct LinkedList_Generic*list,struct ListNode_Generic*element)
{
 struct ListNode_Generic*ptr,*prev;
 if((list->start)==NULL)
  (list->start)=element;
 else
 {
  for(ptr=(list->start);ptr;prev=ptr,ptr=ptr->next);
  (prev->next)=element;
 }
}
void removeElement(struct LinkedList_Generic*list,struct ListNode_Generic*node)
{
 struct ListNode_Generic*ptr,*prev;
 for(ptr=(list->start),prev=NULL;ptr && (ptr)!=node;prev=ptr,ptr=ptr->next);
 if(ptr)
 {
  if(prev!=NULL)
  {
   prev->next=ptr->next;
   if(ptr)
   {
    free(ptr);
   }
  }
  else if(prev==NULL && ptr!=NULL) // means the element that we need to delete is the start of the list.
  {
   prev=list->start;
   (list->start)=((list->start)->next);
   if(prev)
   {
    free(prev);
   }
  }
 }
}
struct ListNode_Generic*getNodeReferenceWithGivenData(struct LinkedList_Generic*list,void*data)
{
 struct ListNode_Generic*node;
 for(node=list->start;node;node=node->next)
 {
  if((node->data)==data)
   return node;
 }
}

Graph_Generic.h

struct Graph_Generic
{
 struct LinkedList_Generic *vertexList,*edgeList;
 int numberOfVertices, numberOfEdges;
};
struct Vertex
{
 int id;
 int inDegree,outDegree;
};
struct Edge
{
 int id,sourceVertex,destinationVertex,isDirected,weight;
};
struct Graph_Generic*makeAndInitialiseGraph();
void addVertex(struct Graph_Generic*graph,struct Vertex*vertex);
void removeVertex(struct Graph_Generic*graph,int vertexNumber);
void addEdge(struct Graph_Generic*graph,struct Edge*edge);
void removeEdge(struct Graph_Generic *graph,int ,int ,int);
struct Edge *makeEdge(int sourceVertex,int destinationVertex,int weight,int isDirected);
struct Vertex *makeVertex();
void printGraph_Generic(struct Graph_Generic*grpah);

Graph_Generic.c

#include"Graph_Generic.h"
#include"LinkedList_Generic.h"
#include<stdlib.h>
#include<stdio.h>
struct Graph_Generic*makeAndInitialiseGraph()
{
 struct Graph_Generic*graph;
 graph=(struct Graph_Generic*)malloc(sizeof(struct Graph_Generic));
 graph->numberOfVertices=0;
 graph->numberOfEdges=0;
 graph->vertexList=makeAndInitialiseLinkedList(sizeof(struct Vertex));
 graph->edgeList=makeAndInitialiseLinkedList(sizeof(struct Edge));
 return graph;
}
struct Edge *makeEdge(int sourceVertex,int destinationVertex,int weight,int isDirected)
{
 static int edgeNumber=0;
 struct Edge*edge;
 edge=(struct Edge*)malloc(sizeof(struct Edge));
 edge->sourceVertex=sourceVertex;
 edge->destinationVertex=destinationVertex; 
 edge->weight=weight;
 edge->isDirected=isDirected;
 edge->id=edgeNumber++;
 return edge;
}
struct Vertex *makeVertex()
{
 static int vertexNumber=0;
 struct Vertex*vertex;
 vertex=(struct Vertex*)malloc(sizeof(struct Vertex));
 (vertex->id)=vertexNumber++;
 return vertex;
}

void addVertex(struct Graph_Generic*graph,struct Vertex*vertex)
{
 (graph->numberOfVertices)++;
 addElement(graph->vertexList,makeAndInitialiseListNode(graph->vertexList,vertex));
}
void removeVertex(struct Graph_Generic*graph,int vertexNumber)
{
 struct Edge*e;
 struct ListNode_Generic*ptr,*ptr1;
 (graph->numberOfVertices)--;
 for(ptr=graph->vertexList->start;ptr;ptr=ptr->next)
 {
  if(((struct Vertex*)(ptr->data))->id==vertexNumber)
   break;
 }
 if(ptr)
 {
  /*
   when you will be deleting an vertex then all the edges from and to that vertex should be deleted.
  */
  for(ptr1=graph->edgeList->start;ptr1;ptr1=ptr1->next)
  {
   e=(struct Edge*)(ptr1->data);
   if(e->sourceVertex==vertexNumber || e->destinationVertex==vertexNumber)
    removeEdge(graph,e->sourceVertex,e->destinationVertex,e->weight);
  }
  removeElement(graph->vertexList,ptr);
 }
}
void addEdge(struct Graph_Generic*graph,struct Edge*edge)
{
 (graph->numberOfEdges)++;
 addElement(graph->edgeList,makeAndInitialiseListNode(graph->edgeList,edge));
}
void removeEdge(struct Graph_Generic *graph,int sourceVertex,int destinationVertex,int weight)
{
 struct ListNode_Generic*ptr;
 (graph->numberOfEdges)--;
 for(ptr=(graph->edgeList->start);ptr;ptr=ptr->next)
 {
  if(
   ((struct Edge*)(ptr->data))->sourceVertex==sourceVertex &&
   ((struct Edge*)(ptr->data))->destinationVertex==destinationVertex &&
   ((struct Edge*)(ptr->data))->weight==weight
  ) break;
 }
 if(ptr)
  removeElement(graph->edgeList,ptr);
}
void printGraph_Generic(struct Graph_Generic*graph)
{
 int i;
 struct ListNode_Generic*ptr;
 printf("\nPrinting the vertex List : \n");
 printf("\nTotal Number Of Vertices in the Graph : %d\n",graph->numberOfVertices);
 for(ptr=(struct ListNode_Generic*)((graph->vertexList)->start);ptr;ptr=ptr->next)
  printf("%d ",((struct Vertex*)(ptr->data))->id);
 printf("\nTotal Number Of Edges in the Graph : %d\n",graph->numberOfEdges);
 for(ptr=(struct ListNode_Generic*)((graph->edgeList)->start);ptr;ptr=ptr->next)
  printf("Edge No. : %d, from %d to %d with weight=%d and isDirected?=%d\n",((struct Edge*)(ptr->data))->id,((struct Edge*)(ptr->data))->sourceVertex,((struct Edge*)(ptr->data))->destinationVertex,((struct Edge*)(ptr->data))->weight,((struct Edge*)(ptr->data))->isDirected);
}

main.c

#include<stdio.h>
#include"Graph_Generic.h"
int main()
{
 struct Graph_Generic*graph;
 int a,b,weight,isDirected,i,numberOfVertices,numberOfEdges,sourceVertex,destinationVertex,vertexNumber;

 printf("Enter the number of Vertices in the Graph : ");
 scanf("%d",&(numberOfVertices));
 printf("Enter the number of Edges in the Graph : ");
 scanf("%d",&(numberOfEdges));

 graph=makeAndInitialiseGraph();

 for(i=0;i<numberOfVertices;i++)
  addVertex(graph,makeVertex());

 printf("NOTE 1 : The ordering of the Vertices and Edges is zero indexed.\n");
 printf("NOTE 2 : For each edge enter the following in Sequence : \n");
 printf("\t1. Source Vertex Number.\n");
 printf("\t2. Destination Vertex Number.\n");
 printf("\t3. Weight associated with Edge.\n");
 printf("\t4. 1 if the Edge is Directed, and 0 otherwise.\n");
 
 for(i=0;i<numberOfEdges;i++)
 {
  printf("Enter the edge Number %d : ",i+1);
  scanf("%d%d%d%d",&a,&b,&weight,&isDirected);
  addEdge(graph,makeEdge(a,b,weight,isDirected));
 }
 printGraph_Generic(graph);
 
 printf("\nDeleting an Edge : \n");
 printf("Enter the sourceVertex, destinationVertex and weight of the graph : ");
 scanf("%d%d%d",&sourceVertex,&destinationVertex,&weight);
 removeEdge(graph,sourceVertex,destinationVertex,weight);
 
 printf("Deleting a Vertex : \n");
 printf("Enter the Vertex number to be deleted : ");
 scanf("%d",&vertexNumber);
 removeVertex(graph,vertexNumber);
 
 printGraph_Generic(graph);
 
 printf("Program Execution Successful...\n");
 return 0;
}

Makefile

all: LinkedList_Generic.o Graph_Generic.o main.o
 gcc LinkedList_Generic.o Graph_Generic.o main.o -o hello
LinkedList_Generic.o: LinkedList_Generic.c
 gcc -c LinkedList_Generic.c
Graph_Generic.o: Graph_Generic.c
 gcc -c Graph_Generic.c
main.o: main.c
 gcc -c main.c
clean:
 rm -rf *.o *~ hello

SampleInputData.txt

6
9
1 0 1 1
1 3 1 1
1 2 1 1 
0 5 1 1
0 4 1 1
2 3 1 1
2 4 1 1
2 5 1 1
4 3 1 1
2 5 1
0