Concurrency in Java

Concurrent programming is currently the most talked about and the most important feature of java.
It was released with java 7 and will only work with a java7 compiler.
Concurrent programming includes threading or creating a thread pool and distributing our work among the threads to complete the work faster and use less cpu time.
This is very important because by using a single thread we may require about a day to get the output for this problem but with concurrency it takes about 1 second to get the output.

PROBLEM STATEMENT:

Randomly generate one million (x, y) points, where 0.0 <= x < 1.0 and 0.0 <= y 1.0, and x and y are of type double. Then find and print out the two closest points, along with the distance between them.

Do this as quickly as possible, and print out the time required in seconds, as a floating point number.

Use ForkJoin. If you have a dual-core or quad-core computer, this should make your program about 2x or 4x faster. If you don't, using ForkJoin will slow things down slightly--but use it anyway!

My code consist of 3 parts, it is always advisable to make different classes and then merge them together so that we dont have 1 code going upto thousands of lines, it makes debugging easier.

Pointset class:

This class creates an object of a point having 2 co-ordinates x and y.

This helps us in storing and creating more than a million objects of this kind.

package jointFork;

import java.util.Comparator;

/**
 * @author Arpit Jain
 * @version April 17,2012
 * This class creates the objects for the 2 coordinates of a point.
 *
 */
public class PointSet implements Comparable<PointSet>{

double x;
double y;

public PointSet(double x, double y) {
this.x = x;
this.y = y;
}

public double getX() {
return this.x;
}

public double getY() {
return this.y;
}

@Override
public String toString(){
String output = "x = " + this.x + ", y = " + this.y; //$NON-NLS-1$ //$NON-NLS-2$
return output;
}

@Override
public int compareTo(PointSet point1) {
return (int)(this.x - point1.x);
}
/**
* Creates duplicate of the same PointSet
*/
public PointSet clone(){
PointSet cloneSet = new PointSet(x, y);
return cloneSet;
}
/**
* This function is used within Array Sort.
* It sorts the array according to only x points.
*/
public static final Comparator<PointSet> PointSetComparatorX = new Comparator<PointSet>() {
@Override
public int compare(PointSet point1, PointSet point2) {
if (point1.x < point2.x) {
return -1;
}
if (point1.x > point2.x) {
return 1;
}
return 0;
}
};
/**
* This function is used within Array Sort.
* It sorts the array according to only y points.
*/
public static final Comparator<PointSet> PointSetComparatorY = new Comparator<PointSet>() {
@Override
public int compare(PointSet point1, PointSet point2) {
if (point1.y < point2.y) {
return -1;
}
if (point1.y > point2.y) {
return 1;
}
return 0;
}
};
}

forkjoin class:
This class only creates the fork pool and given threshold values and set the starting parameters.
Its only job is to take the seed from user, calculate the time and calculate the distance between 2 closest points it receives.


package jointFork;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;

/**
 *
 * @author Arpit Jain
 * @version April 17,2012
 *
 */
public class ForkJoinPoints {

public static ForkJoinPool forkPool = new ForkJoinPool();
private static Random rand;
static PointSet[] xSorted;
public static BufferedReader br;
static final int numberOfPoints = 1000000;

/**
* Takes the seed to generate random numbers as a user input
* Sort all the generated xSorted with respect to x coordinates
* Displays the time take (in secs) to find the closest xSorted
* @param args
*/
public static void main(String[] args) {

float time;

System.out.println("Enter the Seed value:");

br = new BufferedReader(new InputStreamReader(System.in));
String inputEntry = null;
try {
inputEntry = br.readLine();
}
catch(IOException ioe) {
System.out.println("IO error trying to read your entry!"); //$NON-NLS-1$
System.exit(1);
}
catch(NumberFormatException i) {
System.out.println("invalid entry "); //$NON-NLS-1$
System.exit(1);
}
int intValue = Integer.parseInt(inputEntry);
rand =  new Random(intValue);
int numbers = 0;
xSorted = new PointSet[numberOfPoints];


while(numbers < numberOfPoints) {
double Xvalue = rand.nextDouble();
double Yvalue = rand.nextDouble();
xSorted [numbers] = new PointSet(Xvalue,Yvalue);
numbers++;
}

long start_time = System.currentTimeMillis();

Arrays.sort(xSorted,PointSet.PointSetComparatorX);


PointSet[] pairs;

pairs = forkPool.invoke(new SplitWork(xSorted,0, numberOfPoints - 1));
// print value of closest xSorted
System.out.println("The Closest Pairs are : " );
System.out.println(pairs[0] + "\n" + pairs[1]);
double dist1 = distance(pairs[0],pairs[1]);
System.out.println("Distance between the 2 closest points is : " + dist1);
time = (System.currentTimeMillis() - start_time)/1000;
System.out.println("Time taken = " + time + " seconds");
}

public static double distance(PointSet p1, PointSet p2) {
double powerX = Math.pow(p1.x - p2.x, 2);
double powerY = Math.pow(p1.y - p2.y, 2);
double finalDistance = Math.sqrt(powerX + powerY);
return finalDistance;
}
}

split work class:

This class does all the calculation and creates objects of pointset class and uses shortest distance algorithm to find the value of the closest points. if we use brute force to find closest distance between a million points then it will take almost a day to calculate it. hence we dont make use of brute force.

package jointFork;

import java.util.Arrays;

import java.util.concurrent.RecursiveTask;

/**

 * @author Arpit Jain

 * @version April 17,2012

 * The class extends the Recursive task i.e every thread is

 * given its own set of work by the compute function and 

 * work is done by recursively calling the function.

 * 

 */

