Tower of Hanoi Program in C++

This program asks user for number of discs first. say n= 2 or 3 or any number. Then it will ask user to enter one option out of two.

1 If the user wants the solution of the Tower of Hanoi for disc he has entered.

or

2 If the user wants to play by himself and shuffle the discs between the pegs A B and C

And user will play till he moves all the discs from peg A to peg C and the peg B is auxiliary peg. The game continues till all the disc from peg A (Starting peg) to move peg C (Final peg).

CODE :

// TOWER OF HANOI

#include <iostream.h>
class hanoi{
public:
 int s[50],top,elem,i,count,count1;
 hanoi(){
 top=-1;
 count1=0;
 }
 void push(int e){
 ++top;
 s[top]=e;
 ++count1;
 }
 int pop(){
 int e;
 if(top==-1){
 cout<<"\npeg is empty\n";
 return 0;
 }
 else{
 e=s[top];
 --top;
 --count1;
 return e; 
 }
 }
 void display(){
 if(top==-1)
 cout<<"| "<<endl;
 else{
 cout<<"| ";
 for(i=0;i<=top;i++)
 cout<<s[i]<<"-";
 cout<<endl;
 }
 }
 void store(int n){
 count=n;
 for(i=0;i<n;i++){
 push(count);
 --count;
 }
 count1=n;
 }
};
void tower(int n,char frm,char aux,char to){
 if(n==1){
 cout<<"\tmov disc 1 from "<<frm<<" to "<<to<<endl;
 return;
 }
 else{
 tower(n-1,frm,to,aux);
 cout<<"\tmov disc "<<n<<" from "<<frm<<" to "<<to<<endl;
 tower(n-1,aux,frm,to);
 }
}
int main(){
 int n,op;
 cout<<"\n\t~~~~~~~~~TOWER OF HANOI~~~~~~~~~\n";
 cout<<"\nEnter no.of disc= ";
 cin>>n;
start:
 cout<<"\nPress 1 for solution OR 2 for playing\n";
 cin>>op;
 if(op>2 || op<1)
 goto start;
 else if(op==1)
 tower(n,'A','B','C');
 else{
 char fp,tp;
 int disc;
 bool flag1,flag2,flag3;
 hanoi a,b,c;
 a.store(n);
 cout<<"\nstarting peg is A\tFinishing peg is C\n";
 cout<<"\nA";a.display();
 cout<<"\nB";b.display();
 cout<<"\nC";c.display();
 while (c.count1!=n){
mid:
 cout<<"\nmov disc from peg= ";
 cin>>fp;
 cout<<"\nmov disc to peg= ";
 cin>>tp;
 flag1=flag2=flag3=false;
 switch(fp){
 case 'A':{disc=a.pop();
 flag1=true;
 if(disc==0)
 goto mid;
 break;
 }
 case 'B':{disc=b.pop();
 flag2=true;
 if(disc==0)
 goto mid;
 break;
 }
 case 'C':{disc=c.pop();
 flag3=true;
 if(disc==0)
 goto mid;
 break;
 }
 }
 switch(tp){
 case 'A':{if(disc>a.s[a.top] && a.top>-1){
 cout<<"\nInvalid move\n";
 if(flag1==true)
 a.push(disc);
 else if(flag2==true)
 b.push(disc);
 else if(flag3==true)
 c.push(disc);
 }
 else{
 a.push(disc); }
 break;
 }
 case 'B':{if(disc>b.s[b.top] && b.top>-1){
 cout<<"\nInvalid move\n";
 if(flag1==true)
 a.push(disc);
 else if(flag2==true)
 b.push(disc);
 else if(flag3==true)
 c.push(disc);
 }
 else{
 b.push(disc); }
 break;
 }
 case 'C':{if(disc>c.s[c.top] && c.top>-1){
 cout<<"\nInvalid move\n";
 if(flag1==true)
 a.push(disc);
 else if(flag2==true)
 b.push(disc);
 else if(flag3==true)
 c.push(disc);
 }
 else{
 c.push(disc); }
 break;
 }
 }
 cout<<"\nA";a.display();
 cout<<"\nB";b.display();
 cout<<"\nC";c.display();
 }
 if(c.count1==n)
 cout<<"\n\t\t~~~~~YOU WON!!~~~~~\n";
 }
 return 0;
}

