24
$\begingroup$

Take a look at these two questions:
- A Set of Water Jug Challenges
- Pouring problem

Now I'm asking for a generalised solution to that problem.

I define the problem as follows:

  • You are required to measure exactly $n$ litres of water.

  • You have $j$ jugs.

  • Each jug has volume $v_m$ where $m$ is the jug-number ($1$ to $j$).

  • You have an infinitely large tub of water.

  • There is no indication on the jugs saying how much liquid is in them, and you can't judge it by eye. You do know for sure when they are empty and when they are full.

Question(s):

  • For what sets of values ($n$, $j$, $v_1$ to $v_j$) is this solvable?

  • For cases which are solvable, what algorithm can be used to find the solution?

This is intended to be a math/algorithm problem, rather than a lateral thinking problem, so 'creative' solutions such as "I use the infinitely-large tub of water to solve the world's drought problems, am elected world president for my services to humanity, and keep the jugs as a souvenir" may be upvoted if they're witty/entertaining but won't be marked as correct.

NB: Searching the entire possible space of jug-pouring actions is clearly a solution. But it isn't a very interesting or elegant one.

See also:

$\endgroup$
14
  • 2
    $\begingroup$ Everything is solvable with BFS :D $\endgroup$
    – dmg
    Jan 27, 2015 at 12:52
  • 1
    $\begingroup$ My solution would probably involve a generated automaton. I'm a lazy bum though. $\endgroup$ Jan 27, 2015 at 12:58
  • 1
    $\begingroup$ @AE each jug has (at most) max(Vn)+1 states (it can have 0 to Vn litres in it). From there on, each state of the search is a combination of the possible states for each of the jugs. In practice, it can turn out that depending on the problem the search space is lower. But this is the upper bound. $\endgroup$
    – dmg
    Jan 27, 2015 at 13:05
  • 4
    $\begingroup$ I don't believe it is possible if all jug capacities have a common factor - for example, measuring 2 liters with jugs of 5, 10, and 15. $\endgroup$
    – mdc32
    Jan 27, 2015 at 13:12
  • 1
    $\begingroup$ @mdc32 ..and the looked-for capacity is not a multiple of that factor! $\endgroup$ Jan 27, 2015 at 13:23

3 Answers 3

14
$\begingroup$

Your link to Diophantine equations shows that you already have an idea of the answer.

The only actions available are filling a jug completely from the tub, emptying a jug completely, or pouring one jug into another. If we fill empty jug $k$ from the tub, then the amount of water we have is increased by $v_k$. Similarly, if we empty jug $k$ when it is full, we decrease the amount of water we have measured by $v_k$. If we empty a jug into another, the amount of water doesn't change. However, if jug $l$ is full, and we pour it into jug $m$, when $v_l>v_m$, then the amount of water left in jug $l$ is $v_l-v_m$, and emptying it will decrease the amount of water we have by that amount. From this, we can see that the only effect we can have on the total amount of water is to add or subtract $v_n$ repeatedly, for each $n\in[1,j]$.

This means that in order to get a total amount of water $n$ (you've used the same variable name for two things, tsktsk) there must be integers $z_1, z_2,\ldots z_j$ so that $z_1v_1+z_2v_2+\cdots+z_jv_j=n$. However, this is not a sufficient condition. For example, if your largest jug has volume $v_k$, and $n\gg v_k$, then you won't have anywhere to put the water you are measuring. The restrictions on the magnitude of $n$ for making a necessary and sufficient condition are tricky, so I'll get to that later. For now, let's suppose that we also have an infinite empty tub to put our water in.

Given volumes $v_1$ to $v_j$ and a goal $n$, the equation $z_1v_1+z_2v_2+\cdots+z_jv_j=n$, or $\sum_{k=1}^jz_kv_k=n$, is a Diophantine equation, because we are looking for integer solutions. So you could simply say that the problem is solvable when this equation has a solution. However, that isn't especially helpful, as it is just restating the question in an abstracted way.

Note that if $d$ is the smallest possible positive value of $\sum_{k=1}^jz_kv_k$, then $d=\gcd(v_1,v_2,\ldots,v_j)$, by Bézout's identity. Furthermore, every number that can be expressed this way (as an integer-multiple linear combination of $v$'s) is a multiple of $d$. Therefore, we have the requirement that $$\gcd(v_1,v_2,\ldots,v_j)\ \textrm{ divides }\ n.$$ If we assume the empty tub, this is a necessary and sufficient condition. It is especially nice because there is already an algorithm for computing the gcd, and the minimal coefficients of the corresponding linear combination: the extended Euclidean algorithm.