class SplitWork extends RecursiveTask<PointSet[]> {

private static final long serialVersionUID = 1L;

int startIndex;

int endIndex;

private static PointSet[] xSorted;

static final int thresholdValue = 5000;

/**

* This constructor is used by to get the values of the set containing the

* points and to get the start and the end index initially when it is called

* by the fork join pool.

* @param p - Array of objects(x & y coordinates)

* @param startIndex - initial index of the size of array i.e 0

* @param endIndex - last index of the array

*/

SplitWork(PointSet[]p,int startIndex, int endIndex) {

this.startIndex = startIndex;

this.endIndex = endIndex;

SplitWork.setxSorted(p);

}

/**

* This constructor is used to call recursively

* @param startIndex- current startIndex

* @param endIndex - current End index

*/

SplitWork(int startIndex, int endIndex) {

this.startIndex = startIndex;

this.endIndex = endIndex;

}

/**

*Compute function provides each thread with its set of work 

*/

public PointSet[] compute() {

return closestPoints(startIndex,endIndex);

}

/**

*  Calculating the distance between 2 points

* @param p1 -First point

* @param p2 - second point

* @return -distance between them

*/

public static double distance(PointSet p1, PointSet p2) {

double powerX = Math.pow(p1.x - p2.x, 2);

double powerY = Math.pow(p1.y - p2.y, 2);

double finalDistance = Math.sqrt(powerX + powerY);

return finalDistance;

}

/**

* This function computes the closest pairs of xSorted by dividing 

* the array of xSorted recursively

* @param startIndex - starting index of the array of xSorted

* @param endIndex - last index of the array of xSorted

* @return - the closest pairs of xSorted

* 

*/

static PointSet[] closestPoints(final int startIndex, final int endIndex) {

PointSet[]  pairs = new PointSet[2];

if(endIndex - startIndex == 0) {

return null;

}

else if(endIndex - startIndex == 1) {

pairs[0] = getxSorted()[startIndex];

pairs[1] = getxSorted()[endIndex];

return pairs;

}

// else if(endIndex- startIndex+1 == 3 ) {

//

// double minimumDistance= -1;

// for(int i = 0; i<3;i++) {

// for(int j = i+1;j<3;j++) {

// double dist = distance(xSorted[i],xSorted[j]);

// if(i == 0 && j == i+1) 

// minimumDistance = dist;

//

// if(minimumDistance > dist) {

// minimumDistance = dist;

// pairs[0] = xSorted[i];

// pairs[1] = xSorted[j];

// }

// }

// }

// return pairs;

// }

else if(endIndex - startIndex == 2) {

           int number = getClosestPoints(getxSorted()[startIndex],getxSorted()[startIndex+1],getxSorted()[endIndex]);

         if(number == 0) {

         return null;

         }

         else if(number == 1) {

          pairs[0] = getxSorted()[startIndex];

          pairs[1] = getxSorted()[startIndex + 1];

         }

         else if(number == 2) {

          pairs[0] = getxSorted()[startIndex+1];

          pairs[1] = getxSorted()[endIndex];

         }

         else if(number == 3) {

          pairs[0] = getxSorted()[startIndex];

  pairs[1] = getxSorted()[endIndex];

         }

           return pairs;

}

final int midIndex = (startIndex + endIndex) / 2;

int leftValue = midIndex - startIndex +1;

int rightValue = endIndex - midIndex;

PointSet[] leftSet = null;

PointSet[] rightSet = null;

SplitWork leftSide = null, rightSide = null;

if (leftValue < thresholdValue) {

leftSet = closestPoints(startIndex, midIndex);

} else {

leftSide = new SplitWork(startIndex, midIndex);

leftSide.fork();

}

if (rightValue < thresholdValue) {

rightSet = new PointSet[2];

rightSet = closestPoints(midIndex + 1, endIndex);

} else {

rightSide = new SplitWork(midIndex + 1, endIndex);

rightSide.fork();

}

if (leftSide != null) {

leftSet = leftSide.join();

}

if (rightSide != null) {

rightSet = rightSide.join();

}

//finding the minimum distance on left and right

double minLeft = distance(leftSet[0], leftSet[1]);

double minRight = distance(rightSet[0], rightSet[1]);

double minRL;

minRL = Math.min(minLeft, minRight);

if (minRL == minLeft) {

pairs[0] = leftSet[0];

pairs[1] = leftSet[1];

} else {

pairs[0] = rightSet[0];

pairs[1] = rightSet[1];

}

double minDist= minRL;

int leftMiddle= midIndex;

int rightMiddle = midIndex;

double middleX = getxSorted()[midIndex].x;

double middleLeftX = middleX - minRL;

double middleRightX = middleX + minRL;

while (leftMiddle> startIndex && getxSorted()[leftMiddle- 1].x > middleLeftX) {

leftMiddle--;

}

while (rightMiddle < endIndex && getxSorted()[rightMiddle + 1].x < middleRightX) {

rightMiddle++;

}

/*

*Array of elements which might have the shortest 

*distance but are divided by the midpoint.

*

*/

PointSet []Ystrip = new PointSet[rightMiddle - leftMiddle+ 1];

for (int index = 0; index < Ystrip.length; index++) {

Ystrip[index] = getxSorted()[index + leftMiddle].clone();

}

Arrays.sort(Ystrip,PointSet.PointSetComparatorY);

// Calculating the distance of all the xSorted in Ystrip with each other

for (int i = 0; i < Ystrip.length - 1; i++) {

for (int j = i+1; j < Ystrip.length && (Ystrip[j].getY() -  Ystrip[i].getY() < minRL); j++) {

double d = distance(Ystrip[i],Ystrip[j]);

if (d < minDist) {

minDist= d;

pairs[0] = Ystrip[i];

pairs[1] = Ystrip[j];

}

}

}

return pairs;

}

/**

* For the array of size 3 we calculate the smallest distance by using 

* brute force.

* @param p1- first point

* @param p2- second point

* @param p3- third point

* @return- the point whose distance is the shortest

*/

public static  int getClosestPoints(PointSet p1, PointSet p2, PointSet p3) {

       double distance1 = distance(p1,p2);

       double distance2  = distance(p2,p3);

       double distance3 = distance(p1,p3);

       if(distance1 <= distance2 && distance1 <= distance3) {

        return 1;

       }

       else if(distance2 <= distance1 && distance2 <= distance3) {

        return 2;

       }

       else if(distance3 <= distance1 && distance3<=distance2) {

        return 3;

       }

       return 0;

   }

public static PointSet[] getxSorted() {

return xSorted;

}

public static void setxSorted(PointSet[] xSorted) {

SplitWork.xSorted = xSorted;

}

}

