All,
There is a common puzzle called the 3 jug problem. You have 3 jugs (X, Y and Z) and a sufficiently large supply of water (infinite). Jugs X and Y hold a fixed whole amount of water. Jug Z is sufficiently large to hold an arbitrary amount of water (infinite). The usual task is to get a target amount (T) of water in jug Z without any measuring device other than jugs X and Y.

T must be a multiple of GCD(X, Y). For GCD(X, Y) = 1, any value of T can be obtained - which is typical in such puzzles. This is all a non-straight forward way of saying that the usual problem is simple and boring.

This challenge puts further constraints on the problem and complicates it - to answer the following questions:

• Is there a general solution for all values of X, Y and T that minimize the number of steps?^*
• Is there a general solution for all values of X, Y and T that minimize the amount of water needed?^*
• If such a general solution exists, does it still work if instead of being a 3 Jug Problem, it is extended to N jugs?

While I understand this is more of a math problem, there was sufficient interest in the chatterbox to post it. Ideas ranged from brute force, dynamic programming to towers of hanoi. Since the description in the first two paragraphs might not have made how this works clear, here is an example (which may not be optimal):

X = 3, Y = 5, T = 4
GCD(X, Y) = 1 so we know it is possible

0.  Starting state (X=0, Y=0, Z=0)
1.  Fill X with 3 units of water (X=3, Y=0, Z=0)
2.  Pour X into Z (X=0, Y=0, Z=3)
3.  Fill X with 3 units of water (X=3, Y=0, Z=3)
4.  Pour X into Y (X=0, Y=3, Z=3)
5.  Fill X with 3 units of water (X=3, Y=3, Z=3)
6.  Pour X into Y until Y is full (X=1, Y=5, Z=3)
7.  Pour X into Z (X=0, Y=5, Z=4)
[download]

* Each "step" is defined as filling a jug or pouring a jug. For the example above, there are 7 steps. The amount of water was 9. If, in a more complicated problem, water needs to be poured on to the ground - that water would need to be accounted for as well. Since I don't know the answer to the questions above, it is possible that the optimal solution for steps is not the same as for water.

Update: Second paragraph was re-worded as blokhead pointed out via /msg that I had misunderstood and mistated something

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.