Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Solving the water jug problem – Artificial Intelligence

While reading through some lecture notes on preliminary number theory, I came across the solution to
water jug problem (with two jugs) which is summed as thus:

Using the property of the G.C.D of two numbers that GCD(a,b) is the smallest possible linear combination of a and b, and hence a certain quantity Q is only measurable by the 2 jugs, iff Q is a n*GCD(a,b), since Q=sA + tB, where:

n = a positive integer
A = capacity of jug A
B=  capacity of jug B

And, then the method to the solution is discussed

Another model of the solution is to model the various states as a state-space search problem as often resorted to in Artificial Intelligence.

My question is: What other known methods exist which models the solution, and how? Google didn’t throw up much.

Tags:

5

Answers


  1. 0

    This type of problem is often amenable to dynamic programming techniques. I’ve ofetn seen this specific problem used as an example in operations research courses. One nice step-by-step description is here.

    Login or Signup to reply.
  2. 0

    An amazing and amusing approach (for 3 jugs) is through barycentric coordinates (really!), as described at the always brilliant website Cut-the-Knot: Barycentric coordinates: A Curious Application.

    Login or Signup to reply.
  3. 0

    The search space method is what I would’ve suggested. I made a program to solve generic water jugs problems using a BFS. Could send it to you if you wish.

    Login or Signup to reply.
  4. 0

    Strictly for 2 Jug Problem

    Q = A * x + B * y

    Q = Gallons you need.

    Note: The Q must be a multiple of Gcd(A,B) else there is no solution. If Gcd(A,B) == 1, There is a solution for Any Q.

    1) Method 1 :
    Extended Euclid’s Algorithm will solve it faster than any Graph Algorithm.

    2) Method 2:
    Here’s a Naive Approach. (note, this can throw 2 solutions, You’ll have to choose which is shorter)

    The Problem in question can be simply solved by repeatedly Fill from one bucket A to another bucket B (order doesnt matter) until it fills up with the amount you want…ofcoz, when a bucket fillsup, you empty it and continue. 

        A = 3, B = 4 and Q = 2

    Repeatedly Fill A->B

        A B
   ######
    0 0
    4 0
    1 3
    1 0
    0 1
    4 1
    2 3 <-Solution

    Lets try and observe what happens if we go the other way round,
    Fill B->A

    A  B
#####
0  0
0  3
3  0
3  3
4  2 <- Solution

    In this case filling B->A gives us the goal state faster than A->B

    Generic N Jugs
    Here’s an interesting paper

    Login or Signup to reply.
  5. 0

    I encountered this problem during one of my studies. As you, and as st0le said here, I found as answer to the problem the Extended Euclide’s algorithm. But this answer do not satisfied me, because I think it’s a quantitative answer, not a qualitative one (that is, the algorithm does not say what step to take to reach the result).

    I think I found a different solution to the problem that always reach the result with the minimum number of steps.

    Here it is:

    1. Check problem’s feasibility:
      • Q is a multiple of the MCD(A,B);
      • Q is <= max(A,B).

    2. Choose the service jug (that is, the one you will refill with the pump). Supposing A > B (you can easily find which jug is the bigger one):

      if(Q is multiple of B)
    return B

a_multiplier = 1
b_multiplier = 1
difference = A - B
a_multiple = A
b_multiple = B
while(|difference| differs Q)
    if b_multiple < a_multiple
        b_multiple = b_multiplier + 1
        b_multiple = b_multiplier * B
    else
        a_multiple = a_multiplier + 1
        a_multiple = a_multiplier * A

    difference = a_multiple - b_multiple

if(difference < 0)
    return B
else
    return A

    3. start the filling process:

      • fill with the pump the service jug (if empty)

      • fill the other jug using the service one

      • check fullness of the other jug and, in case, empty it

      • stop when the bigger jug contains Q

    Below you find a very naive implementation of the algorithm in c++. Feel free to reuse it, or improve it as you need.

    #include <cstdio>
#include <cstdlib>
#include <cstring>

unsigned int mcd(unsigned int a, unsigned int b) {
    // using the Euclide's algorithm to find MCD(a,b)
    unsigned int a_n = a;
    unsigned int b_n = b;
    while(b_n != 0) {
        unsigned int a_n1 = b_n;
        b_n = a_n % b_n; 
        a_n = a_n1;
    }
    return a_n;
}

unsigned int max(unsigned int a, unsigned int b) {
    return a < b ? b : a;
}

