Hash Functions and Encoding and Decoding of Integer in Crypto++

/*
	This program shows encoding of an integer into a byte array
	and again decoding the byte array into integer.

	This encoding and decoding is basically used when we need to give a byte array to SHA256 or SHA512
*/

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <cryptopp/integer.h>
using CryptoPP::Integer;

#include <cryptopp/sha.h>
using CryptoPP::SHA512;


Integer hashOfInteger(const Integer &a) // {0,1}* -> Zp*
{
	cout<<"Finding hash of "<<a<<endl;
	// using SHA512 here
	int byteCount=a.BitCount()/8;
	if(a.BitCount()%8!=0)
		byteCount++;
	byte byteArray[byteCount];	
	byte digest[SHA512::DIGESTSIZE];
	a.Encode(byteArray,byteCount);
	
	// now byte array contains bytes corresponding to the Integer a

	SHA512().CalculateDigest(digest,byteArray,byteCount);

	Integer result;
	result.Decode(digest,SHA512::DIGESTSIZE);
	return result;
}

int main()
{

	int n;
	cin>>n;
	cout<<"result  = "<<hashOfInteger(Integer::Power2(n))<<endl;
	return 0;
}

Scalar Multiplication in Elliptic curve in Crypto++

#include<bits/stdc++.h>
using std::cout;
using std::endl;

#include <cryptopp/ecp.h>
#include <cryptopp/asn.h>
#include <cryptopp/integer.h>
using CryptoPP::Integer;

#include <cryptopp/eccrypto.h>
using CryptoPP::ECP;    // Prime field
using CryptoPP::ECPPoint;
using CryptoPP::DL_GroupParameters_EC;

#include <cryptopp/asn.h>
#include <cryptopp/oids.h>
namespace ASN1 = CryptoPP::ASN1;

int main()
{
	DL_GroupParameters_EC<ECP> groupParameter = ASN1::secp160r1();

	
	cout << "Modulus: "<< groupParameter.GetCurve().GetField().GetModulus() << endl;
	cout << "Cofactor: "<< groupParameter.GetCofactor() << endl;
		    
	cout << "Coefficients" << endl;
	cout << "  A: "<< groupParameter.GetCurve().GetA() << endl;
	cout << "  B: "<< groupParameter.GetCurve().GetB() << endl;
	
	ECP curve=groupParameter.GetCurve();
	
	Integer y = groupParameter.GetSubgroupGenerator().x;
	Integer x = groupParameter.GetSubgroupGenerator().y;
	
	ECPPoint P=ECPPoint(x,y);
	cout<<"P = "<<P.x<<" , "<<P.y<<endl;

	ECPPoint R = curve.ScalarMultiply(P,Integer(2));

	cout<<"R = "<<R.x<<" , "<<R.y<<endl;

	return 0;
}

Basic Elliptic Curve Parameters in Crypto++

#include<bits/stdc++.h>
using std::cout;
using std::endl;

#include <cryptopp/ecp.h>
#include <cryptopp/asn.h>
#include <cryptopp/integer.h>
using CryptoPP::Integer;

#include <cryptopp/eccrypto.h>
using CryptoPP::ECP;    // Prime field
using CryptoPP::ECPPoint;
using CryptoPP::DL_GroupParameters_EC;

#include <cryptopp/asn.h>
#include <cryptopp/oids.h>
namespace ASN1 = CryptoPP::ASN1;

int main()
{
	DL_GroupParameters_EC<ECP> groupParameter = ASN1::secp160r1();

	
	cout << "Modulus: "<< groupParameter.GetCurve().GetField().GetModulus() << endl;
	cout << "Cofactor: "<< groupParameter.GetCofactor() << endl;
		    
	cout << "Coefficients" << endl;
	cout << "  A: "<< groupParameter.GetCurve().GetA() << endl;
	cout << "  B: "<< groupParameter.GetCurve().GetB() << endl;
	
	ECP curve=groupParameter.GetCurve();
	
	Integer y = groupParameter.GetSubgroupGenerator().x;
	Integer x = groupParameter.GetSubgroupGenerator().y;
	
	ECPPoint P=ECPPoint(x,y);
	cout<<"P = "<<P.x<<" , "<<P.y<<endl;

        return 0;
}

