Having 3 containers (2 full and 1 empty) and trying to create x amount from them

Question

Note: I came across the question below and I wanted to generalize the problem and implement it, but it turns out that it is not easy. This question is making me crazy. This is NOT a Homework question just a curiosity.

Question

There are three containers whose sizes are 10 pints, 7 pints and 4 pints respectively. The 7-pint and 4-pint containers start out full of water, but the 10-pint container is initially empty.

Since there are no marks on the containers, you can pour the contents of one container into another and stop under the following conditions:

1. the source container is empty
2. the destination container is full

What sequence of moves should you make if you want to isolate exactly 2 pints of water?

Source: page 102, Question 3.8

Solution

Answering that question is easy using directed graph data structure where nodes contain tuples to represent a certain state.

We start from the initial state (node), and then we create a node representing a possible next state, and we connect it to initial node, and then run BFS to find the shortest path.

• Pattern of each state (or node): <10-pint container, 7-pint container, 4-pint container>

• Initial state or node: <0, 7, 4>.

The nodes connected to the initial state (or node): <7, 0, 4>, <4, 7, 0>, as you can see from the picture.

Generalised Question

But suppose if want to generalized the problem, suppose we have three containers whose sizes are x, y and z pints respectively such that x >= y >= z.

The y-pint and z-pint containers start out full of water but the x-pint container is initially empty.

What sequence of moves should you make if you want to isolate exactly a pints of water?

Suggesting a Solution to Generalised Version

Here (DropBox, GitHub) is my source code so far.

Here are two important method in main class. They fill the graph based on all possibilities, and it also makes sure there is no duplicate node.

public static void fillGraph(int x, int y, int z) {

    TupleContainer initialState = new TupleContainer(x, y, z);
    TupleContainer currentState = initialState;
    Iterator<TupleContainer> it, it_1, it_2, it_3;
    Graph.addNode(initialState);

    it = addAdjacentEdgesToTuple(currentState).iterator();
    while (it.hasNext()) {
        it_1 = addAdjacentEdgesToTuple(it.next()).iterator();
        while (it_1.hasNext()) {
            it_2 = addAdjacentEdgesToTuple(it.next()).iterator();
            while (it_2.hasNext()) {
                it_3 = addAdjacentEdgesToTuple(it.next()).iterator();
                while (it_3.hasNext()) {
                    addAdjacentEdgesToTuple(it.next()).iterator();
                }
            }
        }
    }

public static Collection<TupleContainer> addAdjacentEdgesToTuple(
        TupleContainer currentState) {
    TupleContainer tempTupleContainer;
    Collection<TupleContainer> CollectionLevel;
    Iterator<TupleContainer> it;

    CollectionLevel = currentState.MixUpContainers();
    it = CollectionLevel.iterator();

    while (it.hasNext()) {
        tempTupleContainer = it.next();
        if (graphContains(tempTupleContainer) != null)
            Graph.addNode(tempTupleContainer);
        else
            tempTupleContainer = graphContains(tempTupleContainer);
        Graph.addEdge(currentState, tempTupleContainer);
    }
    return CollectionLevel;
}

My Question

My code just fills the graph to depth of 4, but how can I set depth and make it run recursively or how make it run until all possibilities are taken to consideration without going into infinite loop. What is the algorithm to this generalized question?

Answer 1

Hm ... there may be better algorithms, but if you simply want arbitrarily deep recursion without going into endless loops, you can use a breadth first search that visits each node only once, i.e. if it hasn't already been visited:

public class Test {

    public static void main(String[] args) throws Exception {
        State initialState = new State(null, 0, 7, 4);

        Set<State> reached = new HashSet<>();
        Queue<State> pending = new ArrayDeque<>();
        pending.add(initialState);
        while (!pending.isEmpty()) {
            State state = pending.remove();

            if (isGoal(state)) {
                printPathTo(state);
                return;
            }

            for (State s : state.adjacentStates()) {
                if (!reached.contains(s)) {
                    reached.add(s);
                    pending.add(s);
                }
            }
        }

        System.out.println("There appears to be no solution.");
    }

    private static boolean isGoal(State state) {
        for (int a : state.content) {
            if (a == 2) {
                return true;
            }
        }
        return false;
    }

    private static void printPathTo(State state) {
        if (state != null) {
            printPathTo(state.previous);
            System.out.println(state);
        }
    }
}

class State {

    final static int[] capacity = { 10, 7, 4 };

    final int[] content;
    final State previous;

    public State(State previous, int... content) {
        this.content = content;
        this.previous = previous;
    }

    Iterable<State> adjacentStates() {
        List<State> result = new ArrayList<>();
        for (int i = 0; i < content.length; i++) {
            for (int j = 0; j < content.length; j++) {
                if (i != j) {
                    int[] newContent = Arrays.copyOf(content, content.length);
                    int movedQuantity = Math.min(content[i], capacity[j] - content[j]);
                    newContent[i] -= movedQuantity;
                    newContent[j] += movedQuantity;
                    result.add(new State(this, newContent));
                }
            }
        }
        return result;
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(content);
    }

    @Override
    public boolean equals(Object obj) {
        return Arrays.equals(content, ((State) obj).content);
    }

    @Override
    public String toString() {
        return Arrays.toString(content);
    }
}