Graph Modeling and Algorithms for the Water Jug Problem Solution

This document presents a solution to the classic water jug problem, a common challenge in computer science and artificial intelligence. The assignment, part of a COT 4400 course, involves modeling the problem as a graph and employing the Breadth-First Search (BFS) algorithm to determine the steps required to measure a specific amount of water using two jugs of different capacities. The solution details the construction of a directed, weighted, and vertex-labeled graph. It provides pseudo-code for computing the moves and outlines the steps involved in filling, emptying, and transferring water between the jugs. The solution includes a step-by-step breakdown of the process, illustrating the state of the jugs at each stage, and references relevant academic papers. The project emphasizes the application of graph theory and algorithmic problem-solving techniques.

Running head: WATER JUG PROBLEM
WATER JUG PROBLRM
Name of the Student
Name of the University
Author Note

WATER JUG PROBLEM 1
WATER JUG PROBLEM:
Two jugs are given, one is a 5 gallon jug and another one is a 3 gallon jug. The
challenge here is to find 3 gallons of water in a 5 gallon jug.
1) What type of graph would you use to model the problem input and how would you
construct this graph?
For the solution the BFS (Breadth-first search) technique can be used by making a
tree to solve the water jug problem. The graph is a directed graph and it is weighted too and
the graph is vertex labelled.
2. Give pseudo code for an algorithm to compute the amount of water that takes the most
moves to reach?
Pseudo code:
Class Jug {
value as integer
capacity as integer
public:
jug is integer
{
initial value is zero
initial capacity is n
}
void Fill() //fill
{
store capacity to value
}

2WATER JUG PROBLEM
empty function
{
empty value
}
value is full
{
value is greater than or equal to capacity
}
value is empty
{
empty
}
Transfer the contents hold by B to A till A shows full
{
store new value to old value
store value with b's value to value
if value is greater than capacity
omit old value from new value
}
get new value
{
return to value
}
};

3WATER JUG PROBLEM
gcd as integer
{
condition
return value of p
condition
return value
else
condition unsatisfied
}
{
C cannot hold water more than capacity //overflow
return false
}
//if k is multiple i and j hcf then
{
return true;
}
//if k is multiple i and j hcf then
Unable to reach this state with the jugs that are given
//false
}
jug and value
{
//condition
{
C full
{
fill D
store value
}

4WATER JUG PROBLEM
C is full
{
C is empty
store value
}
` Store D to C
store value
}
}
int main()
{
int i, j, result;
Enter the capacity of C
Enter the capacity of D
do{
Enter the water that is required in C
result;
}
condition
Jug C(i), D(j);
print result
solved
cout<<"Done!"<<endl; //done
#endif
//end of program
return 0;

5WATER JUG PROBLEM
}
Here for getting the solution the following steps can be followed. The steps are:
1. Fill 5-gal jug (x, y) → (5, y)
x < 5
2. Fill 3-gal jug (x,y) → (x,3)
y < 3
3. Empty 5-gal jug (x,y) → (0,y)
x > 0
4. Empty 3-gal jug (x,y) → (x,0)
y > 0
5. Pour water from 3 (x,y) → (5, y - (5 - x))
to fill 5-gal jug 0 < x+y ≥ 5 and y > 0
6. Pour water from 5 (x,y) → (x - (3-y), 3)
to fill 3-gal-jug 0 < x+y ≥ 3 and x > 0
7. Pour all water from 3-gal (x,y) → (x+y, 0)
into 5-gal 0 < x+y ≤ 5 and y ≥ 0
8. Pour all water from 5 (x,y) → (0, x+y)
into 3-gal jug 0 < x+y ≤ 3 and x ≥ 0
The solution will be as follows:

6WATER JUG PROBLEM
Gals in 5-gal jug Gals in 5-gal jug Rule Applied
0 0
0 3 1. Fill 3
3 0 7. Pour 3 into 5 to fill
3 3 1. Fill 3
5 1 7. Pour 3 into 5 to fill
0 1 3. Empty 5
1 0 7. Pour 3 into 5 to fill
1 3 1. Fill 3
4 0 7. Pour 3 into 5 to fill
Input:

7WATER JUG PROBLEM
Output:
References:

8WATER JUG PROBLEM
Man, Y. K. (2015, March). Solving the general two water jugs problem via an algorithmic
approach. In Proceedings of the International MultiConference of Engineers and
Computer Scientists (Vol. 1, pp. 18-20).
Saxena, D., Malik, N. K., & Singh, V. R. (2015). A cognitive approach to solve water jugs
problem. International Journal of Computer Applications, 124(17).