Random number Generation in Crypto++

#include<iostream>
using std::cout;
using std::endl;

#include<cryptopp/integer.h>
using CryptoPP::Integer;

#include<cryptopp/osrng.h>
using CryptoPP::AutoSeededRandomPool;

int main()
{
	// Illustration of generating a random number using AutoSeededRandomPool
	AutoSeededRandomPool rng;
	cout<<Integer(rng,Integer(400),Integer(500))<<endl;
	return 0;
}

Basics about Integer class in Crypto++

// refer this documentation - https://www.cryptopp.com/docs/ref/class_integer.html
// http://www.cryptopp.com/docs/ref561/class_integer.html
#include<iostream>
#include<cryptopp/integer.h>
using CryptoPP::Integer;
using std::cout;
using std::endl;

int main()
{
	// example showing calculation of 2^x for really big x
	cout<<"2**30000 = "<<Integer::Power2(30000)<<endl; // Power2 is a static member function of class. 
	

	// addition, subtraction, multiplication, division of two big numbers
	Integer i1=Integer::Power2(100); 
	Integer i2=Integer::Power2(50);

	cout<<"2**100 + 2**50 = "<<i1+i2<<endl;
	cout<<"2**100 - 2**50 = "<<i1-i2<<endl;
	cout<<"2**100 * 2**50 = "<<i1*i2<<endl;
	cout<<"2**100 / 2**50 = "<<i1/i2<<endl;
	
	// example showing use of modular operator
	Integer i3=Integer::Power2(1024);
	Integer i4(501);

	cout<<"2**1024 % 501 = "<<i3%i4<<endl;

	// example showing calculation of modular inverse
	Integer i5(3628800);
	Integer i6(2431);
	cout<<"modular inverse of 3628800 wrt 2431 = "<<i5.InverseMod(i6)<<endl;
	
	// example showing GCD of two numbers
	cout<<"GCD("<<i5<<","<<i6<<") = "<<Integer::Gcd(i5,i6)<<endl;

	Integer a,b,c;
	a=Integer(10241024);
	b=Integer(10241024);
	c=Integer(1000000007);

	// modular Multiplication 
	cout<<a_times_b_mod_c(a,b,c)<<endl;
	// modular Exponentiation
	cout<<a_exp_b_mod_c(a,b,c)<<endl;


	return 0;
}

Integer XOR in Crypto++

#include<iostream>
#include<algorithm>
using std::cout;
using std::cin;
using std::endl;

#include<cryptopp/integer.h>
using CryptoPP::Integer;


Integer XOR(Integer &a,Integer &b)
{
	Integer result=0;
	if(a>b)
	{
		for(int i=a.BitCount()-1;i>=b.BitCount();i--)
			result=result*2 + a.GetBit(i);
		for(int i=b.BitCount()-1;i>=0;i--)
			result=result*2 + (a.GetBit(i) ^ b.GetBit(i));
	}
	else
	{
		for(int i=b.BitCount()-1;i>=a.BitCount();i--)
			result=result*2 + b.GetBit(i);
		for(int i=a.BitCount()-1;i>=0;i--)
			result=result*2 + (a.GetBit(i) ^ b.GetBit(i));
	}

	return result;
}
void printBits(Integer &a)
{	
	for(int i=a.BitCount()-1;i>=0;i--)
		cout<<a.GetBit(i);
	cout<<endl;
}
int main()
{
	int x,y;
	cin>>x>>y;
	Integer a(Integer::Power2(x));
	Integer b(Integer::Power2(y));

	cout<<XOR(a,b)<<endl;
	return 0;
}

Printing the same character n number of times in Vim

Many times you need to type the same character many times and for that you need to long press that character and this wastes time. Well, there is a smarter way to do this in Vim.

Suppose you need to type _(underscore) 50 times.

So to do this, go in command mode by pressing Esc key and type the following:
50i_<Esc>

The moment you press <Esc>, the one undersocre that appears on the screen will be repeated 50 times, and now you can see 50 underscores on the screen one after the other.

Running python code from Vim and replacing the code with output

