data structureWe have two containers: one has a capacity of three gallons of water, the other five gallons. Both are initially empty, although we have access to a large water fountain. We can take a non-full container and fill it completely up with the water, or we can completely empty a container (with water in it) into the fountain, or we can pour the contents of one container into the other until either the first is empty or the second is full. Our goal is to find a sequence of actions we can take to end

Question

Computers & Technology

Yael Boyer

10 October, 17:18

data structureWe have two containers: one has a capacity of three gallons of water, the other five gallons. Both are initially empty, although we have access to a large water fountain. We can take a non-full container and fill it completely up with the water, or we can completely empty a container (with water in it) into the fountain, or we can pour the contents of one container into the other until either the first is empty or the second is full. Our goal is to find a sequence of actions we can take to end

+1

Answers (1)

Know the Answer?

Piper Oconnell · Answer 1

Answer explained below

Explanation:

This problem can be represented on a graph by considering each state (or configuration) of the pair of containers as a vertex of the graph. We will be having 24 vertices, since the first container can have 0, 1, 2 or 3 gallons and the second can have 0, 1, 2, 3, 4 or 5 gallons of water. So, we will be having vertices like (0, 0), (0, 1), (0,5), (1, 0), (2, 3), (5, 5) etc.

The edges will be directed, and a vertex will be having an edge to it from another vertex if the configuration of the later vertex can be reached from the former vertex by any one of the legal moves. For example, from (2, 3) we can get (0, 5) by transferring the contents of the first container to the second. So there will be an edge from (2, 3) to (0, 5).