Solving the water jug problem

Question

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.

Answer 1

This type of problem is often amenable to dynamic programming techniques. I've ofetn seen this specific problem used as an example in operations research courses. One nice step-by-step description is here.

Answer 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.

Answer 3

The search space method is what I would've suggested. I made a program to solve generic water jugs problems using a BFS. Could send it to you if you wish.

Answer 4

You are given two jugs, a 4-gallon one and a 3-gallon one.Neither has any measuring markers on it.How can you get exactly 2-gallons of water in 4-gallon jug?

Answer 5

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

Answer 6

can you send me the generic code ?