Four in a Row game using C

This game is similar to the Connect 4 game, Here we make use of signals and pipes to communicate between M children and a parent and play the game of connect 4.
The child is Intelligent to an extent and will not make just random moves, whereas the parent will make random moves.Here 1 or B stand for child and 2 or R stands for the parent.
The size of the board is N which is currently fixed to be 5 but can be changed.
I have made use of two c files, 1 is the header and the other is the c file. The header file contains all of the headers and non calculating functions. Also i made this program in Linux, if you are building it on windows you might wanna include conio.h as the header file as well and use getch().
I will be putting up the code and some of its outputs as well

this is the header file called as header.h


#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>
#include <unistd.h>
#include <time.h>
#include <signal.h>
#define M 3 //number of players
#define N 5 //board size

int count = 0;
int isDone[M];
pid_t array[M];

union BoardGame{
int board[N][N];
pid_t childpid;
int hasCompleted;
int boardNumber;
int signal;
};
typedef union BoardGame game;


void initializeBoard(game *board,int id){
board-> hasCompleted = 0;
board -> boardNumber = id;
board -> signal = 0;
int i,j;
for(i = 0; i<N;i++){
for(j = 0;j<N;j++){
board-> board[i][j] = 0;
}
}
}

int isBoardEmpty(game *board){
int column;
for(column = 0; column < N ; column++){
if(board->board[0][column] == 0)
return 0;
}

printf(" Board %d is full ", board->boardNumber);
return 1;
}

int isValidMove(game *board, int column) {
if (board->board[0][column] == 0) {
return 1;
}

else
return 0;
}

void print(game *board){
int i = 0 ;
int j;
int k;
int row = 0;
for(k =0; k<N;k++)
printf(" -------");
printf("\n");
for(i= 0 ; i<3*N; i++){
for(j = 0;j<=N;j++){

if (i% 3 == 1 && j!=N){
printf("|");
if( board->board[i/3][j] == 1){
printf("   B ");
}
else if( board->board[i/3][j] == 2){
printf("   R ");
}
else if( board->board[i/3][j] == 0){
printf("   %d ", board->board[i/3][j]);
}
}
else
printf("| ");
}

printf("\n");
if(i%3==2){
for(k =0; k<N;k++)
printf(" -------");
printf("\n");
}
}
}

The main file :


#include "four_header.h"


int randomNumber(){
int x1 = rand()%N;
return x1;
}

int calculateChild1(int column, game *board){        //(game *board){{
int i;
//int column = rand()%N;
for(i = N-1;i >= 0;i--){
//        printf("i = %d\n",i);
if(board->board[i][column] == 0){
board->board[i][column] = 1;
return i;
}
}  
}


int columnCalculate(game *board){
int column;
again:
column = randomNumber();
if(isValidMove(board, column) == 1)
return column;
else
goto again;
}

int calculateRow(int column, game *board){  
int i;
//int column = rand()%N;
for(i = N-1;i >= 0;i--){
//        printf("i = %d\n",i);
if(board->board[i][column] == 0){
return i;
}
}  
}

int calculateChild(game *board){
int column,row;
// srand(time(NULL));
for(column = 0; column < N; column++) {

if(board->board[0][column] != 0) {

continue;
}
row = calculateRow(column,board);

if((row - 1) >= 0){
if(board->board[row - 1][column] == 1) {
return column;
}
}
//check left
if((column - 1) >= 0){
if(board->board[row][column - 1] == 1) {
return column;
}
}

if((column + 1) <= N -1) {
if(board->board[row][column + 1] == 1){
return column;
}
}


if(((column + 1) <= (N - 1)) && ((row - 1) >= 0)){
if( board->board[row - 1][column + 1] == 1)
return column;
}

if(((column - 1) > -1) && ((row - 1) > -1)){
if(board->board[row - 1][column - 1] == 1)
return column;
}

if(((column + 1) < N) && ((row + 1) < N)){
if(board->board[row + 1][column + 1] == 1)
return column;
}
}
while(1) {
column = columnCalculate(board);
return column;
}

}


int calculateParent(int column,game *board){
int i;
for(i = N-1;i >= 0;i--){
//        printf("i = %d\n",i);
if(board->board[i][column] == 0){
board -> board[i][column] = 2;
return i;
}
}
}



