-1
$\begingroup$

We have 3 jugs with capacities A, B and C. How can we create an algorithm that will find out how to measure D liters?

This is my task for one online course I'm taking. I have no idea where to start. I don't even understand how are these four related to each other. I will be thankful for any help or clarification of the problem.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you have capacities given or just symbolic? Probably the task states that $A \gt B \gt C$, you can use differences between them to create finer scale and check the capacity of $D$ by using the rest with the restriction that the $D$ capacity is some multiple of the minimal measureable amount. If this is purely symbolic without other constraints, well it be hard. $\endgroup$ – Evil Oct 20 '17 at 19:06
  • 1
    $\begingroup$ When you don't know how to get started, try some examples (e.g., example values for A,B,C). If you're still stuck, try a simpler version of the problem (e.g., just 2 bowls instead of 3). Work through examples until you start to get some feeling for the problem, and see if any patterns emerge. $\endgroup$ – D.W.♦ Oct 20 '17 at 19:33
1
$\begingroup$

Construct (mentally) a graph whose vertex set consists of triplets $(a,b,c)$ denoting the amount of water in each of the three bowls. Edges correspond to allowable operations (which you haven't specified). There is also a distinguished vertex, which is the starting position (which you haven't specified), and a bunch of target vertices (in which $D \in \{a,b,c\}$). You want to know whether a target vertex is reachable from the starting position. The obvious thing to try is some graph search algorithm such as BFS, DFS, or A*. These algorithms don't actually require you to construct the entire graph ahead of time.

There might be more efficient algorithms, but this is the baseline against which more sophisticated algorithms should be compared.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

This is a generalisation of an old puzzle. We assume that you can pour water into a jug until it is full, that you can pour water from one jug into another until either the first is empty or the second is full, and that you can empty a jug. You should also assume that you have a fourth container of unknown capacity $> D$, and that you can only pour fluid into the container but not remove it.

That way you can measure various amounts of water. For example, fill the first jug with $A$ liters. If $B < A$, pour water from the first to the second jug until it is full, so the first jug contains $A-B$ and the second contains $B$.

So you write down all the ways that you can produce various amounts of fluid. And then you write an algorithm that tries out possibilities and finds one that fills the last container with $D$.

Your headline describes a slightly different problem.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

A configuration describes the amount of water in each jug. The initial configuration is all jugs empty.

The moves from a configuration are as follows:

  • Fill a jug.
  • Empty a jug.
  • Pour as much as possible from one jug into another.

Use breadth-first search to explore the possible configurations. Stop when you find a configuration with $D$ in a jug.

Assuming that the capacities of the jugs are rational relative to one another, there are a finite number of configurations; so any kind of search will terminate. But BFS will find the quickest route to a configuration.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.