Tower of Hanoi Sample output 1

Tower of Hanoi Sample Output 2

C++ program for tic tac toe

Please Find the code for the following in Github : https://github.com/GarimaDamani/cpp_learnings/blob/master/tic_tac_toe.cpp

 

tic tac toe sample output 1

tic tac toe sample output 2

tic tac toe sample output 3

Java program for even and odd parity error detection

This program works for any length of input data.

it will ask user to enter data to be transmitted then ask to choose the odd or even parity. later after evaluating parity of the input data. it will display the data.

then ask user to enter the data that receiver receives but condition is it should be of same length as of the senders data length.

after this it will count the no.of ones in the data entered at receiver end. and according to no.of ones counted and the parity selected at the sender side. based on this will display a message saying if the data is received with error or not.

CODE :

package oddevenparity;
import java.io.*;
import java.util.*;
public class OddEvenParity {
String dataR=new String();
String dataS=new String();
int i,option,len;
int count1,count0;
void getDataSender()throws IOException{
System.out.println("--------------At Sender--------------");
System.out.println("Enter the Binary data:");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
dataS=br.readLine();
len=dataS.length();
for(i=0;i<dataS.length();i++){
if(dataS.charAt(i)!='1' && dataS.charAt(i)!='0'){
System.out.println("Enter only binary values");
return;
}
}
System.out.println("Even parity or Odd Parity?");
System.out.println("Enter 1 for even or 2 for odd");
Scanner s=new Scanner(System.in);
option=s.nextInt();
if(option==1){
System.out.println("Sender has agreed for Even parity");
even();
}
else{
System.out.println("Sender has agreed for odd parity");
odd();
}
System.out.println();
}
void even()throws IOException{
count1=count0=0;
for(i=0;i<dataS.length();i++){
if(dataS.charAt(i)=='1'){
count1++;
}
if(dataS.charAt(i)=='0'){
count0++;
}
}
if(count1%2==0){
dataS=dataS+'0';
System.out.println("Data after even parity:");
for(i=0;i<dataS.length();i++){
System.out.print(dataS.charAt(i));
}
}
else{
dataS=dataS+'1';
System.out.println("Data after even parity:");
for(i=0;i<dataS.length();i++){
System.out.print(dataS.charAt(i));
}
}
}
void odd()throws IOException{
count1=count0=0;
for(i=0;i<dataS.length();i++){
if(dataS.charAt(i)=='1'){
count1++;
}
if(dataS.charAt(i)=='0'){
count0++;
}
}
if(count1%2!=0){
dataS=dataS+'0';
System.out.println("Data after odd parity:");
for(i=0;i<dataS.length();i++){
System.out.print(dataS.charAt(i));
}
}
else{
dataS=dataS+'1';
System.out.println("Data after odd parity:");
for(i=0;i<dataS.length();i++){
System.out.print(dataS.charAt(i));
}
}
}
void getDataReciver()throws IOException{
System.out.println("\n\n--------------At Receiver--------------");
System.out.println("Enter the Binary data:");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
dataR=br.readLine();
len+=1;
if(len!=dataR.length()){
System.out.println("Enter the Binary data of length: "+len);
return;
}
for(i=0;i<dataR.length();i++){
if(dataR.charAt(i)!='1' && dataR.charAt(i)!='0'){
System.out.println("Enter only binary values");
return;
}
}
count1=count0=0;
for(i=0;i<dataR.length();i++){
if(dataR.charAt(i)=='1'){
count1++;
}
if(dataR.charAt(i)=='0'){
count0++;
}
}
if(option==1){
if(count1%2==0){
System.out.println("Data received successfully with no error");

}
else{
System.out.println("Error has been detected in received data");
}
}
else{
if(count1%2!=0){
System.out.println("Data received successfully with no error");
//System.out.println("Error has been detected in received data");
}
else{
System.out.println("Error has been detected in received data");
}
}
System.out.println();
}
public static void main(String[] args) throws IOException {
OddEvenParity p=new OddEvenParity();
p.getDataSender();
p.getDataReciver();
}
}

odd even parity Sample output 1

odd even parity sample output 2

odd even parity sample output 3

C++ Program for Elimination of Direct and Indirect Left Recursion