int check1(game *board){
int row[N], column[N], diagonal1[N], diagonal2[N];
int i,j;
for(i = 0;i<N;i++){
row[i] = 0;
column[i] = 0;
diagonal1[i] = 0;
diagonal2[i] = 0;
}
for(i = 0;i<N;i++){
for(j = 0; j<N;j++){
if(board -> board[i][j] == 1){

row[i] = row[i]+1;
//                printf("row check of %d = %d\n",i,row[i]);
//                printf("----------------------------\n");
}
else row[i] = 0;
if(board-> board[j][i]==1){
column[i] = column[i]+1;
//                printf("column check of %d = %d\n",i,column[i]);
//                printf("----------------------------\n");
}
else column[i] = 0;
if(board -> board[i+j][j] == 1){
diagonal1[i] = diagonal1[i] + 1;
//                printf("diagonal1 check of player 1 = %d\n",diagonal1[i]);
//                printf("----------------------------\n");
}
else diagonal1[i] = 0;  
if(board->board[i+j][N-1-j] == 1){
//                printf("diag2 = %d\n i+j = %d \n n-1-j = %d\n",board[i+j][N-1-j][no],i+j,((N-1)-j));
diagonal2[i] = diagonal2[i] + 1;
//                printf("diagonal2 check of player 1 = %d\n",diagonal2[i]);
//                printf("----------------------------\n");
}
else diagonal2[i] = 0;
//if(row[i] == 4 || column[i] == 4|| diagonal1[i] == 4||diagonal2[i]==4)
//    return 1;
if(row[i] == 4){
printf ("\nChild won on row\n");
sleep(2);
return 1;
}
else if(column[i] == 4){
printf ("\nChild won on column\n");
sleep(2);
return 1;
}
else if(diagonal1[i] == 4){
printf ("\nChild won on diagonal\n");
sleep(2);
return 1;
}
else if(diagonal2[i] == 4){
printf ("\nChild won on anti-diagonal\n");
sleep(2);
return 1;
}
}
}  
return 0;
}

int check2(game *board){
int row[N], column[N], diagonal1[N], diagonal2[N];
int i,j;
for(i = 0;i<N;i++){
row[i] = 0;
column[i] = 0;
diagonal1[i] = 0;
diagonal2[i] = 0;
}
for(i = 0;i<N;i++){
for(j = 0; j<N;j++){
if(board -> board[i][j] == 2){

row[i] = row[i]+1;
//                printf("row check of %d = %d\n",i,row[i]);
//                printf("----------------------------\n");
}
else row[i] = 0;
if(board-> board[j][i] == 2){
column[i] = column[i]+1;
//                printf("column check of %d = %d\n",i,column[i]);
//                printf("----------------------------\n");
}
else column[i] = 0;
if(board -> board[i+j][j] == 2){
diagonal1[i] = diagonal1[i] + 1;
//                printf("diagonal1 check of player 1 = %d\n",diagonal1[i]);
//                printf("----------------------------\n");
}
else diagonal1[i] = 0;  
if(board->board[i+j][N-1-j] == 2){
//                printf("diag2 = %d\n i+j = %d \n n-1-j = %d\n",board[i+j][N-1-j][no],i+j,((N-1)-j));
diagonal2[i] = diagonal2[i] + 1;
//                printf("diagonal2 check of player 1 = %d\n",diagonal2[i]);
//                printf("----------------------------\n");
}
else diagonal2[i] = 0;
//if(row[i] == 4 || column[i] == 4|| diagonal1[i] == 4||diagonal2[i]==4)
//    return 1;
if(row[i] == 4){
printf ("\nParent won on row\n");
sleep(2);
return 1;
}
else if(column[i] == 4){
printf ("\nParent won on column\n");
sleep(2);
return 1;
}
else if(diagonal1[i] == 4){
printf ("\nParent won on diagonal\n");
sleep(2);
return 1;
}
else if(diagonal2[i] == 4){
printf ("\nParent won on anti-diagonal\n");
sleep(2);
return 1;
}
}
}  
return 0;
}


void boardCheck(int ){
count += 1;
if(count == M){
printf("Game over\n");
exit(0);
}
}
void quit(int parentPipe[2],int childPipe[2],game *board, int player){

if(player == 1){
kill(getppid(), SIGUSR1);
close(parentPipe[0]);
close(childPipe[1]);
close(parentPipe[1]);
close(childPipe[0]);
}
else if(player == 2){
close(parentPipe[1]);
close(childPipe[0]);
close(parentPipe[0]);
close(childPipe[1]);      
}
}
void playChildGame(int parentPipe[2],int childPipe[2],game *board, int boardNum){
int i,j;
int parentMove = 0;
int childMove = 0;
int childMove1 = 0;
int check = 0;
int columnChild;
initializeBoard(board, boardNum);
for(i = 0; i< N*N;i++){
if(isBoardEmpty(board) == 1){
check = getpid();
write(childPipe[1], &check,sizeof(int));
goto quit;

}

do{
read(parentPipe[0],&parentMove,sizeof(int));
check = -1;
write(childPipe[1],&check,sizeof(int));
}while(isValidMove(board,parentMove) == 0);
calculateParent(parentMove, board);
printf("--------------------------------------------------------------------------\n");
printf("Parent is making the move on %d on board # %d \n",parentMove, boardNum);
printf("--------------------------------------------------------------------------\n");
print(board);
sleep(2);

if(check2(board) == 1 || isBoardEmpty(board) == 1){
check = getpid();
write(childPipe[1], &check, sizeof(int));
goto quit;

}
else{
check = -1;
write(childPipe[1], &check, sizeof(int));
}

check = 0;
do{
check++;
columnChild = randomNumber();
}while(isValidMove(board, columnChild) == 0 );

childMove = calculateChild(board);
childMove1 = calculateChild1(childMove,board);
printf("--------------------------------------------------------------------------\n");
printf("Child is making the move on %d on board # %d \n",columnChild, boardNum);
printf("--------------------------------------------------------------------------\n");
print(board);
sleep(2);
if(check1(board) == 1 || isBoardEmpty(board) == 1){
check = getpid();
write(childPipe[1], &check, sizeof(int));
goto quit;

}
else{
check = -1;
write(childPipe[1], &check, sizeof(int));
}
}
goto quit;
quit:  
kill(getppid(), SIGUSR1);
close(parentPipe[0]);
close(childPipe[1]);
close(parentPipe[1]);
close(childPipe[0]);

}

