How to determine reachable states in 3 water jug problem?

Question

Consider 3 water jugs 1,2,3 with capacities 12,8,5 respectively. The total water held by the 3 jugs should be 12 units. We can either empty jug x into jug y (xEy) or fill up jug y from jug x (xFy). With these considerations in mind, given a start state and a goal state, how can we tell if the goal state is reachable in finite steps without actually performing the algorithm?

The equation x+y+z = 12 has 53 solutions, i.e., 2756 possible pairs of start and goal states. Inspecting all these pairs for reachability individually, even on a computer is madness, like the goal state (0,7,5) has 12 start states for which it is reachable. Or I have not yet thought of a good algorithm. Anyways, the number is too big and I want some 'thumb rule' for identifying reachable states. Any help or idea would be appreciated.

Answer 1

Let's uniquely identify a jug state as the amount of water in all 3 jugs with this little data structure (an array of 3 integers). For this exercise, I'll code in C/C++, but it could easily be ported to any programming language.

struct JugState
{
    int jugs[3];
};

So for example, if the first jug has 4 units of water, the second jug has 5, and the third jug has 3. Then we can have a JugState above of {4,5,3} for example.

But given that the jugs have a fixed capacity of 12, 8, and 5 respectively. We can easily have an integer representation of the jug state. The above {4,5,3} configuration could easily be represented with the number 453. A jug configuration of {11,0,1} could be represented as 1101. It doesn't have to be a decimal encoding, but it makes for debugging easier.

We can have helper functions that converts from JugState to "jug state index".

int getIndexFromJugState(const JugState& jugState)
{
    return jugState.jugs[0] * 100 + jugState.jugs[1] * 10 + jugState.jugs[2];
}

JugState getJugStateFromIndex(int index)
{
    int jug2 = index % 10;
    index = index / 10;

    int jug1 = index % 10;
    index = index / 10;

    int jug0 = index;
    return { jug0, jug1, jug2};
}

Now we can define a function that moves water from one jug to another. This function is aware of the 12,8,and 5 unit capacities of each jug. It takes as parameters the initial "jug state index", and two parameters to indicate where water is being moved from (e.g. 0,1,2 indices of the JugState). For example, if you invoke it as moveWater(453, 0, 1) that's basically saying "move water from the first jug indo the second jug". It should return in this case, 183 since only 3 units from the first jug can be poured into the second.

int moveWater(int index, int srcJug, int dstJug)
{
    if (srcJug == dstJug)
    {
        return index;
    }

    JugState js = getJugStateFromIndex(index);

    // how much water is in the source jug
    int sourceAmount = js.jugs[srcJug];

    // how much water is in the destination jug
    int dstAmount = js.jugs[dstJug];

    // how much more water can the destination jug take
    int maxTransfer = (dstJug == 0) ? 12 : ((dstJug == 1) ? 8 : 5) - dstAmount;

    // how much to actually move
    int transfer = (sourceAmount >= maxTransfer) ? maxTransfer : sourceAmount;

    js.jugs[srcJug] -= transfer;
    js.jugs[dstJug] += transfer;

    return getIndexFromJugState(js);
}

Now we can think of this problem as a graph. Given any state such as {4,5,3} (index == 453) and we want to test if it's possible to transition to {7,1,4} (index == 714). At any given state, there are 6 valid transitions that can be made. (i.e. move water from jug0->jug1, jug0->jug2, ..., jug2->jug0). So we can just use a set to keep track of what node indices we've visited so that we don't recurse indefinitely. The cool part of this tree traversal is that we don't need to build an actual tree.