Below program is for Elimination of Direct and Indirect left recursion. this left indirect recursion works for two production only. the program prompts user asking no.of productions. and if the user says 1 this means its direct left recursion production and 2 means its a indirect left recursion production. the Sample output has been attached.

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

class rec{
public:
 char S[10], A[10];
 char left1, left2;

 int i = 0;
 bool flag1 = false;
 bool flag2 = false;
 bool flag3 = false;

 char beta[50], alpha[50];
 char temp1[50], temp2[50];

 int j = 0, k = 0;
 int q = 0, o = 0;

 void direct(char temp2[]){
 i = 0;
 int length = strlen(temp2);
 cout << "\nlen= " << length;
 char left = temp2[0];
 cout << "\nleft= " << left;
 j = 0, k = 0;

 for (i = 2; i < length; i++){
 if (temp2[i] == left){
 int c = i + 1;
 while (temp2[c] != '|' && temp2[c] != '\o'){
 alpha[j] = temp2[c];
 c++;
 j++;

 }
 alpha[j] = '|';
 j++;
 i = c;
 alpha[j] = '\o';
 flag1 = true;
 }
 else if (temp2[i] != left){
 int z = i;
 while (temp2[z] != '|' && temp2[z] != '\o'){
 beta[k] = temp2[z];
 z++;
 k++;

 }
 beta[k] = '|';
 k++;
 i = z;
 beta[k] = '\o';
 flag2 = true;
 }
 }

 cout << "\n----------\n";
 if (flag1 == true){
 cout << "\nalpha= ";
 for (i = 0; alpha[i] != '\o'; i++)
 cout << alpha[i] << " ";
 }
 if (flag2 == true){
 cout << "\nbeta= ";
 for (i = 0; beta[i] != '\o'; i++)
 cout << beta[i] << " ";
 }

 cout << "\n----------form\n";
 cout << "A= ";
 for (i = 0; beta[i] != '\o'; i++){
 if (beta[i] != '|')
 cout << beta[i];
 else
 cout << " A'|";
 }

 cout << "\n-----------\n";
 cout << "A'= ";
 for (i = 0; alpha[i] != '\o'; i++){
 while (alpha[i] != '|'){
 cout << alpha[i]; i++;
 }
 cout << " A'|";
 }
 cout << "^";
 cout << endl;
 }
} r;

int main(){

 cout << "Enter the no.of productions: ";
 int count;
 cin >> count;
 if (count>1){

 cout << "\nEnter production 1:\n";
 cin >> r.S;
 cout << "\nEnter production 2:\n";
 cin >> r.A;
 cout << "---------------------------------\n";
 cout << "\nEntered Production 1 is=\t" << r.S;
 cout << "\nEntered Production 2 is=\t" << r.A;

 int len1 = strlen(r.S);
 int len2 = strlen(r.A);
 cout << "\n---------------------------------\n";
 cout << "\nlen1= " << len1 << "\tlen2= " << len2;

 r.S[len1] = '\o';
 r.A[len2] = '\o';
 r.left1 = r.S[0];
 r.left2 = r.A[0];
 cout << "\nleft1= " << r.left1 << "\nleft2= " << r.left2;
 cout << "\n---------------------------------\n";

 r.temp2[r.q] = 'S'; r.q++;
 r.temp2[r.q] = '='; r.q++;

 for (int i = 2; i< len1; i++){
 if (r.S[i] == r.left2){
 r.flag3 = true;
 int h = i + 1;

 while (r.S[h] != '|' && r.S[h] != '\o'){
 r.temp1[r.o] = r.S[h];
 h++;
 r.o++;
 }
 for (int p = 2; p < len2; p++){
 while (r.A[p] != '|' && r.A[p] != '\o'){
 r.temp2[r.q] = r.A[p];
 r.q++;

 p++;
 }
 for (int g = 0; g<(strlen(r.temp1)); g++){
 r.temp2[r.q] = r.temp1[g];
 r.q++;
 }
 r.temp2[r.q] = '|';
 r.q++;
 }
 i = h;
 }
 else if (r.S[i] != r.left2){
 r.temp2[r.q] = r.S[i];
 r.q++;
 }
 }
 r.temp2[r.q] = '\o';
 cout << endl;

 int length = strlen(r.temp2);
 for (int i = 0; i <length; i++)
 cout << r.temp2[i];
 r.direct(r.temp2);
 }
 else{
 cout << "\nEnter production:\n";
 cin >> r.temp2;
 cout << "---------------------------------\n";
 cout << "\nEntered Production is=\t" << r.temp2;
 r.direct(r.temp2);
 }
 return 0;
}
    

