For this assignment you will solve a more generalized version of this riddle. To
ID: 665840 • Letter: F
Question
For this assignment you will solve a more generalized version of this riddle. To ensure we only have a single solution, we will require that the smaller jug, in this case the 3 gallon jug, be empty once the required number of gallons are in the larger jug. Thus a correct solution to the Die Hard 3 example would be 4 gallons in the 5 gallon jug and zero gallons in the 3 gallon jug.
You have two jugs, A and B, and an innite supply of water. There are three types of actions:
• Fill jug A or ll jug B. • Empty jug A or empty jug B. • Pour water from one jug into the other.
Pouring water from one jug into the other stops when the rst jug is empty or the second jug is full, whichever comes rst. For example, if A has 5 gallons and B has 6 gallons and B has a capacity of 8, then pouring from A to B leaves B full and 3 gallons remaining in A. Each action is now associated with a positive cost. A problem is given by the parameters (Ca, Cb, N, fA, fB,
eA, eB, pAB, pBA), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. The cost to ll A is fA, fB is the cost to ll B, eA is the cost to empty A, and eB is the cost to empty B, pAB is the cost to pour A to B and pBA is the cost to pour B to A. A solution is a sequence of actions that leaves jug A empty, and exactly N gallons in jug B.
The possible actions are listed below where fill means to ll the jug from the innite water supply, empty means to discard the water in the jug, pour A B means to pour the contents of jug A into jug B (this action stops when B becomes full or A becomes empty), and success X indicates that the goal has been accomplished, that is, jug A is empty, jug B contains N gallons, and the total cost of the operations is X.
fill A fill B empty A empty B pour A B pour B A success X
The output from your program will consist of a series of instructions from the list of the possible actions which will result in jug A being empty and jug B containing exactly N gallons of water. The last line of output for each puzzle should be the line success X, where X is the total cost of all the actions. Output lines start in column 1 and there should be no empty lines nor any trailing spaces.
2 Program Specication
Write a Jug class (jug.h, jug.cc) that takes 9 parameters in the constructor, namely (Ca, Cb, N, fA, fB, eA, eB, pAB, pBA). Note that the order of the parameters is important. Use assert in your program to ensure the following: 0 < Ca Cb and N Cb 1000.
class Jug { public: Jug(int,int,int,int,int,int,int,int,int);
~Jug(); // Solve() is used to check the input and find the solution if one exists
// returns -1 if the input is invalid.
// returns 0 if input is valid but a solution does not exist.
// returns 1 if solution is found and also prints solution
int Solve();
private: //anything else you need };
Sample Input
Jug die_hard(3, 5, 4, 1, 2, 3, 4, 5, 6); die_hard.solve();
Sample Output
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
success 27
You will generate a graph to model this problem. The vertices of your graph will store information about the number of gallons of water in each of the two jugs, A and B. The edges in your graph will represent the actions possible for a given vertex. Your program must nd the solution in the shortest number of actions. To achieve this you will implement the Breadth First Search(BFS) algorithm to nd the shortest path in a graph where all edges have a weight of
1. To solve the single-pair-shortest-path problem for a graph with edge weights that vary, but are all positive, you will implement Dijkstra’s Algorithm, and run it on your graph representation for the problem.
Explanation / Answer
#include
#include
#include
class Queue
{
public:
Queue()
: head(NULL), tail(NULL)
{
}
void enqueue(int i)
{
if (head == NULL)
head = tail = new Node(i, NULL);
else
tail = tail->next = new Node(i, NULL);
}
int dequeue()
{
Node* old = head;
head = head->next;
int i = old->i;
delete old;
return i;
}
int isEmpty()
{
return (head == NULL);
}
~Queue()
{
while (!isEmpty())
dequeue();
}
private:
struct Node
{
int i;
Node* next;
Node(int iP, Node* nextP)
: i(iP), next(nextP)
{
}
} *head, *tail;
} iQueue;
const int MAX = 100;
const int MAX_I = (MAX + 1) * (MAX + 1);
int N, M, k, n, m;
int distance[MAX_I];
int prev[MAX_I];
int nmToI(int n, int m)
{
return n * (M + 1) + m;
}
int iToN(int i)
{
return i / (M + 1);
}
int iToM(int i)
{
return i % (M + 1);
}
void trace(int i)
{
if (i > 0)
trace(prev[i]);
cout <<" "<
}
void test(int n, int m, int n1, int m1)
{
if (n1 < 0 || n1 > N || m1 < 0 || m1 > M)
return;
int i1 = nmToI(n1, m1);
if (distance[i1] != 0)
return;
int i = nmToI(n, m);
distance[i1] = distance[i] + 1;
prev[i1] = i;
iQueue.enqueue(i1);
}
int solve()
{
n = m = 0;
distance[0] = 1;
iQueue.enqueue(0);
while (!iQueue.isEmpty())
{
int i = iQueue.dequeue();
int n = iToN(i);
int m = iToM(i);
if (n == k || m == k || n + m == k)
return i;
// empty out a jug
test(n, m, 0, m);
test(n, m, n, 0);
// fill a jug
test(n, m, N, m);
test(n, m, n, M);
// pour one to another until source is empty
test(n, m, 0, n + m);
test(n, m, n + m, 0);
// pour one to another until destination is full
test(n, m, n – M + m, M);
test(n, m, N, m – N + n);
}
return -1;
}
void main()
{
clrscr();
cout<<"Please enter the number of gallons in first jug: ";
cin>>N;
cout<<"Please enter the number of gallons in second jug: ";
cin>>M;
cout<<"Please enter the vol. of water to be left finally: ";
cin>>k;
int i = solve();
cout<<" JUG 1 "<<" JUG 2 ";
cout<<"---------------- ";
if (i == -1)
cout << 0 << " ";
else
{
cout << distance[i] << " ";
trace(i);
}
cout << -1 << " ";
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.