16
$\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$
  • 1
    $\begingroup$ Everything is solvable with BFS :D $\endgroup$ – dmg Jan 27 '15 at 12:52
  • 1
    $\begingroup$ My solution would probably involve a generated automaton. I'm a lazy bum though. $\endgroup$ – No. 7892142 Jan 27 '15 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 '15 at 13:05
  • 3
    $\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 '15 at 13:12
  • 1
    $\begingroup$ @mdc32 ..and the looked-for capacity is not a multiple of that factor! $\endgroup$ – No. 7892142 Jan 27 '15 at 13:23
13
$\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$
  • 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$ – Dewi Morgan Jan 30 '16 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$ – Roobie Nuby Feb 25 '17 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$ – Dewi Morgan Mar 2 '17 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$ – Roobie Nuby Mar 3 '17 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$ – Dewi Morgan Mar 4 '17 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$

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.