In the movie “Die Hard 3”, Bruce Willis and Samuel L. Jacksonwere confronted with the following puzzle. They were given a3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallonjug with exactly 4 gallons. The solution they reached was to fillthe 5-gallon jug, pour the 5-gallon jug into the 3-gallon jug (thisleft 2 gallons in the 5-gallon jug), empty the 3-gallon jug, pourthe 5-gallon jug into the 3-gallon jug, fill the 5-gallon jug andthen fill the 3-gallon jug from the 5-gallon jug, empty the 3gallon jug, leaving 4 gallons in the 5 gallon jug.

Your assignment will be to generalize this problem in the followmanner.

You have two jugs, A and B, and an infinite supply of water.There are three types of actions that you can use each with acost:

you can fill jug A or B

you can empty jug A or B

you can pour from one jug to the other.

Pouring from one jug to the other stops when the first jug isempty or the second jug is full, whichever comes first. Forexample, if A has 5 gallons and B has 6 gallons and a capacity of8, then pouring from A to B leaves B full and 3 gallons in A.

A problem is given by (Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB,cpBA), where Ca and Cb are the capacities of the jugs A and B,respectively, and N is the goal. cfA is the cost to fill A, cfB isthe cost to fill B, ceA, is the cost to empty A, ceB is the cost toempty B, cpAB is the cost to pour A to B and cpBA is the cost topour B to A. A solution is a sequence of steps that leaves jug Aempty, and exactly N gallons in jug B. The possible steps are

fill A

fill B

empty A

empty B

pour A B

pour B A

success X

fill means to fill the jug from the infinite watersupply
empty means to discard the water in the jug
"pour A B" means "pour the contents of jug A into jugB"
"success X" means that the goal has been accomplished, jug Bcontains N gallons at a cost of X.

Program Specs

You MUST solve this problem bybuilding and traversing a graph, if you find a cute math formula tosolve the problem NO credit will begiven.

Write a Jug class that takes 9 parameters in the constructor.(Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA) Note: theorder IS important. Also checking forvalid input is something you should do.

Your Jug class must have a solve() member which will solve andthen store the steps for the CHEAPEST solution in a string.

class Jug {    public:        Jug(int,int,int,int,int,int,int,int,int);        ~Jug();        //solve is used to check input and find the solution if one exists        //returns -1 invalid inputs. solution set to empty string.        //returns 0 if inputs are valid but a solution does not exist. solution set to empty string.        //returns 1 if solution is found and stores solution steps in solution string.        int solve(string &solution);    private:        //anything else you need};

You may also find that you need an few helping structures to aidin the building of your graph. You may use queues, stacks, heaps,priority queues, trees or any other NONGRAPH structure you need. You make take these fromold homework, or the STL. Alsoyou MUST state in your comments at thetop of the Jug.h file that you are using them and give credit wherecredit is due.

Input

Input to your program consists of 9 ints defining one puzzle.Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA. Ca and Cb are thecapacities of jugs A and B, and N is the goal. the rest are thecosts for each action. You will want to verify the costs arepositive and 0 < Ca ? Cb and N ? Cb ? 1000. If the inputs areinvalid solve will return -1.

Solution

If a solution exists, the solve function should generate astring, that if output would look like the sample output below.This string will store the steps as a series of instructions, oneinstruction per line, from the list of the potential output lineswhich will result in jug A being empty and jug B containing exactlyN gallons of water. The last line for each puzzle should be theline "success X". (where X is the cost). There should be no emptylines nor any trailing spaces within this string. This string is"returned" via the reference parameter.

main.cpp

{   string solution;   Jug head(3, 5, 4, 1, 2, 3, 4, 5, 6);   if (head.solve(solution) != 1) {      cout << "Error 3" << endl;   }   cout << solution << endl << endl;}{   string solution;   Jug head( 3, 5, 4, 1, 1, 1, 1, 1, 2);            if(head.solve(solution) != 1) {      cout << "Error 3" << endl;   }   cout << solution << endl;}

Sample Output

If the string generated by the solve function is output, theoutput would look like this for the first set of values in theabove main function:

fill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bsuccess 27

Sample Output Not Shortest Path

fill Bpour B Aempty Apour B Afill Bpour B Aempty Asuccess 28

Answer rating: 100% (QA)

This is a programming problem that requires implementing a graph traversal algorithm to find the cheapest sequence of steps that leads to the goal sta... View the full answer