Update: elaboration on the above paragraph. Suppose aX + bY = gcd(X,Y). Then one of {a,b} is positive and one is non-positive. Suppose a is positive. Then here is how you get gcd(X,Y) units in the X-unit jug:

• Do this "a" times: Fill the X-jug and dump as much as you can into the Y-unit jug.
• If the Y-jug fills during this step, and you have dumped the Y-jug less than |b| times, then dump the Y-jug on the ground and continue to empty the X-jug into the Y-jug.
• Once you have dumped the Y-jug |b| times, there will be aX - |b|Y = aX + bY = gcd(X,Y) left in the X-jug, which you can pour into the target jug

BTW, the greedy approach won't necessarily work either. The greedy approach is (assuming X>Y): fill in increments of X as many times as you can, then fill in increments of Y as many times as you can, then somehow obtain the remaining amount to be filled, if any.

For instance, with X=5, Y=3, and target = 6, the best you can do is fill the 3-unit jug twice. The greedy algorithm would first put 5 units in the target jug, then try to get 1 unit into the target jug, which will certainly take more steps.

In fact, if you restrict the target amount to something that is expressible as a positive linear combination of X and Y, you have an equivalent of the change-making problem, where it is known that the greedy algorithm may not always work (for the generalized problem with more than 2 jugs/denominations).

blokhead,
BTW, the greedy approach won't necessarily work either.

There is a reason I left that on my scratch and not in this post :-) I knew if I said it was my hunch, I would immediately be proven wrong. Perhaps DP is the way to go.

Cheers - L~R

If GCD(X, Y) <> 1, then any value of T can be obtained provided that T > X*Y - X - Y

I think your condition is not stated correctly. If X = 2 and Y = 4, then no odd T is achievable. Perhaps the condition should be any T where T is a multiple of GCD(X, Y)? </nitpick> And on to the list.

It seems like dynamic programming is the way to go for either optimization. Essentially I see it in two stages: determining algorithms for obtaining all water amounts less than the bigger jug and then application of the Knapsack problem. I'm gonna go off with a pen and paper to think about how to achieve that first part. Don't tell my boss.

kennethk,
Not a nitpick, it was outright wrong. I have modified the second paragraph accordingly as blokhead has also pointed this out in a /msg. I misunderstood this which talks about GCD(X, Y) = 1 but where the only operation permitted is addition.

Cheers - L~R

So, I'd apply Dijkstra's algorithm. Start with a queue containing a single state (X = Y = Z = 0). Now, loop and do the following:

• Pop a state from the queue.
• For each transition, apply the transition to the popped state, creating a new state. For each such state:
  • If the new state satisfies the condition, you're done.
  • Else, if we've seen this state before, try next transition.
  • Otherwise, put the state at the back of the queue.

The drawback is that the algorithm will not terminate if there is no solution. Nor is it necessarely efficient.

You can easily change the algorithm to find the solution using the smallest amount of water to keep track of the amount of water used, and keeping the queue partially ordered (a heap will do) on water usage.

I saw your node when I was about to post a solution that uses the technique you mentioned, so I'll post it here. It saves me from explaining it :)

Such as solution for the first problem:

Read more... (3 kB)

7 steps:
   S->X
   X->Z
   S->X
   X->Z
   Z->Y
   S->X
   X->Z
[download]

And for the second problem

Read more... (3 kB)

Required supply: 6
7 steps:
   S->X
   X->Z
   S->X
   X->Z
   Z->Y
   Y->X
   X->Z
[download]

Being the brute-force approach, I wrote is as a baseline for verification and benchmarking.

• This is the same algorithm that JavaFan described (brute force).
• It tracks water usage, if you want to optimize a solution that way, but that's commented out right now. I suspect that the shortest path solution is always the least water used solution.
• Call it with a series of numbers on the command line. The first is the target number, and all subsequent numbers are jug capacities.
• It can handle any number of jugs.
• I wrote a jug object with Moose, mostly for fun.
• Formatting courtesy of Perl::Tidy because Yours::Truly wrote some long lines.
• I waste CPU and memory as if I'm writing in Perl or something.

Update: After some work last night refactoring this into more objects and other fun stuff, it now can really find least water solutions, but it takes a really long time to do it.

It tracks water usage, if you want to optimize a solution that way, but that's commented out right now. I suspect that the shortest path solution is always the least water used solution.

I think you are wrong. I wrote my own solution (which I won't post, as several have now been posted) and found that for jugs with sizes 3 and 7, and target 11, there's a solution that requires 5 moves (fill Y, pour Y in X, pour Y in Z, fill Y, pour Y in Z), but that uses 14 water. There's a solution that requires just 11 water, but that requires 6 moves (fill Y, pour Y in X, pour Y in Z, pour X in Y, fill Y, pour Y in Z).

Of course, my program may be wrong, and I might have missed a 5 move solution that uses just 11 water.

My solution agrees with your findings:

$ perl min_steps.pl 3 7 11
5 steps:
   S->Y
   Y->Z
   Z->X
   S->Y
   Y->Z

$ perl min_supply.pl 3 7 11
Required supply: 11
6 steps:
   S->Y
   Y->Z
   Z->X
   X->S
   S->Y
   Y->Z
[download]

How many steps do you see? And how much water is consumed?

1. Fill Y pour Z
2. Fill Y pour Z
3. Fill X from Z and return to resevoir.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

I wrote my own solution (which I won't post, as several have now been posted) ...

I'd be interested to see that.

I did some more work on mine, and I got to where I thought it should find a minimum water solution, but it ran overnight without finishing.

Note that the problem he describes is somewhat more restrictive: either you have 3 jugs with certain amounts of liquid, or you have just 2 jugs and an infinite supply of liquid (so, no arbitrary large jug).

Here is some math describing the 3 jugs problem where all jugs have finite (integer) size, and no water is to be spilled (and no infinite supply available).