Question

Pouring water.

We have three containers whose sizes are 10 pints, 7 pints, and 4 pints, respectively. The 7-pint and 4-pint containers start out full of water, but the 10-pint container is initially empty. We are allowed one type of operation: pouring the contents of one container into another, stopping only when the source container is empty or the destination container is full. We want to know if there is a sequence of pouring’s that leaves exactly 2 pints in the 7- or 4-pint container.

(a) Model this as a graph problem: give a precise definition of the graph involved and state the specific question about this graph that needs to be answered.

(b) What algorithm should be applied to solve the problem?

(c) Find the answer by applying the algorithm.

Short answer

(a)Model of this as a graph problem by using breadth-firstis involved and states are shown below in the description.

(b) Algorithm-Breadth-firstsearch by using arbitrarily deep recursion with endless loops is used here.

(c) Answer is in recursive loops.

Step-by-step solution

Step 1: Breadth-First Search

In this question, the solution is provided by using breadth-first search and also by using arbitrarily deep recursion with going into endless loops.

Breadth First Search traverses the tree from level one to the end level in a horizontal order so it is also called level order traversal.

The queue is used as a data structure in thebreadth-first search.

Here start from any one of the nodes, by choosing it randomly and then start traversing by its adjacent unvisited vertex. After that mark, it visited. and stored the visited list in the queue.

Step 2: Model of a graph problem

1. There are three containers whose sizes are 10 pints, 7 pints and 4 pints respectively. The 7 -pint and 4 -pint containers start out full of water, but the 10 pint container is initially empty. Since there are no marks on the containers, then pour the contents of one container into another and stop under the following conditions that are the source container is empty. And the other is the destination container is full. By using a directed graph as a data structure in which the vertices contain tuples where it shows its state.

Starts from the initial state or are said to be the source vertex and after that creates a vertex as a node which shows a possible next state. And connect all nodes and after that apply breadth-first search on the vertices and evaluate the shortest path.The nodes connected to the initial state or node: 7,0,4 and 4,7,0 as is shown below:

• Pattern of each state or node:{10 -pint container, 7 -pint container, 4-pint container}
• Initial state or node: $\left(0,7,4\right)$.
• Final state or node: $\left(8,3,0\right)$.

BFS Algorithm

b)

In this question the solution is provided by using breadth first search and also by using arbitrarily deep recursion with going into endless loops.

The breadth first search is applied here each step are given as:

1). In stating each container is given as a node or vertex are of different sizes of ten, seven and four.

Let’s consider it as a node.

2). Traverse all the node which follows breadth first search.

3). Starting from the source vertex to the end vertex, when we reach to the final destination that is treat as the final answer.

4). The initial vertex as a$(0,7,4)$while traversing.

5).Start traversing by itsadjacent unvisited vertex. After that mark, it visited.

6).By using arbitrarily deep recursion with endless loops start filling container$(0,7,4)$whenever the source vertex is empty and the destination vertex is full.

And again, fill whenever the leaves exactly two pints in the 7 - or 4 -pint container.

Applying the algorithm

c)

In stating each container is given as a node or vertex are of different sizes of ten, seven and four. And let’s consider it as a node of each container.

start out full of water, but the 10-pint container is initially empty.

And type of operation:

a). Pouring the contents of one container into another.

b). Stopping only when the source container is empty or the destination container is full.

c). If there is a sequence of pourings that leaves exactly two pints in the 7 - or 4 -pint container.

Since there are no marks on the containers, then pour the contents of one container into another and stop under the following conditions that arethe source container is empty. And the other is the destination container is full. By usingdirected graph as a data structure in which the vertices contain tuples where it shows its state.

Let’s this scenario:

• Pattern of each state or node: {10 -pint container, 7 -pint container, 4-pint container}
• Initial state or node: $(0,7,4)$.
• Final state or node: $\left(8,3,0\right)$.

Applying Breadth first search on the adjacency nodes which are near by the source vertex. And also apply arbitrarily deep recursion in simultaneously which applied on the endless loops. Traverse all the vertices of container which follows breadth first search. whose sizes are 10 pints, 7 pints, and 4 pints, respectively. The 7 -pint and 4 -pint containers start out full of water.

And the sequence of pouring’s that leaves exactly two pints in the 7 - or 4 -pint container then again starts filling the container.

So here the final result is in the recursive loops.