Search code examples
algorithmlanguage-agnostic

Water Jug Puzzle with N Jug

I'm trying to solve the famous "water jug puzzle" (like in the movie Die Hard with a Vengeance).

I solve easily the puzzle with supports of 2 jugs in C#.

But now I would like to achieve the same with N number of jugs (2, 3, 4, 5, ...). It completely changes the way the algorithm works.

My current solution works on the following principle :

  1. Fill the m litre jug and empty it into n liter jug.
  2. Whenever the m liter jug becomes empty fill it.
  3. Whenever the n liter jug becomes full empty it.
  4. Repeat steps 1,2,3 till either n liter jug or the m liter jug contains d litres of water.

Then, I repeat the operation by reversing the order of the jugs and I take the fastest solution between the two.

This system works great with 2 jugs but cannot work with more jugs.

Reminder of the rules: You have N jugs of water, each with a specific capacity. It is possible to fill a jug completely from a faucet, empty a jug completely into a sink, and transfer the contents of one jug to another (subject to available capacity of target and current fill of source).

The goal is to get ONE jug with a given amount of water (the goal) and find the fastest way to do it.

For example: Two jugs of 3 and 5 liters represented as an array of int [3, 5]. The goal is to have a jug with 4 (represented by an int). The function takes these two elements as parameters and displays the fastest path (if there is one).

The way to get there is (in 6 steps in this case): (0,5) (3,2) (0,2) (2,0) (2,5) (3,4)

As explained before, I solved this simple version with 2 jugs easily. But how to do it with N jugs? Has anyone ever done something similar? Or have an idea?

Solution

  • The only precise operations are

    1. FILL: Completely fill any jug from an infinite water supply.
    2. EMPTY: Completely empty the contents of any jug.
    3. POUR: Pour the contents of jug A into jug B until jug B is full or jug A is empty.

    These operations perform, respectively:

    1. amount[A] = capacity[A];
    2. amount[A] = 0;
    3. temp = min(available(B), amount[A]); amount[B] += temp; amount[A] -= temp;

    With this special convenience function: available(i) => capacity[i] - amount[i]

    Perform a breadth first search from among these relatively few available operations until the desired amount of water exists in one of the jugs.

    There are N choices of indices for operation 1 and 2 (FILL or EMPTY), and there are (N * N-1) choices for operation 3 (POUR), in other words choose a random A and a random B that is not equal to A.

    Optimization Note

    A useful optimization is to prevent enqueuing search states that have already been deemed reachable with fewer steps. A state here is at first glance represented by the values in the amount array, but can also be represented by the number of jugs of each unique capacity and amount, because the jugs themselves are not unique except for their capacity and current amount.