Pouring Water
  1. /** Node in Pouring Water Problem
  2.  * @author Lin Chen
  3.  * @since 11.13.2017
  4.  */
  5. public class Node
  6. {
  7. 	private int a = 10, b = 7, c = 4;//size of containers
  8. 	private int A, B, C;//real water volume in container
  9. 	private Node prev;//predecessor
  10.  
  11. 	public Node(int A, int B, int C)
  12. 	{
  13. 		this.A = A;
  14. 		this.B = B;
  15. 		this.C = C;
  16. 		prev = null;
  17. 	}
  18.  
  19. 	public int getA() {return A;}
  20. 	public int getB() {return B;}
  21. 	public int getC() {return C;}
  22. 	public int geta() {return a;}
  23. 	public int getb() {return b;}
  24. 	public int getc() {return c;}
  25. 	public Node getPrev() {return prev;}
  26.  
  27. 	public void setA(int A) {this.A = A;}
  28. 	public void setB(int B) {this.B = B;}
  29. 	public void setC(int C) {this.C = C;}
  30. 	public void setPrev(Node n) {prev = n;}
  31.  
  32. 	@Override
  33. 	public boolean equals(Object n)
  34. 	{
  35. 		Node temp = (Node)n;
  36. 		if((A == temp.A) && (B == temp.B) && (C == temp.C))
  37. 			return true;
  38.  
  39. 		return false;
  40. 	}
  41.  
  42. 	@Override
  43. 	public int hashCode()
  44. 	{
  45. 		return A+B*10+C*100;
  46. 	}
  47.  
  48. 	public String toString()
  49. 	{
  50. 		return "("+A+"/"+a+","+B+"/"+c+","+C+"/"+c+")";
  51. 	}
  52. }
  53. 			
  1. /** Program to demo pouring water
  2.  * @author Lin Chen
  3.  * @since 11.13.2017
  4.  */
  5. import java.util.*;
  6. import javafx.util.*;
  7.  
  8. public class P
  9. {
  10. 	/** Calculate the remaining water after pouring water from A to B
  11. 	 * @param A volume of water in container A
  12. 	 * @param B volume of water in container B
  13. 	 * @param a volume of container A
  14. 	 * @param b volume of container B
  15. 	 * @return (volume in A, volume in B)
  16. 	 */
  17. 	public static Pair<Integer, Integer> pouring(int A, int B, int a, int b)
  18. 	{
  19. 		int tempA, tempB;
  20. 		if((b-B) > A)
  21. 		{
  22. 			tempA = 0;
  23. 			tempB = B+A;
  24. 		}
  25. 		else
  26. 		{
  27. 			tempB = b;
  28. 			tempA = A - (b-B);
  29. 		}
  30.  
  31. 		return new Pair<Integer, Integer>(tempA, tempB);
  32. 	}
  33.  
  34. 	/** Pouring water operation
  35. 	 * @param A volume of water in A
  36. 	 * @param B volume of water in B
  37. 	 * @param C volume of water in C
  38. 	 * @param A volume of container A
  39. 	 * @param B volume of container B
  40. 	 * @param C volume of container C
  41. 	 * @param direction pouring direction
  42. 	 * @return {@code Node}, a node from the operation
  43. 	 */
  44. 	public static Node pouringWater(int A, int B, int C, int a, int b, int c, String direction)
  45. 	{
  46. 		if(direction.equals("AB"))
  47. 		{
  48. 			Pair<Integer, Integer> p = pouring(A, B, a, b);
  49. 			return new Node(p.getKey(), p.getValue(), C);
  50. 		}
  51. 		else if(direction.equals("AC"))
  52. 		{
  53. 			Pair<Integer, Integer> p = pouring(A, C, a, c);
  54. 			return new Node(p.getKey(), B, p.getValue());
  55. 		}
  56. 		else if(direction.equals("BC"))
  57. 		{
  58. 			Pair<Integer, Integer> p = pouring(B, C, b, c);
  59. 			return new Node(A, p.getKey(), p.getValue());
  60. 		}
  61. 		else if(direction.equals("BA"))
  62. 		{
  63. 			Pair<Integer, Integer> p = pouring(B, A, b, a);
  64. 			return new Node(p.getValue(), p.getKey(), C);
  65. 		}
  66. 		else if(direction.equals("CA"))
  67. 		{
  68. 			Pair<Integer, Integer> p = pouring(C, A, c, a);
  69. 			return new Node(p.getValue(), B, p.getKey());
  70. 		}
  71. 		else if(direction.equals("CB"))
  72. 		{
  73. 			Pair<Integer, Integer> p = pouring(C, B, c, b);
  74. 			return new Node(A, p.getValue(), p.getKey());
  75. 		}
  76. 		else
  77. 			return null;
  78. 	}
  79.  
  80. 	/** Check if the pouring from A to B is a valid operation
  81. 	 * @param A volume of water in A
  82. 	 * @param B volume of water in B
  83. 	 * @param a volume of container A
  84. 	 * @param b volume of container B
  85. 	 * @return {@code true}, valide; {@code false}, otherwise
  86. 	 */
  87. 	public static boolean isValid(int A, int B, int a, int b)
  88. 	{
  89. 		if(A <= 0)
  90. 			return false;
  91. 		if(B >= b)
  92. 			return false;
  93. 		return true;
  94. 	}
  95.  
  96. 	/** Search all children of the current node, if they are valid and not visited, push into queue
  97. 	 * @param q a queue of Node
  98. 	 * @param u current node
  99. 	 * @param m hash table to check if the node has been visited
  100. 	 */
  101. 	public static void addChildren(Queue<Node> q, Node u, HashMap<Node, Integer> m)
  102. 	{
  103. 		int A, B, C, a, b, c;
  104. 		A = u.getA();
  105. 		B = u.getB();
  106. 		C = u.getC();
  107. 		a = u.geta();
  108. 		b = u.getb();
  109. 		c = u.getc();
  110.  
  111. 		Node v;
  112. 		if(isValid(A, B, a, b))
  113. 		{
  114. 			v = pouringWater(A, B, C, a, b, c, "AB");
  115. 			v.setPrev(u);
  116. 			if(!m.containsKey(v))
  117. 			{
  118. 				q.add(v);
  119. 				m.put(v, 0);
  120. 			}
  121. 		}
  122. 		if(isValid(A, C, a, c))
  123. 		{
  124. 			v = pouringWater(A, B, C, a, b, c, "AC");
  125. 			v.setPrev(u);
  126. 			if(!m.containsKey(v))
  127. 			{
  128. 			q.add(v);
  129. 				m.put(v, 0);
  130. 			}
  131. 		}
  132. 		if(isValid(B, A, b, a))
  133. 		{
  134. 			v = pouringWater(A, B, C, a, b, c, "BA");
  135. 			v.setPrev(u);
  136. 			if(!m.containsKey(v))
  137. 			{
  138. 				q.add(v);
  139. 				m.put(v, 0);
  140. 			}
  141. 		}
  142. 		if(isValid(B, C, b, c))
  143. 		{
  144. 			v = pouringWater(A, B, C, a, b, c, "BC");
  145. 			v.setPrev(u);
  146. 			if(!m.containsKey(v))
  147. 			{
  148. 				q.add(v);
  149. 				m.put(v, 0);
  150. 			}
  151. 		}
  152. 		if(isValid(C, A, c, a))
  153. 		{
  154. 			v = pouringWater(A, B, C, a, b, c, "CA");
  155. 			v.setPrev(u);
  156. 			if(!m.containsKey(v))
  157. 			{
  158. 				q.add(v);
  159. 				m.put(v, 0);
  160. 			}
  161. 		}
  162. 		if(isValid(C, B, c, b))
  163. 		{
  164. 			v = pouringWater(A, B, C, a, b, c, "CB");
  165. 			v.setPrev(u);
  166. 			if(!m.containsKey(v))
  167. 			{
  168. 				q.add(v);
  169. 				m.put(v, 0);
  170. 			}
  171. 		}
  172. 	}
  173.  
  174. 	/** Check if the current node is the target node
  175. 	 * @param u node
  176. 	 * @param target target volume
  177. 	 * @return {@code true}, target node; {@code false}, otherwise
  178. 	 */
  179. 	public static boolean checkNode(Node u, int target)
  180. 	{
  181. 		if(u.getA() == target)
  182. 			return true;
  183. 		if(u.getB() == target)
  184. 			return true;
  185. 		if(u.getC() == target)
  186. 			return true;
  187. 		return false;
  188. 	}
  189.  
  190. 	/** Breadth First Search all possible nodes
  191. 	 * @param s start node
  192. 	 * @param target target volume of water
  193. 	 * @return target node
  194. 	 */
  195. 	public static Node BFS(Node s, int target)
  196. 	{
  197. 		Queue<Node> q = new LinkedList<Node>();
  198. 		HashMap<Node, Integer> m = new HashMap<Node, Integer>();
  199.  
  200. 		q.add(s);
  201. 		m.put(s, 0);
  202.  
  203. 		while(!q.isEmpty())
  204. 		{
  205. 			Node u = q.poll();
  206. 			if(checkNode(u, target))
  207. 				return u;
  208. 			addChildren(q, u, m);
  209. 		}
  210.  
  211. 		return null;
  212. 	}
  213.  
  214. 	/** print path finding the target node
  215. 	 * @param u target node
  216. 	 */
  217. 	public static void printNode(Node u)
  218. 	{
  219. 		if(u == null)
  220. 			return;
  221. 		printNode(u.getPrev());
  222. 		System.out.println(u);
  223. 	}
  224.  
  225. 	public static void main(String args[])
  226. 	{
  227. 		Node s = new Node(0, 7, 4);
  228.  
  229. 		Node t = BFS(s, 2);
  230.  
  231. 		printNode(t);
  232. 	}
  233. }
  234.