OUTPUT :

Eliminate Direct left recursion Sample output 1

Eliminate Direct left recursion Sample output 2

Eliminate inDirect left recursion Sample output 1

Eliminate inDirect left recursion Sample output 2

C++ Program for Missionaries and Cannibals

This program will ask user to enter no.of missionaries and cannibals to be transported in the boat on other side of the river.

and if any time the no.of missionaries are less then the no.of cannibals on any side the user will lose the game.

and user will win only when he can successfully make all the missionaries and cannibals cross the river.

CODE :

 
// missionaries and cannibals
#include<iostream>
#include<iomanip>
using namespace std;
class game{
public:
int counto, i;
char left[6], right[6];
int m_num, c_num;
bool side;
int ml_count, cl_count;
int mr_count, cr_count;
game(){
counto = 1;
ml_count = cl_count = 3;
mr_count = cr_count = 0;
side = false;
for (i = 0; i<3; i++){
left[i] = 'M';
left[i + 3] = 'C';
right[i] = ' ';
right[i + 3] = ' ';
}
}
void get(){
start:
cout << "\nEnter no.of missionaries= ";
cin >> m_num;
cout << "\nEnter no.of cannibals= ";
cin >> c_num;
if (m_num>3 || c_num>3 || m_num<0 || c_num<0)
goto start;
else if ((m_num + c_num)>2 || (m_num + c_num == 0))
goto start;
}
void displaymc(){
cout << "\nleft side\tright side\n";
for (i = 0; i<3; i++)
cout << left[i] << " ";
cout << "\t\t";
for (i = 0; i<3; i++)
cout << right[i] << " ";
cout << endl;
for (i = 3; i<6; i++)
cout << left[i] << " ";
cout << "\t\t";
for (i = 3; i<6; i++)
cout << right[i] << " ";
cout << endl;
if (counto % 2 == 0){
side = true;
cout << "\nBoat on right side of river\n";
}
else{
side = false;
cout << "\nBoat on left side of river\n";
}
}
void boat_lr(){
for (i = 0; i<m_num; i++){
if (left[0] == 'M'){
left[0] = ' ';
right[0] = 'M';
ml_count -= 1;
mr_count += 1;
}
else if (left[1] == 'M'){
left[1] = ' ';
right[1] = 'M';
ml_count -= 1;
mr_count += 1;
}
else if (left[2] == 'M'){
left[2] = ' ';
right[2] = 'M';
ml_count -= 1;
mr_count += 1;
}
}
for (i = 0; i<c_num; i++){
if (left[3] == 'C'){
left[3] = ' ';
right[3] = 'C';
cl_count -= 1;
cr_count += 1;
}
else if (left[4] == 'C'){
left[4] = ' ';
right[4] = 'C';
cl_count -= 1;
cr_count += 1;
}
else if (left[5] == 'C'){
left[5] = ' ';
right[5] = 'C';
cl_count -= 1;
cr_count += 1;
}
}
}
void boat_rl(){
for (i = 0; i<m_num; i++){
if (right[0] == 'M'){
right[0] = ' ';
left[0] = 'M';
ml_count += 1;
mr_count -= 1;
}
else if (right[1] == 'M'){
right[1] = ' ';
left[1] = 'M';
ml_count += 1;
mr_count -= 1;
}
else if (right[2] == 'M'){
right[2] = ' ';
left[2] = 'M';
ml_count += 1;
mr_count -= 1;
}
}
for (i = 0; i<c_num; i++){
if (right[3] == 'C'){
right[3] = ' ';
left[3] = 'C';
cl_count += 1;
cr_count -= 1;
}
else if (right[4] == 'C'){
right[4] = ' ';
left[4] = 'C';
cl_count += 1;
cr_count -= 1;
}
else if (right[5] == 'C'){
right[5] = ' ';
left[5] = 'C';
cl_count += 1;
cr_count -= 1;
}
}
}
};
int main(){
game g;
while (true){
if (g.ml_count<g.cl_count && g.ml_count>0 || g.mr_count<g.cr_count && g.mr_count>0){
cout << "\n\n~~~~~~~~~~~~~~~~YOU LOST!!~~~~~~~~~~~~~~~~\n";
break;
}
else if (g.cr_count == g.mr_count && g.cr_count == 3 && g.mr_count == 3){
cout << "\n\n~~~~~~~~~~~~~~~~YOU WON!!~~~~~~~~~~~~~~~~\n";
break;
}
else{
g.displaymc();
g.get();
if (g.side == false)
g.boat_lr();
else
g.boat_rl();
}
g.counto++;
}
return 0;
}