It is possible to write python code in vim and then execute the code. The output of the code will be placed in place of the python code. Let me illustrate you an example so that it becomes more clear.

Example:
Suppose that you have a string "Lavish" and you want to put each character of this string into a new line. We can write python code to do this.

for i in "Lavish":
    print i

Now select the above two lines by going in visal mode and then execute the following commmand:
:'<,'>!python

This will replace the python code with following lines:
L
a
v
i
s
h

Now, you may not see the real difference when the string is small, but as the string goes bigger, the power of vim becomes more visible.

Similarly, as an another example, say you want to print the following thing in a text file

1 Lavish
2 Lavish
3 Lavish
4 Lavish
5 Lavish

I'm sure, you must have figured it out that the python code for this will be:

for i in range(1,6):
    print str(i)+" Lavish"

and then follow the same thing again as described above. Similarly to the above mentioned examples, there is a lot of cool stuff that you can try out and make yourself more productive and efficient.

I hope this was interesting and you learned something from this. :)

Automatic Indentation of Code in Vim

Indentation is very important as it increases the readability of the codea and is considered to be a good programming practice. But a lot of times you may have to get some code that is not indented, and it is really irritating to mannualy indent each line. Vim provides a very eays way to indent your code just with unbelievably few keystrokies.

gg=G

is will indent your code from beginning of the file till the end of the file. Note that here gg means go to the starting of the file and = means to indent and G is for the end of the file. Puting it together we can read it as "indent the code from first line till the last line."

Similarly, to order to indent the current line, just place your cursor anywhere in that line and press
==
This will indent the current line.

Moving to the matching paranthesis in Vim

A lot of times while programming, we need to move to the matching paranthesis/braces. Place your cursor under one of the paranthesis in normal mode and press % the cursor will move to the corresponding matching paranthesis, bracket or brace what so ever it is. This is an efficient way of moving around functions in programming languages.

Saving and Quiting in Vim (shortcut Method)

Normal way to save and quit a file in vim is using :wq in vim. This is used by most of the user, but this involves three different keystrokes. But there is another way to do this saving and quiting. Just press ZZ in the normal mode and the file will be written and then vim will exit. I personally think that this is more efficient because it involves only one keystroke and it does all the things. Hope you also find this way of saving and quiting easier.

Pattern making - Spirograph - Javascript - using array of rods

In the previous post we saw how to create two rods and make them rotate relative to each other, with each rod having different speed and different length. In this post we will extend the previous code so as to make more than two rods rotate relative to the previous rod, and we will also trace the trajectory of end point of the last rod as done in previous post.

The following is the code:

HTML Code

<html>
 <title>Rakshit</title>
 <script type="text/javascript" src="a.js"></script>
 <body>
  <canvas id="mycanvas" width="500" height="500"></canvas>
  <canvas id="desingcanvas" width="500" height="500"></canvas>
  <button id="stopButton">Stop</button>
  <button id="resumeButton">Resume</button>
  <button id="restartButton">Restart</button>

 </body>

</html>

Javascript Code

/*
    Taking array of rods.
*/

var width=0;
var height=0;
var interval;

var rods=[];
var drawing=false; // a global variable that keeps track of whether we are drawing or not.

window.onload = function(){
    var cns = document.getElementById("mycanvas");

    width = cns.width;
    height = cns.height;
    var designContext =  document.getElementById("desingcanvas").getContext("2d");
    var context = cns.getContext("2d");
    rod1=Rod.create(250,250,100,0,10.0,"#0000FF");
    rod2=Rod.create(rod1.endx,rod1.endy,70,Math.PI,60.0,"#FF0000");
    rod3=Rod.create(rod2.endx,rod2.endy,50,Math.PI,30.0,"#00FF00");
    rod4=Rod.create(rod3.endx,rod3.endy,20,Math.PI,10.0,"#0F00F0");

    rods.push(rod1);
    rods.push(rod2);
    rods.push(rod3);
    rods.push(rod4);

    interval = setInterval(function(){draw(context,designContext);},1);

    var stopButton = document.getElementById("stopButton");
    stopButton.addEventListener("click",stopButtonClicked,false);
    var resumeButton = document.getElementById("resumeButton");
    resumeButton.addEventListener("click",resumeButtonClicked,false);
    var restartButton = document.getElementById("restartButton");
    restartButton.addEventListener("click",restartButtonClicked,false);

};

