Write a Java program which implements Breadth-First Search and Depth-First Search algorithms to find a solution for the Water Jugs Problem. The start state is (0, 0); goal states are (2, *) (either state (2, 0) or state (2, 3)). To keep things simple, a Node class is provided for you. (You can find the file Node.java on Blackboard). In this class, the method expand() generates all possible successors of one node and returns the list of all successors. You need to write a new class named WaterJugs to implement and test your algorithms.

Requirements:

1) Create a method BFS that applies the Breadth-Frist search.

2) Create a method DFS that applies the Depth-First search.

3) Output the path from the start state to the goal state.

4) Your program should be able to avoid repeated states in order to find the goal state.

5)Add a counter to your methods that keeps track of how many nodes were created during a computation, as a measure of the algorithms efficiency. Let the program output that number.

6) Your program should be well-documented. Variable names and function names should be self-descriptive. Major functions should be explained clearly in comments.

7) Test your program. Make sure your program compiles and runs correctly.

NODE CLASS

import java.util.ArrayList;

public class Node { public final int CAPACITY_X = 4; public final int CAPACITY_Y = 3; private int x; private int y; private Node parent; /** * constructor method * @param x - water volume in first jug * @param y - water volume in second jug */ public Node(int x, int y) { this.x = x; this.y = y; this.parent = null; } /** * * @return the current water volume in first jug */ public int getX() { return x; } /** * * @return the current water volume in second jug */ public int getY() { return y; } /** * * @return the parent state */ public Node getParent() { return parent; } /** * set the parent state of the current node * @param parent */ public void setParent(Node parent) { this.parent = parent; } /** * * @return the set of successors of current node */ public ArrayList expand(){ ArrayList children = new ArrayList(); Node child; //fill the first jug if(x < CAPACITY_X) { child = new Node(CAPACITY_X, y); child.setParent(this); children.add(child); } //fill the second jug if(y < CAPACITY_Y) { child = new Node(x, CAPACITY_Y); child.setParent(this); children.add(child); } if(x > 0){ //empty the first jug child = new Node(0, y); child.setParent(this); children.add(child); //pour water from first jug to second jug if(y < CAPACITY_Y) { int yNew = Math.min(x+y, CAPACITY_Y); int xNew = x - (yNew - y); child = new Node(xNew, yNew); child.setParent(this); children.add(child); } } if(y > 0){ //empty second jug child = new Node(x, 0); child.setParent(this); children.add(child); //pour water from second jug to first jug if(x < CAPACITY_X) { int xNew = Math.min(x+y, CAPACITY_X); int yNew = y - (xNew - x); child = new Node(xNew, yNew); child.setParent(this); children.add(child); } } return children; } @Override public boolean equals(Object object) { boolean result = false; if(object == null || object.getClass() != getClass()) result = false; else { Node state = (Node) object; if(this.x == state.getX() && this.y == state.getY()) result = true; } return result; } /** * Express the state in a string */ public String toString() { return "(" + x + ", " + y + ")"; } }