int playParentGame(int parentPipe[2],int childPipe[2], int boardNum){
int childMove = 0;
int random = 0;
int parentMove;
while(1){
random = randomNumber();
srand(time(NULL) - random*6);
random = randomNumber();
write(parentPipe[1], &random , sizeof(int));
read(childPipe[0], &childMove, sizeof(int));
if( childMove != -1){
if(array[boardNum] == childMove){
goto quit;

}
}
}
quit:
close(parentPipe[1]);
close(childPipe[0]);
close(parentPipe[0]);
close(childPipe[1]);
return 1;
}

int main(int argc, char **argv){
game boardGame[M];
int i, j, boardNum, k;
int pipe1[M][2];
int pipe2[M][2];
int flag = 0;
int index = 0;
pid_t pid;
srand(time(0));
signal(SIGUSR1, boardCheck);
for (i  = 0; i < M; i++) {
initializeBoard(&boardGame[i],i);
isDone[i] = 0;
}

for(i = 0; i < M; i++) {
pipe(pipe1[i]);
pipe(pipe2[i]);
pid = fork();

if (pid == 0) { //CHILD

if (!flag) {
boardNum = i;
flag = 1;
}
i += M;

playChildGame(pipe1[boardNum],pipe2[boardNum], &boardGame[boardNum], boardNum);

}

else {  //PARENT

array[index] = pid;
index++;
if(index == M) {
for(j = 0; j < M; j++)  
playParentGame(pipe1[j],pipe2[j], j);
}        
}
}
return 0;
}  

some sample out put:

Introduction to C++

C,C++ are the basis for all the high level languages today!!!
C++ is an intermediate level language

Different levels of languages 

Low level languages are those languages which are closer to the hardware and can manipulate memory much more easily than high level languages.
example - assembly language

High Level Language are machine independent programming languages, they cannot manipulate the memory easily but they give a good and interactive foreground to the program.
example - java,python, perl

Intermediate language are those that have features from both the languages.
example - C,C++.

Let us start with C++

The first and the foremost important thing that we require is a compiler. A compiler is something that converts your code into machine language and makes it executable.
There are many compilers in the market but the one's that are pretty well known are Code::Blocks for windows and gedit for Linux or XCode for mac users.

Now, to start with the C++ coding, each line that we write in the editor is a command to the system to perform certain function.
This collection of commands makes a source code.
a command consists of keywords, variables and instructions.

Keywords are predefined words that the language uses and are not allowed to be used as variable names. for example - if, int, char, for, while - these are all keywords and these words have some significance in the library of the compiler and a user cannot use these names as  variable names.

Variables are locations in the memory of the computer created by the user where the user can store data and from where he can retrieve data.
a variable is always preceded by a data type. 

different data types -
int - to store a numeric or integer value
char - to store a letter
String - to store a sentence (not present in C)
float - to store a decimal value
boolean - store true or false(not present in C)
Double - to store large float values
long - to store large int values.

To perform certain inbuilt functions like printing value on the screen or to take values from user or do complex mathematical function like square and square roots there are inbuilt programs created in the library of C and before we write the simplest code it is mandatory to call a few of these library files.
The example below will show you how to call them

There are two parts to a program i.e Instructions and comments
Instructions are used to ask the program to perform a certain function.
anything and everything written on the editor is considered as an instruction until it is preceded by "// " or "/*".

 //line comment
/*block comment or multiline comment */

Comment is something that a programmer writes for future reference, so that when he reads the code sometime later he knows what a few statements mean and what do they do.

here is a simple example to start with

#include<iostream>
#include<string>   
using namespace std;

int main(){
    int a,b;      //This is a comment. Here a,b are variables, int is a data type
    int c (6);   // constructor initialization. here 6 is the initial value of c

    int d = 5;  //here initial value of d is 5
    int result;
    string new1,new2;
    string new3;
    new1 = " this is my first program";// initializing values to new1 and new2
    new2 = " this is my second string";
    cout<<"Please enter the first number"<<endl;
    cin>>a;
    cout<<"please enter the second number\n";
    cin>>b;
    cout<<"enter the new string"<<endl;
    cin>>new3;
    cout<<new3<<endl;
    result = a + b;
    cout<<"final result = "<<result<<"\n the value of c is = "<<c<<endl;
    return 0;
}

in the above code
#include<iostream> is a header file used to include predefined program to print out on the screen and take value from the user.
to print something on the screen we write
cout<<"Print on the screen";
 to take values from the user
cin>>variable name ;

#include<String> is used to as we are making use of String as a data type.

endl is used to go to the next line.

2 strings can be concatenated using "+" sign.