function stopButtonClicked()
{
    if(drawing)
    {
        clearInterval(interval);
        drawing=false;
    }
}
function resumeButtonClicked()
{
    if(drawing===false)
    {
        var context = document.getElementById("mycanvas").getContext("2d");
        var designContext =  document.getElementById("desingcanvas").getContext("2d");
        interval = setInterval(function(){draw(context,designContext);},1);
    }
}
function restartButtonClicked()
{
    if(drawing===true)
        clearInterval(interval);
    var canvas1 = document.getElementById("mycanvas");
    var canvas2 = document.getElementById("desingcanvas");
    var context = canvas1.getContext("2d");
    var designContext =  canvas2.getContext("2d");

    context.clearRect(0,0,canvas1.width,canvas1.height);
    designContext.clearRect(0,0,canvas2.width,canvas2.height);

    interval = setInterval(function(){draw(context,designContext);},1);
}

var Rod={
    startx:0,
    starty:0,
    endx:0,
    endy:0,
    length:0,
    angle:0,
    speed:100,
    color:"#000000",
    create:function(startx,starty,length,angle,speed,color)
    {
        var obj=Object.create(this);
        obj.startx=startx;
        obj.starty=starty;
        obj.length=length;
        obj.angle=angle;
        obj.speed=speed/500.0;

        obj.color=color;

        obj.endx=startx+length*Math.cos(angle);
        obj.endy=starty+length*Math.sin(angle);
        return obj;
    },

    update:function(startx,starty)
    {
        this.startx=startx;
        this.starty=starty;
        this.angle+=this.speed;
        if(this.angle>2*Math.PI)
            this.angle=0;
        this.endx=this.startx+this.length*Math.cos(this.angle);
        this.endy=this.starty+this.length*Math.sin(this.angle);
    },

    drawRod:function(context)
    {
        context.strokeStyle = this.color;
        context.lineWidth = 2;
        context.beginPath();
        context.moveTo(this.startx,this.starty);
        context.lineTo(this.endx,this.endy);
        context.stroke();
        context.closePath();
    }

};


function draw(context,designContext)
{
    var n=rods.length; // n is the number of rods.
    drawing=true;
    designContext.strokeStyle="#FF0000";
    designContext.lineWidth=0.25;
    designContext.beginPath();
    designContext.moveTo(rods[n-1].endx,rods[n-1].endy);

    context.clearRect(0,0,width,height);

    for(var i=0;i<n;i++)
    {
        if(i===0)
        {
            rods[i].drawRod(context);
            rods[i].update(rods[i].startx,rods[i].starty);
        }
        else {
            rods[i].drawRod(context);
            rods[i].update(rods[i-1].endx,rods[i-1].endy);
        }
    }

    designContext.lineTo(rods[n-1].endx,rods[n-1].endy);
    designContext.stroke();
    designContext.closePath();
}

The following animation is the illustration of the above mentioned code. You can try changing the length and speed of each rod and generate some really amazing patterns. You can also try adding more rods, or removing some of the rods so as to get something interesting.



Please feel free to comment if have any problem, or if you find any other thing that is interesting in this context. Also feel free to point any mistakes in the code.

Pattern Making - Spirograph - JavaScript

This post contains an illustration of making a spirograph using HTML5 and Javascript. Note that down there, we have three small buttons for you to play with the animation. The concept used here is that I have two rods/arms attached back to back and I'm plotting the trajectory of end-point of the last rod. See the below animation to get a clear idea.



Note that the code mentioned above is not easily extendable but the coming posts in this series will show how you can create an array of rods, and loop over all the rods to track the path traced by the end point of the last rod.
You can always right click and go to view page source to view the code behind construction of the above spirograph, but for the sake of simplicity and cutting off all the dirty code, here is the clean code used to make the above spirograph.
HTML Code