Missionaries and Cannibals Sample output

Help Missionaries and Cannibals to cross the river

If you are into artificial intelligence or studying artificial intelligence then you must be familiar with one of the most famous “Missionaries and Cannibals problem.”

If you are thinking to write a program for this game. Then before you start with your program first you should be clear with the concept of this problem. So that its easy and very much clear for you, what are you trying to code and from where to start and what’s the goal state of this problem.

Let’s try to understand what the missionaries and cannibals problem is:

• On left bank of a river are three missionaries and three cannibals.

• There is one boat available that can hold up to two people and those they would like to use to cross the river.

• If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.

How can the boat be used to safely carry all the missionaries and cannibals across the river?

 

To solve this problem we will make the following assumptions:

1. Number of cannibals should lesser than the missionaries on either side.

2. Only one boat is available to travel.

3. Only one or maximum of two people can go in the boat at a time. Boat cannot go on other side of the river empty.

4. All the six have to cross the river from bank.

5. There is no restriction on the number of trips that can be made to reach of the goal.

6. Both the missionaries and cannibals can row the boat.

In order to solve this problem, we have to find logic in such a way that they all cross the river safely. That’s what our goal state is.

So let’s see now the solution to this problem:

 

In the above figure the red dots represents the cannibals where as black triangle represents the missionaries.

I hope you must have understood the logic behind this problem. So you can start your coding. And refer this above solution for coding.

I would suggest if you code this problem by your own. Give it a try for your better understanding.

If not then I hope I can help you out with it, till then Happy Coding!

Inline Functions in C++

One of the objectives of using functions in a program is to save some memory space, which becomes useful when function is likely to be called many times.

However, every time a function is called, it takes a lot of time in executing a series of instructions for tasks such as jumping to the function, saving registers, pushing arguments into the stack and returning to the calling function.

To eliminate the cost of calls to small function, C++ proposes a new feature called inline functions i.e. inline expansion is used to eliminate the time overhead (excess time) when a function is called.

An inline function is a function upon which the compiler has been requested to perform inline expansion. In other words an inline function is a function that is expanded in line when it is invoked.

This does not change the behavior of a function itself, but is used to suggest to the compiler that the code generated by the function body is inserted at each point the function is called.

The inline functions are defined as follows:

inline return_type function_name ( arguments,… )

{

Function body

}

Example:

inline double cube(double a)

{

return (a*a*a);

}

And the call is just like the call to any other function. All we need to do is to prefix the keyword inline to the function definition. We do not have to include the inline keyword when calling the function, only in its declaration. All inline functions must be defined before they are called.

• Which functions can we make as inline function?

The functions are made inline when they are small enough to be defined in one or two lines.

Remember:

The inline keyword merely sends a request, not a command, to the compiler, the may ignore this request if the function definition is too long or too complicated and compile the function as a normal function.

Some of the situations where inline expansion may not work:

• For functions returning values, if a loop, a switch, or a goto exists.
• For functions not returning values, if a return statement exists.
• If function contain static variables.
• If inline functions are recursive.

Inline functions makes a program run faster because the overhead of a function call and return is eliminated.

Example:

#include <iostream.h>

inline float mul (float x, float y){

return(x*y);

}

inline double div (double p, double q){

return(p/q);

}

void main(){

float a=12.345;

float b=9.82;

cout<<mul(a,b)<<“\n”;

cout<<div(a,b)<<“\n”;

}

Output

121.228

1.25713

Advantages: 

• It does not require function calling overhead.
• It also save overhead of variables push/pop on the stack, while function calling.
• It also save overhead of return call from a function.
• It increases locality of reference by utilizing instruction cache.

I hope you found this piece of information useful. looking forward for your feedback. Thank you.

Happy coding!!