using namespace std - if we want to use cout and cin directly we need to specify this else we'll have to type as follows

std::cout<<
std::cin>>

i will explain you the significance of :: later. 

Tower of Hanoi

Code for Playing Towes of Hanoi-
A very Interesting game, which we generally played when we were kids or when we are with kids.
about the game - Tower of Hanoi
The code has been written in Python.


"""Code By Arpit Jain """

import random
import copy
import math

def int2baseTwo(x):
    """converts interger value to base of two and represents in binary"""
    binary = [] # make an empty list named bunary.
    while (x>0):
        value = x % 2  # Find the remainder on dividing by 2 as we need binary values.
        binary.append(value)  # append the binary value in the list
        x =  x//2  # Integer divide the number by 2.
    return binary
     
def randLocationR(n):
    """Creates a list of random numbers between 0 and 2 inclusive and we call it rollcall"""
    rollcall = [] # Create an empty list called roll call to return a list of random numbers between 0 and 2 inclusive.
    for i in range(0,n):
        tower = random.randint(0,2) # creates n random numbers between 0 and 2 inclusive.
        rollcall.append(tower) # adds the random number generated to the list.
    return rollcall

def rollcall2List(R):
    """converts the roll calls that we get in the above functions into a combined list of 3 lists of each tower and its elements"""
    tower1 = []     # creation of blank lists
    tower2 = []
    tower0 = []
    length = len(R)
    for i in range(0,length):   # loop to run form start to length of the list so that we can check for each and every elememt
        if(R[i]==0):
            tower0.append(i)  #if the  element is 0 then we add the value of i to tower zero similarly for the others.
            length -= 1
        if(R[i]==1):
            tower1.append(i)
            length -= 1
        if(R[i]==2):
            tower2.append(i)
            length -= 1
    tower0.sort()
    tower1.sort()
    tower2.sort()
    return [tower0,tower1,tower2]

def isLegalMove(L,a,b):
    """ this function returns a boolean value whether the move is legal or not i.e larger disc will not be allowed to go above smaller disc"""
    if(a == b):         #checks whether a and b are same if they are same then retuen false as we cannot move the disc from a post onto itself
        return False
    elif (len(L[a]) == 0):  # checks whether the length of the post a is zero or not i.e whether it has any any disc on it or not if it doesnt have any list then we can move nothing hence it should return false
        return False
    elif(len(L[b])==0): # checks for the length of the post B and returns true even if the post contains no element as it is the right condition.
        return True
    elif (L[b][0] > L[a][0]): # we movr from the post A to post B if B is zero which we checked above or if the top disc at B is larger than the disc we are moving from A else we return False
        return True
    else:
        return False

def makeMove(L,a,b):
    """Moves the disc from one tower to another if the move is legal"""
    legal = isLegalMove(L,a,b)  # calls the function isLegalMove to check if the move made is legal or not
    if (legal):
        L[b].append(L[a][0])  # if the move is legal then moves
        L[a].remove(L[a][0])  # removes the element from list a that has been transferred to tower b.
        L[b].sort() # sorts the list in tower b
        return L
    else:
        return False

def printList(L):
    """This function prints the hanaoi game in the format that we want"""
    List1 = [[],[],[]]
    length1 = len(L[0])# we find the lenght of the 3 lists inside L
    length2 = len(L[1])
    length3 = len(L[2])
    final = [length1,length2,length3]   # we add all the 3 values to a new list
    maximum = max(final)# find the maximum out of the 3

    for i in range(3):
         for j in range(maximum-len(L[i])):     # this function finds the difference between the length of the list inside L and the maximum value and appends that many number of spaces so that all the lists become of equal length.
             List1[i].append('')
         List1[i] = List1[i] + L[i]

    for i in range(maximum):
        print(str(List1[0][i]).rjust(6),str(List1[1][i]).rjust(6),str(List1[2][i]).rjust(6))# This function is used to print the list. rjust is used to give space between the two values that we have to print

    for i in range(25):
        print('-',end ='')# This loop is used to print the line. We make use of end to indicate that print on the same line until the loop is finished and end bu space.
    print('')
    print('1'.rjust(6),'2'.rjust(6),'3'.rjust(6))  

def list2Rollcall(L):
    """converts list into rollcall i.e checks each number and returns the tower on which it is placed"""
    rollcall = L[0]+L[1]+L[2]   # concatinating all the 3 lists with each other.
    rollcall.sort()     # Sorting the list and arranging it in ascending order.
    rollcall.reverse()  # reversing the order of the sorted list
    for i in range(0,len(rollcall)):  
        if(rollcall[i] in L[0]):  # we search for each element in the new list within the 3 lists and checks to which list does it belong.
           rollcall[i] = 0
        elif(rollcall[i] in L[1]):
           rollcall[i] = 1
        elif(rollcall[i] in L[2]):
           rollcall[i] = 2
    return rollcall

def rollcall2SA(R):
    """converts rollcall into sierpinski's address"""
    p =[]   # empty list which is used to assign numbers depending whether the len of the rollcall is even or odd.
    s = [] # represents sierpinski's address
    i = 0
    if(len(R)%2 == 1):     # checking if the list length is even or odd.
        p = [0,1,2]         # if odd
    else:
        p = [2,1,0]         # if even
    while(i<len(R)):                   # we run a loop uptil the length if the input i.e R
        if (R[i] == p[0]):      # we compare the value in R at ith position with the value in p at 0th position to check if they are same
            s.append(0)         # if they are same then we append zero in s otherwise we check the next conditions
            temp = p[1]         # now we need to swap the remaning 2 elements from the list P hence we make use of temp as a temporary variable.
            p[1] = p[2]         # we exchange the position of the elements in the list and store the new P
            p[2] = temp
            i = i+1
        elif (R[i] == p[1]):    # here we do the same as above and compare the 1st element of p with ith value of R
            s.append(1)
            temp = p[0]
            p[0] = p[2]
            p[2] = temp
            i = i+1
        elif (R[i] == p[2]):    # perform the same function as above.
            s.append(2)
            temp = p[1]
            p[1] = p[0]
            p[0] = temp
            i=i+1
    return s                    # return s