Given two integers $a$ and $b$, we can compute $\gcd(a,b)$ and integers $x$ and $y$ so that $ax+by=\gcd(a,b)$ as follows:

Let $r_0=a, r_1=b, s_0=1, s_1=0, t_0=0, $ and $t_1=1$. Then, for any index $i$, find $q_{i+1}, r_{i+1}$ so that $r_{i-1}=q_{i+1}r_i+r_{i+1}$ and $0\le r_{i+1}<r_i$. That is, $g_{i+1}=\left\lfloor\dfrac{r_{i-1}}{r_i}\right\rfloor$ and $r_{i+1}=r_{i-1}\mod r_i$. Also, let $s_{i+1}=s_{i-1}-q_{i+1}s_i$ and $t_{i+1}=t_{i-1}-q_{i+1}t_i$. When you reach $r_{i+1}=0$, stop. At this point, you have $\gcd(a,b)=r_i, x=s_i,$ and $y=t_i$.

This only finds the gcd of two numbers, however, $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$, so you can apply this algorithm repeatedly, storing the coefficients at each stage. Also, you don't always need to test all of the jugs' volumes. As soon as you reach a point where $n$ is a multiple of the gcd you have found, you can stop.

(I will finish this answer later, including how to turn the linear combination back into a jug-pouring sequence.)

