/** Node in Pouring Water Problem
* @author Lin Chen
* @since 11.13.2017
*/
public class Node
{
private int a = 10, b = 7, c = 4;//size of containers
private int A, B, C;//real water volume in container
private Node prev;//predecessor
public Node(int A, int B, int C)
{
this.A = A;
this.B = B;
this.C = C;
prev = null;
}
public int getA() {return A;}
public int getB() {return B;}
public int getC() {return C;}
public int geta() {return a;}
public int getb() {return b;}
public int getc() {return c;}
public Node getPrev() {return prev;}
public void setA(int A) {this.A = A;}
public void setB(int B) {this.B = B;}
public void setC(int C) {this.C = C;}
public void setPrev(Node n) {prev = n;}
@Override
public boolean equals(Object n)
{
Node temp = (Node)n;
if((A == temp.A) && (B == temp.B) && (C == temp.C))
return true;
return false;
}
@Override
public int hashCode()
{
return A+B*10+C*100;
}
public String toString()
{
return "("+A+"/"+a+","+B+"/"+c+","+C+"/"+c+")";
}
}
/** Program to demo pouring water
* @author Lin Chen
* @since 11.13.2017
*/
import java.util.*;
import javafx.util.*;
public class P
{
/** Calculate the remaining water after pouring water from A to B
* @param A volume of water in container A
* @param B volume of water in container B
* @param a volume of container A
* @param b volume of container B
* @return (volume in A, volume in B)
*/
public static Pair<Integer, Integer> pouring(int A, int B, int a, int b)
{
int tempA, tempB;
if((b-B) > A)
{
tempA = 0;
tempB = B+A;
}
else
{
tempB = b;
tempA = A - (b-B);
}
return new Pair<Integer, Integer>(tempA, tempB);
}
/** Pouring water operation
* @param A volume of water in A
* @param B volume of water in B
* @param C volume of water in C
* @param A volume of container A
* @param B volume of container B
* @param C volume of container C
* @param direction pouring direction
* @return {@code Node}, a node from the operation
*/
public static Node pouringWater(int A, int B, int C, int a, int b, int c, String direction)
{
if(direction.equals("AB"))
{
Pair<Integer, Integer> p = pouring(A, B, a, b);
return new Node(p.getKey(), p.getValue(), C);
}
else if(direction.equals("AC"))
{
Pair<Integer, Integer> p = pouring(A, C, a, c);
return new Node(p.getKey(), B, p.getValue());
}
else if(direction.equals("BC"))
{
Pair<Integer, Integer> p = pouring(B, C, b, c);
return new Node(A, p.getKey(), p.getValue());
}
else if(direction.equals("BA"))
{
Pair<Integer, Integer> p = pouring(B, A, b, a);
return new Node(p.getValue(), p.getKey(), C);
}
else if(direction.equals("CA"))
{
Pair<Integer, Integer> p = pouring(C, A, c, a);
return new Node(p.getValue(), B, p.getKey());
}
else if(direction.equals("CB"))
{
Pair<Integer, Integer> p = pouring(C, B, c, b);
return new Node(A, p.getValue(), p.getKey());
}
else
return null;
}
/** Check if the pouring from A to B is a valid operation
* @param A volume of water in A
* @param B volume of water in B
* @param a volume of container A
* @param b volume of container B
* @return {@code true}, valide; {@code false}, otherwise
*/
public static boolean isValid(int A, int B, int a, int b)
{
if(A <= 0)
return false;
if(B >= b)
return false;
return true;
}
/** Search all children of the current node, if they are valid and not visited, push into queue
* @param q a queue of Node
* @param u current node
* @param m hash table to check if the node has been visited
*/
public static void addChildren(Queue<Node> q, Node u, HashMap<Node, Integer> m)
{
int A, B, C, a, b, c;
A = u.getA();
B = u.getB();
C = u.getC();
a = u.geta();
b = u.getb();
c = u.getc();
Node v;
if(isValid(A, B, a, b))
{
v = pouringWater(A, B, C, a, b, c, "AB");
v.setPrev(u);
if(!m.containsKey(v))
{
q.add(v);
m.put(v, 0);
}
}
if(isValid(A, C, a, c))
{
v = pouringWater(A, B, C, a, b, c, "AC");
v.setPrev(u);
if(!m.containsKey(v))
{
q.add(v);
m.put(v, 0);
}
}
if(isValid(B, A, b, a))
{
v = pouringWater(A, B, C, a, b, c, "BA");
v.setPrev(u);
if(!m.containsKey(v))
{
q.add(v);
m.put(v, 0);
}
}
if(isValid(B, C, b, c))
{
v = pouringWater(A, B, C, a, b, c, "BC");
v.setPrev(u);
if(!m.containsKey(v))
{
q.add(v);
m.put(v, 0);
}
}
if(isValid(C, A, c, a))
{
v = pouringWater(A, B, C, a, b, c, "CA");
v.setPrev(u);
if(!m.containsKey(v))
{
q.add(v);
m.put(v, 0);
}
}
if(isValid(C, B, c, b))
{
v = pouringWater(A, B, C, a, b, c, "CB");
v.setPrev(u);
if(!m.containsKey(v))
{
q.add(v);
m.put(v, 0);
}
}
}
/** Check if the current node is the target node
* @param u node
* @param target target volume
* @return {@code true}, target node; {@code false}, otherwise
*/
public static boolean checkNode(Node u, int target)
{
if(u.getA() == target)
return true;
if(u.getB() == target)
return true;
if(u.getC() == target)
return true;
return false;
}
/** Breadth First Search all possible nodes
* @param s start node
* @param target target volume of water
* @return target node
*/
public static Node BFS(Node s, int target)
{
Queue<Node> q = new LinkedList<Node>();
HashMap<Node, Integer> m = new HashMap<Node, Integer>();
q.add(s);
m.put(s, 0);
while(!q.isEmpty())
{
Node u = q.poll();
if(checkNode(u, target))
return u;
addChildren(q, u, m);
}
return null;
}
/** print path finding the target node
* @param u target node
*/
public static void printNode(Node u)
{
if(u == null)
return;
printNode(u.getPrev());
System.out.println(u);
}
public static void main(String args[])
{
Node s = new Node(0, 7, 4);
Node t = BFS(s, 2);
printNode(t);
}
}