def SA2rollcall(SA):
    p = []   # empty list which is used to assign numbers depending whether the len of the rollcall is even or odd.
    R = [] # represents empty roll call list
    i = 0
    if(len(SA)%2 == 1):     # checking if the list length is even or odd.
        p = [0,1,2]
    else:
        p = [2,1,0]
    while(i<len(SA)):                
        if (SA[i] == p[0]): # we perform the same function as the function above only in this case we find the location in p which corresponds to the element in p and then return that location index
            R.append(0)
            temp = p[1]
            p[1] = p[2]
            p[2] = temp
            i = i+1
        elif (SA[i] == p[1]):
            R.append(1)
            temp = p[0]
            p[0] = p[2]
            p[2] = temp
            i = i+1
        elif (SA[i] == p[2]):
            R.append(2)
            temp = p[1]
            p[1] = p[0]
            p[0] = temp
            i=i+1

    return R

def SA2TA(SA):
    """converts Sierpinski's address to ternarty address"""
    TA = [0,0,0]    # intialize a new list to 3 elements with zero each as we need to give the output of 3 elements.
    n = len(SA)
    for i in range(0,n):
        if(SA[i] == 0): # if the ith element of the list SA is 0 then we use the formula - (0,1,1)x2^(n-1)
            TA[0] += 0*(2**(n-i-1)) # we have to add TA to itself as we need addition of the all the elemnts that get entered there.
            TA[1] += 1*(2**(n-i-1))
            TA[2] += 1*(2**(n-i-1))
         
        elif(SA[i] == 1):  # if the ith element of the list SA is 0 then we use the formula - (1,0,1)x2^(n-1)
            TA[0] += 1*(2**(n-i-1))
            TA[1] += 0*(2**(n-i-1))
            TA[2] += 1*(2**(n-i-1))

        elif(SA[i] == 2):# if the ith element of the list SA is 0 then we use the formula - (1,1,0)x2^(n-1)
            TA[0] += 1*(2**(n-i-1))
            TA[1] += 1*(2**(n-i-1))
            TA[2] += 0*(2**(n-i-1))
    return TA

def TA2SA(TA):
    """converts Ternary Address back into Sierpinski's Address"""
    total = TA[0]+TA[1]+TA[2]       # Total consist of addition of all the elements or values in the TA
    power = int2baseTwo(total)  # We send the total to the int2baseTwo function to find out power of 2 and then we subtract
    SA = []     # Empty SA list
    temp = TA   # Storing the TA in a new varibale called Temp
    mod = [0,0,0]   # we initialize the list for mod with 3 elements all zero's as we need to store the addition of the elements in this list hence it is initialzed to zero.
    i = 0
    for i in range(0,len(power)-1):
        if(i>0):
            temp[0] = temp[0]//2    # We do Integer division of the value in temp[0] by 2 and then in the next step we mod it by 2 and store the result in mod.
            temp[1] = temp[1]//2    # we do Integer division by 2 as we need to know how many 2's it has.
            temp[2] = temp[2]//2


        mod[0] = temp[0]%2
        mod[1] = temp[1]%2
        mod[2] = temp[2]%2

        if( mod == [0,1,1] ):   # now we have the value of mod. we check whether the current value if mod and append 0,1 or 2 accordingdly in the emplty list SA.
            SA.append(0)
        elif(mod == [1,0,1]):
            SA.append(1)
        elif(mod == [1,1,0]):
            SA.append(2)
    SA.reverse()
    return SA

def reduceTA(A,B):
    """ It takes in 2 ternary addresses and removes the large discs with the same value at the same position from both the SA's. But the large discs should be in a proper order.
    If 7 is the highest and is at the same location but 6 is at different locations and then again 5 is at the same location then we remove only 7 and not 5 because 6 is not in the same location."""

    SA= TA2SA(A)    #Converts the Ternary Address into sierpinski's
    SA1=[]
    SB = TA2SA(B)
    SB1=[]
    length1 = len(SA) #we find the length of the SA formed as we need the loop to run to this length.
    k = 0

    for i in range(0,length1):
        if(SA[i]==SB[i]):   #we compare the two values of SA and SB and if they are same then we change that value to "Equal" stating both are same
            SA[i]= 'Equal'
            SB[i]= 'Equal'
        elif(SA[i]!=SB[i]): # if the two are not at the same location then we break the loop as if the higher disc is not at the same location then we dont worry about the other discs.
            break
    while(k<length1): # Now we append the values which are not Equal into another lists SA1 and SB1. we only append the values which are not 'Equal'
        if (SA[k]!= 'Equal'):
            SA1.append(SA[k])
        if (SB[k]!= 'Equal'):
            SB1.append(SB[k])
        k = k+1

    TA1= SA2TA(SA1) # convert SA back into TA
    TB1= SA2TA(SB1)
    for i in range(0,3): # changing the original Array as we donot return anything explicitly.
       A[i] = TA1[i]
       B[i] = TB1[i]

