The water jug problem

We have three water jugs, and each can hold 3oz., 5oz., and 8oz. of water, respectively.
Without the possibility of water spilling when poured from one jug to another, and given that the jugs have no calibration, how do we divide the 8oz. of water equally among two jugs?


We will define a class named State holding the capacity of A and B jars.
It should be noted that only 2 jars are sufficient to define a state, as water held in third jar can be calculated by subtracting the sum of two from the total.

Define class State like this...

package mystate;
import bfs.threejugproblem.NotSupportedException;
import java.util.ArrayList;
import java.util.List;
public class State
{
    int a=0;//3
    int b=0;//5
    int c=8;//8

    public State(int a, int b)
    {
        this.a=a;
        this.b=b;
        this.c=8-a-b;
    }
    public boolean isGoal()
    {
        return (b==4 && c==4);
    }
    public boolean equals(Object xx)
    {
        State x = (State) xx;
        if(this.a==x.a && this.b==x.b && this.c==x.c)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    public int hashCode()
    {
        return 8;
    }
    public List<State> getChildren() 
    {
        List<State> children = new ArrayList<State>();
        // a -> b
        if(a!=0 && b!=5)// if a is not empty
        {
            if(a+b<=5)
            {
                children.add(new State(0, a+b));
            }
            else
            {
                children.add(new State(a+b-5,5));
            }
        }
        //a->c
        if(a!=0 && c!=8)
        {
            // We are pouring completely from a to c
            // a will be 0
            // b will be 8-a-c
            // c will be a+c
            children.add(new State(0, 8-a-c));
        }
        //b->a
        if(b!=0 && a!=3)
        {
            if(a+b<=3)
            {
                children.add(new State(a+b, 0));
            }
            else
            {
                children.add(new State(3, a+b-3));
            }
        }
        // b->c
        if(b!=0 && c!=8)
        {
            // We are pouring completely from b to c
            // a will be 8-b-c
            // b will be 0
            // c will be b+c
            children.add(new State(8-b-c, 0));            
        }
        //c->a
        if(c!=0 && a!=3)
        {
            if(c+a<=3)
            {
                children.add(new State(c+a, 8-c-a));
            }
            else
            {
                    // a will be full i.e. 3 liters
                    // b will be 8-c-a
                    // c will be c+a-3
                    children.add(new State(3, 8-c-a));
                
            }
        }
        // c->b
        if(c!=0 && b!=5)
        {
            if(c+b<=5)
            {
                children.add(new State(8-c-b , c+b));
            }
            else
            {
                children.add(new State(8-c-b, 5));
            }
        }
        return children;
    }
    @Override
    public String toString()
    {
        return "{"+a+","+b+","+c+"}";
    }
}

Depth First Search Algorithm

public class DFSThreeJugProblem 
{
    public static void main(String[] args)
    {
        State currentState = new State(0,0);
        List<State> visitedStates=new ArrayList<State>();  
        // Check if the current State has a solution
        // given a set of visited States.
        dfs(currentState, visitedStates);
    }
    public static void dfs(State currentState, List<State> vStates)
    {
        // if it is GOAL
        if(currentState.isGoal())
        {
            // That's it we are done.
            for(State v : vStates)
            {
                System.out.println(v);
                System.out.println(currentState);
            }
            System.exit(0);            
        }
        
        // if visisted state contains currentState, then just return.
        // This is the wrong branch, and we need not traverse it further.
        if(vStates.contains(currentState))
            return;
        
        // Add current state to visited states.
        vStates.add(currentState);        
        
        // Make clone of visited states.
        List<State> clonedVStates = new ArrayList<State>(vStates);
        // Find the set of possible children of current state.
        List<State> children = currentState.getChildren();
        for(State c : children)
        {
            // if a children C is not in the visited states 
            // again call DFS on current child and visited States.
            if(!clonedVStates.contains(c))
            {
                dfs(c, clonedVStates);
            }
        }
    }
}

Breadth First Search algorithm...

public class BFSThreeJugProblem 
{
    private static List<State> visitedStates=new ArrayList<State>();
    private static Queue<State> stateQueue = new LinkedList<State>();
    public static void main(String[] args) throws NotSupportedException 
    {
        State currentState = new State(0,0);
        // Add current state to state Queue.
        stateQueue.add(currentState);
        do
        {
            // Get the first Element from Queue.
            State firstElementInQueue = stateQueue.peek();
            // If the first Element is the Goal
            // We are done.
            if(firstElementInQueue.isGoal())
            {
                for(State p : visitedStates)
                {
                    System.out.println(p.toString());
                }
                // There is no recursion here, so simple return would do.
                return;
            }
            else
            {
                // Add firstElement to visited States
                visitedStates.add(firstElementInQueue);    
                // Get the children of first element
                List<State> children = firstElementInQueue.getChildren();
                for(State v : children)
                {
                    // if children has not already been visited.
                    if(!visitedStates.contains(v))
                    {
                        // add the child to state Queue.
                        stateQueue.add(v);
                    }
                }
                // Remove the first element from state queue.
                stateQueue.remove(firstElementInQueue);
            }
            // do this till state queue is empty.
        }while(!stateQueue.isEmpty());
    }
}