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

Question

Note. I came across the question below, and I wanted to generalize the problem and implement it, but it turns out that this is not easy. This question makes me go crazy. This is not a matter of homework, just curiosity.

Question

There are three containers that are 10 pints, 7 pints and 4 pints respectively. Containers with 7 pints and 4 pints start with water, but a container of 10 pints is initially empty.

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

• source container is empty
• destination container is full.

What sequence of actions should you do if you want to isolate exactly 2 pints of water?

Source: page 102, question 3.8

Decision

The answer to this question is easy using a directional graph structure , where the nodes contain tuples to represent a specific state.

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

• The structure of each state (or node): <10-pint container, 7-pint container, 2-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 in the picture.

Generalized question

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

The y-pint and z-pint containers start with water, but the x-pint container is initially empty.

What sequence of actions should you do if you want to isolate precisely pints of water?

We offer a solution for the generalized version

Here ( DropBox , GitHub ) is my source code.

Here are two important methods in the main class. They populate a graph based on all the features, and it also ensures that 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 simply fills the chart to a depth of 4, but how can I set the depth and make it work recursively or how to make it work until all the possibilities are considered without going into an infinite loop. What is the algorithm for this generalized question?

Answer 1

Hm ... there may be better algorithms, but if you just want arbitrarily deep recursion without going into infinite loops, you can use the first width search that visits each node only once, i.e. if he has not 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); } } 

Answer 2

You can also try an iterative in-depth search, we were given a demonstration of his work on the same problem in uni, and it worked well.