﻿ Sample Code

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