def distTA(A_in,B_in):
    """This function is used to calculate the distance between two ternary address."""
    total = 0
    indexA = []
    indexB = []
    final = []
    Acopy = copy.deepcopy(A_in) # we make a deep copy of the first input. we make deep copy as we dont want the original list to change.
    Bcopy = copy.deepcopy(B_in)
    if(A_in == B_in):   # if the 2 inputs are the same then we retrn 0 as the distance between them.
        return 0
    else:
        reduceTA(Acopy,Bcopy)   # if the 2 inputs are not same then we find the reduced TA of the 2 inputs.

        minA = Acopy.index(min(Acopy))  # this function first finds the minimum value in Acopy and then finds the index of that value in Acopy and stores it in minA
        minB = Bcopy.index(min(Bcopy))# we find the index of the lost value so that we donot subtract the lowest valued index with 2^(n-1)

        for i in range(0,len(Acopy)): # we add all the elements in Acopy and then find its int2BaseTwo value as we need to find the number of times o appears in the loop.
            total +=Acopy[i]  
        total = (total+2)//2 # once we add all the values we divide it by 2 and then send that value to find the power.
        power = int2baseTwo(total)
        n = power.count(0)  # n stores the number of times 0 appears in power as that will be the value that we will use

        for i in range(0,len(Acopy)):
            if (i!=minA): # while the value of i is not minimun i.e while the index is not that of the lowest value subtract 2^(n-1) from all the values
                Acopy[i] = Acopy[i] - (2**(n-1))
                indexA.append(i)# we append the indexes that we have changed into a new list.

            if (i!=minB): # performs the same function as the above
                Bcopy[i] = Bcopy[i] - (2**(n-1))
                indexB.append(i)
             
        difference = 3-(minA+minB)  # now to find the 3rd point in the triangle we subtract the addition of the 2 min indexes with the 3. we use this value for option 2
        option1 = Acopy[minB] + 1 + Bcopy[minA] # for option 1 we add the values at index minB in A and minA in B and add '1' to to, this 1 is for the bridge.
        final.append(option1)   # we append this result into final list.

        option2 = Acopy[difference] + 2 + Bcopy[difference] + (2**(n-1))-1 # This is the longer route. we add the 2 values at index 'difference' and add the length of 1 side and 2 bridges.
        final.append(option2)

        required = min(final)# this gives the minimum of the 2.
     
        return required

def play():
    """This Function is used to call all the remaining functions and play the game"""
    value = 0
    print(" Welcome to the game of Tower of Hanoi")
    n = int(input("Enter the number of disc you would like to play with = ")) # input of the number of discs by the user.
    rollcall = randLocationR(n)# calling all the function from above. finding rollcall and SA and TA
    List = rollcall2List(rollcall)
    SA = rollcall2SA(rollcall)
    TA = SA2TA(SA)
    printList(List)
    print("Your Goal is to move everything to tower 3. (Q or q quits)")
    TA2 = (2**n)-1   # we know when we reach the final state the TA of the 2 positions are the same and its value is 2^(n-1)
    if(n%2!=0):   # but the position of the TA2 is not same for all the values its different for odd and even values of n.
        distance1 = distTA(TA,[TA2,TA2,0])# by this we calculate the miminum distance between the current position and the final state.
    elif(n%2==0):
        distance1 = distTA(TA,[0,TA2,TA2])
    print("Fastest Path is " ,distance1," moves")
    while(value != 1 or distance != 0): #loop to run the game until the user quits or finishes the game.
        stack1 = input("Take from stack")
        if (stack1 == '1'):  # user inputs values as 1,2 or 3 and we refer to them as 0,1,2 in our code hence we convert the input accordingly. i.e 1 to 0, 2 to 1, 3 to 2.
            stack1 = 0
        elif (stack1 == '2'):
            stack1 = 1
        elif (stack1 == '3'):
            stack1 = 2
        if(stack1 == 'q' or stack1 =='Q'):  # if user enters 'q' and 'Q' then the game quits.
            value = 1
            return "Quitter"
        stack2 = input("place on stack ")
        if (stack2 == '1'):
            stack2 = 0
        elif (stack2 == '2'):
            stack2 = 1
        elif (stack2 == '3'):
            stack2 = 2
        if(stack2 == 'q' or stack2 =='Q'):
            value = 1
            return "Quitter"
        else:
            check = isLegalMove(List,int(stack1),int(stack2))  #we check if the the move that user is doing is legal or not.
            if(check == True):  # if the isLegalMove true then we make move
                makeMove(List,int(stack1),int(stack2))
                rollcall2 = list2Rollcall(List) #now we convert the new list formed again into new TA and find its distance from the final state
                SA1 = rollcall2SA(rollcall2)
                TA1 = SA2TA(SA1)
                printList(List)
                if(n%2!=0):
                    distance2 = distTA(TA1,[TA2,TA2,0])
                elif(n%2==0):
                    distance2 = distTA(TA1,[0,TA2,TA2])
                print("Fastest Path is " ,distance2," moves")
                if(distance2!=0): # if the distance is not zero then we continue to play
                    value = 0
                    continue
                elif(distance2==0): # if distance is zero we stop playing
                    value =1
                    print("Puzzle Solved great work!!!")
                    break
            else:
                print("wrong Input") # if the move that user is trying to make is illegal we say the move is incorrect and ask him to press enter to continue playing or Q to quit.
                enter = input("Press enter to continue")
                if (enter == 'q' or enter == 'Q'):
                    value = 1
                    break
                else:
                    value = 0
                    continue