Water Jars
//-------------------------------------------------------------
// Water Jars
//
// There are three water jars with capacities of 3, 5, and
// 8 gallons. There are no markings of any kind on the jars
// to indicate the amount of water in the jar. Initially, the
// 8-gallon jar is full and the other two are empty. This
// program determines a sequence of transfers that will result
// in exactly 4 gallons in each of the two larger jars. A
// transfer consists of pouring the contents of one jar into
// another until the first jar is empty or the second jar is
// full.
//
// D. Searls
// Apr 2000
// Asbury College
//-------------------------------------------------------------
# include <iostream>
# include <iomanip>
# include <fstream>
using namespace std;
const int MAXSIZE = 100;
struct Tstate {
int jar[3]; // Jar contents
};
const Tstate CAPACITY = {{8,5,3}}; // The maximum capacity of each of the three jars
const Tstate GOAL = {{4,4,0}}; // The goal state
struct Tstate_list {
int num; // Number of recorded states in the sequence of states
int src[MAXSIZE]; // Source jar leading to corresponding state
int dst[MAXSIZE]; // Destination jar in corresponding state
Tstate state[MAXSIZE]; // Current sequence of states (where each state consists
// of the number of gallons in each jar)
};
// In this program it makes sense to define the following variables as globals.
// We could pass each of these as an in/out parameter to our recursive function
// but it would only make the routine less efficient; both in regard to speed
// and in regard to memory usage.
ofstream outfile; // The output file
Tstate_list history; // Basically, the list of states in the current path
int numSolutions; // The number of solutions
//---------------------------------------------------------
// Equality for Tstate variables
//
// Return true if the corresponding jars in the Tstate
// structures j1 and j2 have the same contents.
//
// In Parameters: j1, j2
//---------------------------------------------------------
bool operator == (const Tstate& j1, const Tstate& j2)
{
return (j1.jar[0] == j2.jar[0] && j1.jar[1] == j2.jar[1] && j1.jar[2] == j2.jar[2]);
}
//---------------------------------------------------------
// duplicateState
//
// This function determines whether the contents of the
// jars matches the contents of the jars at some earlier
// point in the current history. If so, this function
// returns true. Otherwise, this function returns false.
//
// In parameter: contents
//
// Global Access: history
//---------------------------------------------------------
bool duplicateState(const Tstate& contents)
{
bool isDuplicate = false;
int i = 0;
while (i < history.num && !isDuplicate)
{
isDuplicate = (history.state[i] == contents);
i++;
}
return isDuplicate;
}
//---------------------------------------------------------
// writeHistory
//
// Write the current history to the output file. Typically,
// this routine is invoked when a solution has been found.
//
// Global Access: history, outfile, numSolutions
//---------------------------------------------------------
void writeHistory()
{
outfile << "SOLUTION " << numSolutions << endl << endl;
for (int i = 0; i < history.num; i++)
{
if (i == 0)
{
outfile << " Initial State:";
}
else
{
outfile << "Pour jar " << history.src[i]+1
<< " into jar " << history.dst[i]+1 << ':';
}
outfile << setw(4) << history.state[i].jar[0]
<< setw(4) << history.state[i].jar[1]
<< setw(4) << history.state[i].jar[2]
<< endl;
}
outfile << endl;
outfile << "Number of transfers: " << history.num-1 << endl;
outfile << " Number of states: " << history.num << endl << endl;
}
//---------------------------------------------------------
// transfer
//
// This routine pours the contents of the source jar into
// the destination jar. If that results in a state that has
// already been encountered in the current sequence of
// states, then the routine terminates. If this new state
// is the goal state then this routine will write the
// current solution by writing the sequence of states
// that led to the desired goal state. Otherwise, from this
// new state, an attempt is made to pour the contents of
// each jar into each of the other two jars to see if that
// leads to a solution. This routine is an example of a
// depth-first search algorithm. However, instead of
// quitting after finding the first solution, it goes on to
// find every solution.
//
// In parameters: contents, src, dst
//
// Global Access: outfile, history, numSolutions
//---------------------------------------------------------
void transfer(Tstate contents, int src, int dst)
{
// Pour contents of src jar into dst jar
if (CAPACITY.jar[dst]-contents.jar[dst] > contents.jar[src])
{
contents.jar[dst] = contents.jar[dst]+contents.jar[src];
contents.jar[src] = 0;
}
else
{
contents.jar[src] = contents.jar[src] - (CAPACITY.jar[dst]-contents.jar[dst]);
contents.jar[dst] = CAPACITY.jar[dst];
}
// If this is not a duplicate then proceed
if (!duplicateState(contents))
{
// Add new state to history list
history.src[history.num] = src;
history.dst[history.num] = dst;
for (int i = 0; i < 3; i++)
{
history.state[history.num].jar[i] = contents.jar[i];
}
history.num++;
// If we have reached the termination condition, write the history
if (contents == GOAL)
{
numSolutions++;
writeHistory();
cout << "Solution " << numSolutions << endl;
}
// Otherwise, keep pouring
else
{
transfer(contents, 0, 1);
transfer(contents, 0, 2);
transfer(contents, 1, 0);
transfer(contents, 1, 2);
transfer(contents, 2, 0);
transfer(contents, 2, 1);
}
// We've tried every possible move from the current state so
// back up to the previous state.
history.num--;
}
}
//**************************************
// M A I N D R I V E R
//**************************************
int main()
{
Tstate contents = {{8, 0, 0}}; // Initial contents of the jars
history.num = 0;
numSolutions = 0;
outfile.open("output.txt");
if (!outfile.fail())
{
transfer(contents, 0, 0);
outfile.close();
cout << "Output can be found in \"output.txt\"\n\n";
}
else
{
cout << "Could not open output file!\n\n";
}
return 0;
}