bool canTransitionExist(int startIndex, int endIndex, unordered_set<int>& visited)
{
    if (startIndex == endIndex)
    {
        return true;
    }

    // visit the start state
    visited.insert(startIndex);

    // there's 6 possible candidate states to transition to
    int candidates[6];
    candidates[0] = moveWater(startIndex, 0, 1);
    candidates[1] = moveWater(startIndex, 0, 2);
    candidates[2] = moveWater(startIndex, 1, 0);
    candidates[3] = moveWater(startIndex, 1, 2);
    candidates[4] = moveWater(startIndex, 2, 0);
    candidates[5] = moveWater(startIndex, 2, 1);

    // let's try visiting each one of these if we haven't visited before
    for (int i = 0; i < 6; i++)
    {
        // don't visit nodes we've seen before
        if (visited.count(candidates[i]) == 0)
        {
            bool result = canTransitionExist(candidates[i], endIndex, visited);
            if (result)
            {
                return true;
            }
        }
    }
    return false;
}

bool canTransitionExist(int startIndex, int endIndex)
{
    std::unordered_set<int> visited;
    return canTransitionExist(startIndex, endIndex, visited);
}

Now let's introduce 2 helper functions. One function to help us build up that initial set of 53 valid jug states with 12 units of water. This function is aware of the 12/8/5 limits on the jugs. But you can pass it any target state amount you want.

void getValidJugStates(int targetAmount, vector<int>& validStates)
{
    for (int i = 0; i <= 12; i++)
    {
        for (int j = 0; j <= 8; j++)
        {
            for (int k = 0; k <= 5; k++)
            {
                if ((i + j + k) == targetAmount)
                {
                    JugState js = { i,j,k };
                    validStates.push_back(getIndexFromJugState(js));
                }
            }
        }
    }
}

And a helper function to make a string representation of a jug state:

std::string getStringFromIndex(int index)
{
    auto js = getJugStateFromIndex(index);
    std::string s = "{";
    s += std::to_string(js.jugs[0]) + "," + std::to_string(js.jugs[1]) +  "," + std::to_string(js.jugs[2]);
    s += "}";
    return s;
}

Now we have enough to code up a test for all 2756 combinations of transitions for the 12 units of water configurations.

int main()
{
    vector<int> validStates;

    const int capacityAmount = 12;
    getValidJugStates(capacityAmount, validStates);

    std::cout << "there are: " << validStates.size() << " initial starting states of jugs with " << capacityAmount << " units total\n";

    size_t testIndex = 0;

    for (size_t i = 0; i < validStates.size(); i++)
    {
        for (size_t j = 0; j < validStates.size(); j++)
        {
            if (i == j)
            {
                continue;
            }

            int start = validStates[i];
            int end = validStates[j];

            bool success = canTransitionExist(start, end);

            std::cout << "Test number " << testIndex << ": ";
            testIndex++;

            if (success)
            {
                std::cout << "valid path from " << getStringFromIndex(start) << " to " << getStringFromIndex(end) << endl;
            }
            else
            {
                std::cout << "there is not a path from " << getStringFromIndex(start) << " to " << getStringFromIndex(end) << endl;
            }
        }
    }

    return 0;
}

Run our code (here's a snippet)...

...
...
Test number 1968: there is not a path from {7,5,0} to {9,2,1}
Test number 1969: valid path from {7,5,0} to {9,3,0}
Test number 1970: valid path from {7,5,0} to {10,0,2}
Test number 1971: there is not a path from {7,5,0} to {10,1,1}
Test number 1972: valid path from {7,5,0} to {10,2,0}
Test number 1973: valid path from {7,5,0} to {11,0,1}
Test number 1974: valid path from {7,5,0} to {11,1,0}
Test number 1975: valid path from {7,5,0} to {12,0,0}
Test number 1976: valid path from {8,0,4} to {0,7,5}
Test number 1977: valid path from {8,0,4} to {0,8,4}
Test number 1978: valid path from {8,0,4} to {1,6,5}
Test number 1979: there is not a path from {8,0,4} to {1,7,4}
Test number 1980: valid path from {8,0,4} to {1,8,3}
Test number 1981: valid path from {8,0,4} to {2,5,5}
Test number 1982: there is not a path from {8,0,4} to {2,6,4}
Test number 1983: there is not a path from {8,0,4} to {2,7,3}
...
...

You can get the complete listing here:

https://github.com/jselbie/threejugproblem/blob/main/main.cpp