1
$\begingroup$

When reading up on graph theory, I came across this puzzle and on further investigation, learned that a general solution for this is similar to this problem.

However, I haven't been able to understand how a graph may be used (though I did come across this animation). I'm trying to come up with an algorithm where, given two buckets of capacities a and b, how can I come up with the least number of steps to obtain precisely k litres? Since I originally saw the question in relation to a chapter on graph theory, I would love some pointers on how this may be solved using graphs (as opposed to the seemingly more commong gcd method).

EDIT: I found another related solution but am still not entirely certain.

$\endgroup$
1
  • 1
    $\begingroup$ As for how to describe the problem with graphs, if you went a bit further down the page you would have seen a similar problem where they describe the graph-theoretical approach. Essentially, it involves describing each possible state as a vertex, and transitions from one state to another as edges. $\endgroup$
    – JMoravitz
    Mar 19, 2015 at 19:08

1 Answer 1

Reset to default
0
$\begingroup$

The idea is that an ordered pair representing an amount of water one can obtain in each bucket represents a node in a graph. The directed edges of the graph represent which states are obtainable in one move from the current state.

Solving for the least number of steps to obtain precisely $k$ liters is then a shortest path problem. You are searching the graph for the shortest path from the original state to a state that has $k$ as one the members of the ordered pair.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .