CSCI/CMPE 3326 Spring 2018 Program 2: Two empty water buckets A and B with diffe
ID: 3708283 • Letter: C
Question
CSCI/CMPE 3326 Spring 2018 Program 2: Two empty water buckets A and B with different capacities. These water buckets can be repeatedly filled with water and emptied in order to fill the water buckets with the desired amount of water There is no way to accurately measure the amount except using the water buckets. There are three possible types of tasks F(x): Fill x]: Water bucket x is fully filled with water. (Before filling, the water bucket x may be empty or not) E(x): Empty x]: make water bucket x empty M(x.y): Move water from x to y): Pour water from bucket x into bucket y. If the amount of water in the water bucket x is less than or equal to the space remaining in the water bucket y, we can pour the whole water in the water bucket x into the water bucket y. If the amount of water in the bucket x is greater than the empty space remaining in the bucket y, we can pour as much as possible to fill the water bucket y and leave the rest in the water bucket x. For example, let's say that the capacity of water buckets A and B is 2 liters and 5 liters, respectively. If you want to leave 2 liters of water in the bucket A and 4 liters of water in the bucket B, you can reach the desired state with 8 operations in total as follows (0,0) IF(B) (0,5) IM(B,A) (2,3) [E(A) (0,3) IM(B,A) (2,1)-E(A) (0,1) M(B A) (1,0) F(B) 1,5) IM(B.A)(2,4) However, if the work order is as follows, the total number of jobs required is 5 times. (0,0) IF(A)(2,0) IM(A,B) (0,2) [F(A)] (2,2) M(A,B) (0,4)-IF(A)(2,4) Write a program that receives the capacity of both buckets and the desired final state as input, and then finds the minimum number of jobs/operations to reach the final state desired. It starts from the state that both buckets are empty Input format Number of test case Capacity_of_bucket_A Capacity_of_bucket B Desired_state_of_Bucket A Desired_stateof_Bucket B Output format Number of operations Example of input file (input.txt) 37 32 250 1 3 5 24 Example of output -1Explanation / Answer
CODING :
Hi, your code is running if you include the dlange package file GraphSolver.
Here it s:
package dlange;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
/**
* Generic Graph solver with implementation for blind BFS
*
* @author dlange
*
* @param <T>
*/
public class GraphSolver<T> {
// cross-cutting field used to prune graph (only used if blind transitions)
private Map<String,String> exists;
// cross-cutting field used to backtrack from target to root when generating solution output
private Map<GraphNode<T>, GraphNode<T>> path;
/**
* Generic Bredth First Search given a root node in a graph, a goal node to search for, and an object
* which generates transition states from a given state.
* Answer back List<T> representing the path of <T> states from root to solution.
*
* @see http://en.wikipedia.org/wiki/Breadth-first_search
*
* @param root
* @param goal
* @param transition
* @return
*/
public List<T> bfs(T root, Goal<T> goal, Transition<T> transition) {
initCollections();
// queue to hold successor nodes
Queue<GraphNode<T>> queue = new LinkedList<GraphNode<T>>();
// root node
GraphNode<T> start = new GraphNode<T>(root);
// begin by marking root visited and enqueing
visit(start, null);
queue.offer(start);
// continue until queue empty
while (queue.size() > 0) {
GraphNode<T> f = queue.remove();
// trival test
if (goal.isGoal(f.data)) {
return buildSolution(f);
}
// blind BFS uses transition object to generate edges to this node on the fly
populateEdges(f, transition);
// traverse these generated edges
for (GraphNode<T> edge : f.edges) {
// if not visited, visit and queue
if (!edge.visited) {
visit(edge, f);
queue.offer(edge);
// check for goal
if (goal.isGoal(edge.data)) {
return buildSolution(edge);
}
}
}
}
// by contract return empty list if target not found
return new ArrayList<T>();
}
/**
* The fields initialized below should be scoped to the bfs() method to keep it stateless; however, for
* readability of the bfs algorithm they are defined as fields and always initialized here. They are not
* central to BFS but support pruning and output generation.
*/
private void initCollections() {
exists = new HashMap<String,String>();
path = new HashMap<GraphNode<T>, GraphNode<T>>();
}
/**
* Generate transition state nodes from given node using given Transition object.
* Use the exists Map to prune previously traversed states. Add un-pruned nodes
* to the given node as an edge.
*
* @param node
* @param transition
*/
private void populateEdges(GraphNode<T> node, Transition<T> transition) {
// successor states
for (T mixture : transition.transitions((T)node.data)) {
String key = mixture.toString();
if (!exists.containsKey(key)) {
exists.put(key, key);
node.addEdge(new GraphNode<T>(mixture));
}
}
}
/**
* Starting at given target node and working backwards until root reached, add each node's data
* to a collection. Reverse the collection to represent the forward sequence of data.
*
* @param target
* @return
*/
private List<T> buildSolution(GraphNode<T> target) {
List<T> solution = new ArrayList<T>();
while (null != target) {
solution.add((T) target.data);
target = path.get(target);
}
Collections.reverse(solution);
return solution;
}
/**
* helper method ot mark node visited. Add to path.
*
* @param node
* @param parent
*/
private void visit(GraphNode<T> node, GraphNode<T> parent) {
node.visited = true;
path.put(node, parent);
}
/**
* Class representing a node of a graph. The node contains a collection of connected nodes representing the
* nodes directly connected to this node via an edge. The node also contains a generic data type and a flag
* to mark if it was visited by a search algorithm.
*
* @author dlange
*
* @param <T>
*/
class GraphNode<T> {
List<GraphNode<T>> edges = new ArrayList<GraphNode<T>>();
T data;
boolean visited;
public GraphNode(T data) {
this.data = data;
this.visited = false;
}
public void addEdge(GraphNode<T> node) {
this.edges.add(node);
}
}
/**
* Interface for identifying transitions from a given node
*
* @author dlange
*
* @param <T>
*/
public interface Transition<T> {
List<T> transitions(T root);
}
/**
* Interface for identifying if given candidate node satisfied goal state
*
* @author dlange
*
* @param <T>
*/
public interface Goal<T> {
boolean isGoal(T candidate);
}
}