unsigned int min(unsigned int a, unsigned int b) {
    return a > b ? b : a;
}

void getServiceJugIndex(unsigned int capacities[2], unsigned int targetQty, unsigned int &index) {
    unsigned int biggerIndex = capacities[0] < capacities[1] ? 1 : 0;
    unsigned int smallerIndex = 1 - biggerIndex;
    if(targetQty % capacities[smallerIndex] == 0) {
        // targetQty is a multiple of the smaller jug, so it's convenient to use this one
        // as 'service' jug
        index = smallerIndex;
        return;
    }

    unsigned int multiples[2] = {capacities[0], capacities[1]};
    unsigned int multipliers[2] = {1, 1};
    int currentDifference = capacities[0] - capacities[1];
    while(abs(currentDifference) != targetQty) {
        if(multiples[smallerIndex] < multiples[biggerIndex])
            multiples[smallerIndex] = capacities[smallerIndex] * ++multipliers[smallerIndex];
        else
            multiples[biggerIndex] = capacities[biggerIndex] * ++multipliers[biggerIndex];

        currentDifference = multiples[biggerIndex] - multiples[smallerIndex];
    }

    index = currentDifference < 0 ? smallerIndex : biggerIndex;
}

void print_step(const char *message, unsigned int capacities[2], unsigned int fillings[2]) {
    printf("%snn", message);
    for(unsigned int i = max(capacities[0], capacities[1]); i > 0; i--) {
        if(i <= capacities[0]) {
            char filling[9];
            if(i <= fillings[0])
                strcpy(filling, "|=====| ");
            else
                strcpy(filling, "|     | ");
            printf("%s", filling);
        } else {
            printf("        ");
        }
        if(i <= capacities[1]) {
            char filling[8];
            if(i <= fillings[1])
                strcpy(filling, "|=====|");
            else
                strcpy(filling, "|     |");
            printf("%s", filling);
        } else {
            printf("       ");
        }
        printf("n");
    }
    printf("------- -------nn");
}

void twoJugsResolutor(unsigned int capacities[2], unsigned int targetQty) {
    if(capacities[0] == 0 && capacities[1] == 0) {
        printf("ERROR: Both jugs have 0 l capacity.n");
        return;
    }
    // 1. check feasibility
    //  1.1. calculate MCD and verify targetQty is reachable
    unsigned int mcd = ::mcd(capacities[0], capacities[1]);
    if ( targetQty % mcd != 0 ||
    //  1.2. verify that targetQty is not more than max capacity of the biggest jug
            targetQty > max(capacities[0], capacities[1])) {
        printf("The target quantity is not reachable with the available jugsn");
        return;
    }
    // 2. choose 'service' jug
    unsigned int serviceJugIndex;
    getServiceJugIndex(capacities, targetQty, serviceJugIndex);
    unsigned int otherJugIndex = 1 - serviceJugIndex;
    unsigned int finalJugIndex = capacities[0] > capacities[1] ? 0 : 1;
    // 3. start fill process
    unsigned int currentFilling[2] = {0, 0};
    while(currentFilling[finalJugIndex] != targetQty) {
        // 3.1 fill with the pump the service jug (if needed)
        if(currentFilling[serviceJugIndex] == 0) {
            currentFilling[serviceJugIndex] = capacities[serviceJugIndex];
            print_step("Filling with the pump the service jug", capacities, currentFilling);
        }

        // 3.2 fill the other jug using the service one
        unsigned int thisTimeFill = min(currentFilling[serviceJugIndex], capacities[otherJugIndex] - currentFilling[otherJugIndex]);
        currentFilling[otherJugIndex] += thisTimeFill;
        currentFilling[serviceJugIndex] -= thisTimeFill;
        print_step("Filling the other jug using the service one", capacities, currentFilling);
        // 3.3 check fullness of the other jug and, in case, empty it
        if(currentFilling[otherJugIndex] == capacities[otherJugIndex]) {
            currentFilling[otherJugIndex] = 0;
            print_step("Empty the full jug", capacities, currentFilling);
        }
    }
    printf("Donen");
}

int main (int argc, char** argv) {
    if(argc < 4)
        return -1;
    unsigned int jugs[] = {atoi(argv[1]), atoi(argv[2])};
    unsigned int qty = atoi(argv[3]);

    twoJugsResolutor(jugs, qty);
}

    I don’t know if there is any mathematical concept behind the process I described to choose the right jug to minimize the number of needed steps, I use it as an heuristic.

    I hope this can help you.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search