**The Two Water Jugs Problem**

The premise of the puzzle is simple. You have a well, and two water jugs of different sizes. The idea is to get a specific amount of water in one of (or both of) the jugs. In doing so, you are allowed to:

You are not allowed to do anything else, such as fill up a jug to a specific level - it is assumed that there are no ways of telling how full the jug is if it is partially full.

It is possible to tell whether or not a particular jugs problem is doable or not. Say that the capacity of one jug is `p`, the capacity of the other is `q` and that the target amount of water is `r`. A jug problem is possible if `p` and `q` are relatively prime, and if `r` is no bigger than `(p+q)` and/or if `r` is a multiple of gcd(`p`,`q`). Consequently, if you have a 9 litre jug and a 5 litre jug, it is possible to reach any amount of water between 0 and 14 litres inclusive. However, if you have a 6 litre jug and a 4 litre jug, you can only get 0, 2, 4, 6, 8 and 10 litres.

It isn't too hard to work out solutions for even bigger combinations. It's possible (read: I have done this myself) to use computational problem solvers to solve these in a few seconds; it took my machine a mere 0.88 seconds to work out how to get 5 litres, using a 19 litre and a 1,091 litre jug, in 348 steps.

Thanks go to neil for pointing out that a jug problem is still possible if `p` and `q` are not relatively prime, as long as `r` is a multiple of their greatest common divisor.

The contents of this writeup are in the public domain.