<html>
<title>Rakshit</title>
<script type="text/javascript" src="a.js"></script>
<body>
    <canvas id="mycanvas" width="500" height="500"></canvas>
    <canvas id="desingcanvas" width="500" height="500"></canvas>
    <button id="stopButton">Stop</button>
    <button id="resumeButton">Resume</button>
    <button id="restartButton">Restart</button>

</body>

</html>

Javascript Code

/*
    This program adds two rotating rods, representing robotic arm

    This is a simple program that just adds 2 rods
    and gives the trajectory of the end point of the second rod
*/
var width=0;
var height=0;
var interval;
var rod1,rod2;
var drawing=false; // a global variable that keeps track of whether we are drawing or not.
window.onload = function(){
    var cns = document.getElementById("mycanvas");

    width = cns.width;
    height = cns.height;
    var context = cns.getContext("2d");
    var designContext =  document.getElementById("desingcanvas").getContext("2d");
    rod1=Rod.create(250,250,80,0,10.0,"#0000FF");
    rod2=Rod.create(rod1.endx,rod1.endy,130,Math.PI,80.0,"#FF0000");

    interval = setInterval(function(){draw(context,designContext);},1);

    var stopButton = document.getElementById("stopButton");
    stopButton.addEventListener("click",stopButtonClicked,false);
    var resumeButton = document.getElementById("resumeButton");
    resumeButton.addEventListener("click",resumeButtonClicked,false);
    var restartButton = document.getElementById("restartButton");
    restartButton.addEventListener("click",restartButtonClicked,false);

};

function stopButtonClicked()
{
    if(drawing)
    {
        clearInterval(interval);
        drawing=false;
    }
}
function resumeButtonClicked()
{
    if(drawing===false)
    {
        var context = document.getElementById("mycanvas").getContext("2d");
        var designContext =  document.getElementById("desingcanvas").getContext("2d");
        interval = setInterval(function(){draw(context,designContext,rod1,rod2);},1);
    }
}
function restartButtonClicked()
{
    if(drawing===true)
        clearInterval(interval);
    var canvas1 = document.getElementById("mycanvas");
    var canvas2 = document.getElementById("desingcanvas");
    var context = canvas1.getContext("2d");
    var designContext =  canvas2.getContext("2d");

    context.clearRect(0,0,canvas1.width,canvas1.height);
    designContext.clearRect(0,0,canvas2.width,canvas2.height);

    interval = setInterval(function(){draw(context,designContext,rod1,rod2);},1);
}

var Rod={
    startx:0,
    starty:0,
    endx:0,
    endy:0,
    length:0,
    angle:0,
    speed:100,
    color:"#000000",
    create:function(startx,starty,length,angle,speed,color)
    {
        var obj=Object.create(this);
        obj.startx=startx;
        obj.starty=starty;
        obj.length=length;
        obj.angle=angle;
        obj.speed=speed/500.0;

        obj.color=color;

        obj.endx=startx+length*Math.cos(angle);
        obj.endy=starty+length*Math.sin(angle);
        return obj;
    },

    update:function(startx,starty)
    {
        this.startx=startx;
        this.starty=starty;
        this.angle+=this.speed;
        if(this.angle>2*Math.PI)
            this.angle=0;
        this.endx=this.startx+this.length*Math.cos(this.angle);
        this.endy=this.starty+this.length*Math.sin(this.angle);
    },

    drawRod:function(context)
    {
        context.strokeStyle = this.color;
        context.lineWidth = 2;
        context.beginPath();
        context.moveTo(this.startx,this.starty);
        context.lineTo(this.endx,this.endy);
        context.stroke();
        context.closePath();
    }

};


function draw(context,designContext)
{
    drawing=true;
    designContext.strokeStyle="#FF0000";
    designContext.lineWidth=0.25;
    designContext.beginPath();
    designContext.moveTo(rod2.endx,rod2.endy);

    context.clearRect(0,0,width,height);

    rod1.drawRod(context);
    rod1.update(rod1.startx,rod1.starty);
    rod2.drawRod(context);
    rod2.update(rod1.endx,rod1.endy);

    designContext.lineTo(rod2.endx,rod2.endy);
    designContext.stroke();
    designContext.closePath();
}

Please bear with me as I am new to javascript and comment if you have any new idea or find anything wrong in this post.

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