I have written a solution to the classic 3 water jug problem as follows :
I get the error during runtime after I input the values of the Water Jug Capacities. i've tried to find the segmentation fault using gdb a.out. It turns out to be on line I marked with the hashtags. I still don't seem to understand what the problem is as I have made sure to prevent all syntax errors on and near that line.
#include <iostream>
#include <string>
#include <algorithm>
#include <array>
#include <vector>
using namespace std;
vector <vector<int>> memory; // will contain all the posible states in the DFS
vector <int> stepCount;
vector <int> indexCount;
vector<int> maxVol;
void print_Steps_Taken(int previousSteps)
{
cout << "[ ";
for(int i=0; i<previousSteps; ++i)
{
for(int j=0; j<3; ++j)
{
cout << memory[i][j] << ", ";
}
cout << "]";
}
}
bool TransferWater(vector<int> maxVol, vector<int> &jugState, int targetVol, int currentStep, int previousSteps, int _l)
{
int newMemoryState = 1;
int position = _l;
for(int i=0; i<3; ++i)
{
if(maxVol[i] == targetVol)
{
cout << "State achieved in 1 step." ;
return true;
}
}
for(int i=0; i<3; ++i)
{
int tempJugState[3] = {0, 0, 0};
for(int j=0; j<3; j++)
{
if(i != j) // comparing Different Jugs
{
if(jugState[i] != 0) // check if "POURING_JUG" is not empty
{
if(jugState[j] < maxVol[j]) // check if "RECEIVING_JUG" is not empty
{
if(jugState[i] + jugState[j] <= maxVol[j]) // No OVERFLOW in "RECEIVING_JUG"
{
tempJugState[i] = 0;
tempJugState[j] = jugState[i] + jugState[j];
}
else // if excess water is present in "POURING_JUG"
{
tempJugState[i] = jugState[i] - (maxVol[j] - jugState[j]);
tempJugState[j] = maxVol[j];
}
int k = 3 - i - j; // access the "IDLE_JUG"
tempJugState[k] = jugState[k];
/*
int t[] = {i, j, k};
sort(t, t+3);*/
vector <int> checkState;
checkState.push_back(tempJugState[0]);
checkState.push_back(tempJugState[1]);
checkState.push_back(tempJugState[2]);
// Storing states of all three jugs in a vector
int flag = 0;
for(int c=0; c<memory.size(); ++c)
{
if(memory[c] == checkState) flag = 1;
}
if(flag == 0) // if the "CURRENT_STATE" is new.
{
memory.push_back(checkState);
stepCount.push_back(currentStep+1);
indexCount.push_back(previousSteps + position);
position = position + 1;
newMemoryState = 0;
}
if (tempJugState[0] == targetVol || tempJugState[1] == targetVol || tempJugState[2] == targetVol)
{
cout << "Jug volume of " << targetVol << " achieved in " << (currentStep + 1) << " steps";
print_Steps_Taken(previousSteps + position);
return true;
}
}
}
}
}
}
for(int i=0; i<3; ++i)
{
for(int j=0; j<3; ++j)
{
if(i != j)
{
if(jugState[i] != 0)
{
if(jugState[j] != 0 || jugState[3-i-j] != 0)
{
vector <int> checkState;
checkState[i] = 0;
checkState[j] = jugState[j];
checkState[3-i-j] = jugState[3-i-j];
int flag = 0;
for(int c=0; c<memory.size(); ++c)
{
if(memory[c] == checkState) flag = 1;
}
if(flag == 0) // if the "CURRENT_STATE" is new.
{
memory.push_back(checkState);
stepCount.push_back(currentStep+1);
indexCount.push_back(previousSteps + position);
position = position + 1;
newMemoryState = 0;
}
}
}
}
}
}
for(int i=0; i<3; ++i)
{
int tempJugState[3] = {0, 0, 0};
for(int j=0; j<3; ++j)
{
if(i != j)
{
if(jugState[i] != maxVol[i])
{
if((jugState[j] != maxVol[j]) || (jugState[3-i-j] != maxVol[3-i-j]))
{
vector<int> check;
// ####### check[i] = maxVol[i];
check[j] = jugState[j];
check[3-i-j] = jugState[3-i-j];
int flag = 0;
for(int c=0; c<memory.size(); ++c)
{
if(memory[c] == check) flag = 1;
}
if(flag == 0) // if the "CURRENT_STATE" is new.
{
memory.push_back(check);
stepCount.push_back(currentStep+1);
indexCount.push_back(previousSteps + position);
position = position + 1;
newMemoryState = 1;
}
}
}
}
}
}
/*
if (newMemoryState = 1 ) //&& (find(memory, memory.size(), jugState) - memory) == memory.size() - 1)
{
cout << "State cannot be achieved";
return true;
} */
return false;
}
void initialize_states(vector<vector<int>> &memory, vector<int> &maxVol)
{
memory.push_back({maxVol[0], 0, 0}); stepCount.push_back(1);
memory.push_back({0, maxVol[1], 0}); stepCount.push_back(1);
memory.push_back({0, 0, maxVol[2]}); stepCount.push_back(1);
memory.push_back({maxVol[0], maxVol[1], 0}); stepCount.push_back(2);
memory.push_back({maxVol[0], 0, maxVol[2]}); stepCount.push_back(2);
memory.push_back({0, maxVol[1], maxVol[2]}); stepCount.push_back(2);
}
int main()
{
int A, B, C, targetVol;
//vector<int> maxVol;
cout << "Enter the Capacity of A :- " ; cin >> A;
cout << "Enter the Capacity of B :- " ; cin >> B;
cout << "Enter the Capacity of C :- " ; cin >> C;
cout << "Enter the Target Volume :- " ; cin >> targetVol;
maxVol.push_back(A);
maxVol.push_back(B);
maxVol.push_back(C);
sort(maxVol.begin(), maxVol.end(), greater<int>());
// arranging the JUGS in descending order
initialize_states(memory, maxVol);
for(int i=0; i<6; ++i) { indexCount.push_back(i); }
int z = 0;
vector<int> jugState;
for (int i=0; i<memory.size(); ++i)
{
for(int j=0; j<memory[i].size(); ++j)
{
jugState.push_back(memory[i][j]);
}
int currentStep = stepCount[z];
int previousSteps = indexCount[z];
int _l = memory.size();
bool result = TransferWater(maxVol, jugState, targetVol, currentStep, previousSteps, _l);
z = z + 1;
if (result == true) // if given solution is reached.
break; // exit program
}
return 0;
}
Aucun commentaire:
Enregistrer un commentaire