Solving the water jug problem
Solution 1
Strictly for 2 Jug Problem
Q = A * x + B * y
Q = Gallons you need.
Note: The Q must be a multiple of Gcd(A,B) else there is no solution. If Gcd(A,B) == 1, There is a solution for Any Q.
1) Method 1 : Extended Euclid's Algorithm will solve it faster than any Graph Algorithm.
2) Method 2: Here's a Naive Approach. (note, this can throw 2 solutions, You'll have to choose which is shorter)
The Problem in question can be simply solved by repeatedly
Fill from one bucket A to another bucket B (order doesnt matter) until it fills up with the amount you want...ofcoz, when a bucket fillsup, you empty it and continue.
A = 3, B = 4 and Q = 2
Repeatedly Fill A->B
A B
######
0 0
4 0
1 3
1 0
0 1
4 1
2 3 <-Solution
Lets try and observe what happens if we go the other way round, Fill B->A
A B
#####
0 0
0 3
3 0
3 3
4 2 <- Solution
In this case filling B->A gives us the goal state faster than A->B
Generic N Jugs Here's an interesting paper
Solution 2
An amazing and amusing approach (for 3 jugs) is through barycentric coordinates (really!), as described at the always brilliant website Cut-the-Knot: Barycentric coordinates: A Curious Application.
Admin
Updated on September 18, 2020Comments
-
Admin over 3 years
While reading through some lecture notes on preliminary number theory, I came across the solution to water jug problem (with two jugs) which is summed as thus:
Using the property of the G.C.D of two numbers that GCD(a,b) is the smallest possible linear combination of a and b, and hence a certain quantity Q is only measurable by the 2 jugs, iff Q is a n*GCD(a,b), since Q=sA + tB, where:
n = a positive integer A = capacity of jug A B= capacity of jug B
And, then the method to the solution is discussed
Another model of the solution is to model the various states as a state-space search problem as often resorted to in Artificial Intelligence.
My question is: What other known methods exist which models the solution, and how? Google didn't throw up much.
-
amar about 11 yearsDeciding which one to fill to first: does this - "IF(Q is b/w A AND B) THEN max(A, B) ELSE min(A, B)" help actually?
-
st0le about 11 years@AMAR, I don't think so. Can't say for sure. Do you have any proof?
-
amar about 11 yearsNope. It was a question. I had tried it in a problem with hit and trial to smaller 5-6 pairs. Not sure if it works for all.
-
user1414696 almost 9 yearsIs it possible to have jugs with such volumes that it takes same number of steps for both the approaches: filling A first and filling B first??
-
Shubham about 6 years@st0le The link to the paper (in the end) is a dead link.