$\endgroup$
6
  • 2
    $\begingroup$ "if we empty jug $k$ when it is full, [...] the only effect we can have on the total amount of water is to add or subtract $v_n$ repeatedly, for each $n\in[1,j]$." This feels like a false premise (though likely I'm just misunderstanding, no mathematician, I), as jugs can be topped up or emptied when only partially filled, and I feel there are cases which rely on this. For example, "Given [99, 99, 100], get 2" has a step where you alter the total water stored by 1, which is not any $v_k$. $\endgroup$ Jan 30, 2016 at 4:06
  • $\begingroup$ @DewiMorgan Your concern is addressed two sentences later in "However, if jug l is full, ..." Basically, a partially filled jug can only contain an amount that is the sum or difference of v[n]'s. $\endgroup$ Feb 25, 2017 at 8:03
  • $\begingroup$ @RoobieNuby I am likely misunderstanding, but the "However" sentence seems to list only the case where the source jug is full and the destination jug empty, so that "the amount of water left in jug l is vl−vm". The case of pouring a jug into a vessel that already contains liquid is not covered there. $\endgroup$ Mar 2, 2017 at 4:46
  • $\begingroup$ @DewiMorgan What I wrote addressed your concern. A non-empty non-full jug can only contain a sum or difference of multiples of v[n]s. When you pour one such amount into another jug, the amount left in either jug at the end will also be a sum or difference of multiples of v[n]s. $\endgroup$ Mar 3, 2017 at 14:41
  • $\begingroup$ @RoobieNuby I agree with you that you can alter the total amount of water by any sum or difference of V[n]s. However, this does not seem to be what this answer is saying. It seems to be saying, very clearly, "the only effect we can have on the total amount of water is to add or subtract V[n] repeatedly" - this seems demonstrably false, hence my comment. Given jugs of volume 2 and a 3, we can increase or decrease the total volume of water by 1. In this case, 1 is no V[n]. So we are doing something to the total volume of water which is not "add or subtract V[n] repeatedly". $\endgroup$ Mar 4, 2017 at 6:56
4
$\begingroup$

I wrote a program to find general solutions to the decanting problem. I generalized the problem a little bit by allowing you to search for not just getting a single jug with $n$ liters, but listing the amount of water in each jug. So for instance if you have a 5 liter jug and a 3 liter jug, 4 3 is a possible state.

To use: compile the code with gcc jugs.c -o jugs. Then use the program by calling it and passing it the list of jug sizes you have. It will print all possible states that are reachable and provide instructions on how to reach that state.

Each state is given a state number based upon when it was located, and it provides instructions on how to reach that state for instance start at state 3 then transfer jug 3 into jug 2. The second line provides a full list of how to reach that state starting from all jugs empty.

Example:

./jugs 5 3
Jugs                5   3   
Step 0
Step 1
First occurance of 5
State 1 S0  F 0         5   0   
F 0 

First occurance of 3
State 2 S0  F 1         0   3   
F 1 

Step 2
State 3 S1  F 1         5   3   
F 0 F 1 

First occurance of 2
State 4 S1 T0 1         2   3   
F 0 T0 1 

State 5 S2 T1 0         3   0   
F 1 T1 0 

Step 3
State 6 S4  E 1         2   0   
F 0 T0 1 E 1 

State 7 S5  F 1         3   3   
F 1 T1 0 F 1 

Step 4
State 8 S6 T0 1         0   2   
F 0 T0 1 E 1 T0 1 

First occurance of 1
State 9 S7 T1 0         5   1   
F 1 T1 0 F 1 T1 0 

Step 5
State 10 S8  F 0        5   2   
F 0 T0 1 E 1 T0 1 F 0 

State 11 S9  E 0        0   1   
F 1 T1 0 F 1 T1 0 E 0 

Step 6
First occurance of 4
State 12 S10 T0 1       4   3   
F 0 T0 1 E 1 T0 1 F 0 T0 1 

State 13 S11 T1 0       1   0   
F 1 T1 0 F 1 T1 0 E 0 T1 0 

Step 7
State 14 S12  E 1       4   0   
F 0 T0 1 E 1 T0 1 F 0 T0 1 E 1 

State 15 S13  F 1       1   3   
F 1 T1 0 F 1 T1 0 E 0 T1 0 F 1 

Step 8
First occurance of 0 step 0
First occurance of 1 step 4
First occurance of 2 step 2
First occurance of 3 step 1
First occurance of 4 step 6
First occurance of 5 step 1

You may find it useful to filter the output if there is a single state you are searching for.

Ex.

./jugs 5 3 | grep -A2 'First occurance of 4'
First occurance of 4
State 12 S10 T0 1       4   3   
F 0 T0 1 E 1 T0 1 F 0 T0 1 
--
First occurance of 4 step 6
First occurance of 5 step 1

Ex 2:

./jugs 11 9 7 5 | grep -A1 $'3\t8\t1\t5'
State 3839 S3821  F 3       3   8   1   5   
F 0 F 2 T2 1 T0 3 T0 2 T3 0 F 3 T3 1 T1 2 T2 0 E 0 T3 0 F 3 

So if you have jugs with sizes of 11, 9, 7, and 5, you can reach a state of 3 in the 11, 8 in the 9, 1 in the 7, and 5 in the 5. To do so you fill jug 0, fill jug 2, transfer jug 2 into jug 1, etc.

Code:

#include <stdio.h>
#define maxstates 10000
#define maxsteps 100
#define stringsize 30
int isstatenew(int *states,int numstates,int numjugs)
{
int stateindex, jugnumber;
for(stateindex = 0;stateindex<numstates;stateindex++)
for(jugnumber = 0;;jugnumber++)
{
    if(jugnumber == numjugs)
    return 0;
    if(*(states+numstates*numjugs+jugnumber) != *(states + stateindex*numjugs+jugnumber))
    break;
}
return 1;
}

void traceback(char *statereachingconditions,int statenumber,int *previousstates, int stepnumber)
{
int previous[stepnumber];
previous[stepnumber-1] = statenumber;
int index;
for(index = stepnumber-2;index>=0;index--)
previous[index] = *(previousstates+previous[index+1]);
for(index = 0;index<stepnumber;index++)
printf("%s ",strpbrk (statereachingconditions+stringsize*previous[index],"EFT"));
printf("\n\n");
}

int main(int argc, char **argv)
{
int numjugs = argc-1;
int jugs[numjugs];
int jugnumber;

int *states = malloc(numjugs*maxstates*sizeof(int));
int *previousstates = malloc(maxstates*sizeof(int));
char *statereachingconditions = malloc(stringsize*maxstates*sizeof(char));
int higheststatenumthisstep[maxsteps];
int numstates;

int step=0;
int choice;//0 empty, 1 fill, 2 transfer
int index1, index2;


int newstates = 1;//Number of new states reached on this step
int previousstate;

int transferamount; 
int numtabs;

int maxsize = 0;
printf("Jugs\t\t\t\t");
for(jugnumber = 0;jugnumber<numjugs;jugnumber++)
{
    jugs[jugnumber] = atoi(argv[jugnumber+1]);
    *(states+jugnumber) = 0;
    printf("%d\t",jugs[jugnumber]);
    maxsize = fmax(maxsize,jugs[jugnumber]);
        }
        printf("\n");
int firstoccurance[maxsize+1];
for(index1=0;index1<maxsize+1;index1++)
{
    firstoccurance[index1] = -1;
}
firstoccurance[0]=0;
while(newstates && step<maxsteps)
{
    printf("Step %d\n",step);
    newstates = 0;
    if(step == 0)//Initialize starting state
    {
        higheststatenumthisstep[0] = 0;
        newstates = 1;
        numstates = 1;
        *(previousstates) = 0;

    }
    else//Look for new states from previous step
    {
            if(step == 1)
            previousstate = 0;
            else
            previousstate = higheststatenumthisstep[step-2]+1;
        for(;previousstate<=higheststatenumthisstep[step-1];previousstate++)
        {               
        for(choice = 0;choice<3;choice++)
        for(index2 = 0;index2<numjugs && (choice == 2 || index2<1);index2++)
        for(index1 = 0;index1<numjugs;index1++)
        {
            for(jugnumber = 0;jugnumber<numjugs;jugnumber++)
            *(states+numstates*numjugs+jugnumber) = *(states+previousstate*numjugs+jugnumber);

            switch(choice)
            {
                case 0://Empty
                *(states+numstates*numjugs+index1) = 0;
                break;

                case 1://Fill
                *(states+numstates*numjugs+index1) = jugs[index1];
                break;

                case 2://Transfer
                transferamount = fmin(jugs[index2]-*(states+numstates*numjugs+index2),*(states+numstates*numjugs+index1));
                *(states+numstates*numjugs+index1)-= transferamount;
                *(states+numstates*numjugs+index2)+= transferamount;
                break;
            }
            if(firstoccurance[*(states+numstates*numjugs+index1)] == -1 || firstoccurance[*(states+numstates*numjugs+index2)] == -1)
            {
                if(firstoccurance[*(states+numstates*numjugs+index1)] == -1)
                {firstoccurance[*(states+numstates*numjugs+index1)] = step;
                printf("First occurance of %d\n",*(states+numstates*numjugs+index1));}
                if(firstoccurance[*(states+numstates*numjugs+index2)] == -1)
                {firstoccurance[*(states+numstates*numjugs+index2)] = step;
                printf("First occurance of %d\n",*(states+numstates*numjugs+index2));}
            }
            if(isstatenew(states,numstates,numjugs))
            {
                //printf("State is new");
                switch(choice)
            {
                case 0://Empty
                sprintf(statereachingconditions+stringsize*numstates,"State %d S%d  E %d",numstates,previousstate,index1);
                break;

                case 1://Fill
                sprintf(statereachingconditions+stringsize*numstates,"State %d S%d  F %d",numstates,previousstate,index1);
                break;

                case 2://Transfer
                sprintf(statereachingconditions+stringsize*numstates,"State %d S%d T%d %d",numstates,previousstate,index1,index2);
                break;
            }
                numtabs = 4-(strlen(statereachingconditions+stringsize*numstates))/8;
                printf("%s",statereachingconditions+stringsize*numstates);
                for(jugnumber = 0;jugnumber<numtabs;jugnumber++)
                {
                    printf("\t");
                }
                for(jugnumber = 0;jugnumber<numjugs;jugnumber++)
                {
                printf("%d\t",*(states+numstates*numjugs+jugnumber));
                }
                printf("\n");
                *(previousstates+numstates) = previousstate;
                traceback(statereachingconditions,numstates,previousstates,step);
                numstates++;
                newstates++;
            }

        }
    }
    higheststatenumthisstep[step] = higheststatenumthisstep[step-1]+newstates;
    }
    step++;

}
for(index1 = 0;index1<maxsize+1;index1++)
{
    printf("First occurance of %d step %d\n",index1,firstoccurance[index1]);
}
return 0;
}

If you pass it a really long list, you may need to increase the maxstates variable defined at the top.

$\endgroup$
0
$\begingroup$

I will take over from KSmarts and propose a method how to actually do the pouring.

As we have seen, the problem is solvable if

$z_1v_1+z_2v_2+\cdots+z_jv_j=n$

Let's rewrite the equation using only positive factors. Wlog, after rearranging the jugs, for some k, we have:

$n = z_1v_1+z_2v_2+\cdots+z_kv_k - z_{k+1}v_{k+1}-\cdots-z_jv_j$

where all $z_i$ are now positive integers.

From there the algorithm is actually simple:

- Fill every jug $i$ ($i\le k$) exactly $z_i$ times.
- After each filling except the last, transfer jug $i$'s content in the first jug $m$ ($m\gt k$) that hasn't been emptied $z_m$ times.
- If in the process jug $m$ becomes full, empty it and continue transferring from jug $i$ to the same or the next jug.
- When you have filled all jugs $i$ ($i\le k$) $z_i$ times, you might still need to empty some of the jugs $m$ ($m\gt k$) to reach $z_m$ times emptying them. To do that, fill these jugs with water from the first jugs before emptying them as needed.

The end result is that you have added $z_i$ times $v_i$ for $i\le k$ and removed $z_m$ times $v_m$ for $m\gt k$. According to the equation above, you are left with exactly n liters.

In summary, you don't need to think much about which jug you fill from which one. You just make sure to fill the k first jugs the required number of times and empty the remaining jugs the required number of times. In what order and where you store the water is not important. Just alternate the tasks depending on whether you need water or you need space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.