//-----------------Current code w/ erros, please fix-------------------------//
ID: 3739875 • Letter: #
Question
//-----------------Current code w/ erros, please fix-------------------------//
import java.util.List;
import java.util.ArrayList;
import dlange.GraphSolver.Transition;
import dlange.GraphSolver.Goal;
/**
* Solution to problem :
*
* to solve that given start state, a goal state, and understanding on how to generate transition states, this problem
* can be in the form of a graph search problem. for the graph Breadth First Search (BFS) search algorithm is guaranteed to find any existing solution. Generally search routines like BFS begin with a graph and traverse until goal is discovered.
* for this case where transition rules are well known and transition states dependent on initial size conditions,
* a 'blind search' is used- only a root node is given, and edge connected nodes are 'discovered' using prior knowledge
* from the problem statement (filling, pouring water into buckets, etc).
*
* Because it may be possible to propose bucket and solution sizes which will not lead to a solution, it is necessary
* to determine solvability of problem before proceeding with a BFS. This can be quickly determined by modeling the
* problem in another fashion, as a linear diophantine equation:
* ax + by = c
* where a, b are bucket sizes, c solution size, x = +/- a pours, y = +/- b pours.
* A well known condition of this equation is that if c is not a multiple of the greatest common divisor
* of a and b, then the Diophantine equation ax + by = c has no solution.
*
* Note: the parameters x and y can be calculated iteratively using the Extended Euclid algorithm; however, knowing
* the count of pours for each bucket does not directly give you a step by step approach for filling / pouring water.
* The graph approach models these steps explicitly.
*
*
*/
public class WaterBucket {
/**
* Command line to collect input and attempt solution. Standard out shows errors or result.
* @param args [water bucket size] [water bucket size] [solution size]
*/
public static void main(String[] args) {
final String Instructions = " WaterBucket [water bucket size] [water bucket size] [solution size] Sizes are positive values.";
if (3 == args.length) {
try {
// capture the three parameters
int sizeBucketA = Integer.parseInt(args[0]);
int sizeBucketB = Integer.parseInt(args[1]);
int sizeSolution = Integer.parseInt(args[2]);
// try the problem
System.out.println(new WaterBucket().tryToAttempt(sizeBucketA, sizeBucketB, sizeSolution));
} catch (NumberFormatException ie) {
System.out.println("Invalid bucket size or solution size:" + args[0]+" "+args[1]+" "+args[2]);
System.out.println(Instructions);
}
} else {
System.out.println("Requires 3 parameters, provided "+args.length+" parameters.");
System.out.println(Instructions);
}
}
/**
* Given a set of bucket and solution sizes, answer back a String containing either detailed instructions
* on hwo to arrive at solution, or a message indicating problem not solvable.
*
* @param sizeBucketA
* @param sizeBucketB
* @param sizeSolution
* @return
*/
public String tryToAttempt(int sizeBucketA, int sizeBucketB, int sizeSolution) {
if (solvableOrNot(sizeBucketA, sizeBucketB, sizeSolution)) {
return (solution(sizeBucketA, sizeBucketB, sizeSolution).verboseInstructions());
} else {
return("Provided bucket size and solution size is not solvable");
}
}
/**
* Answer back true if a solution exists; otherwise, false
* This two bucket problem can be modeled by a linear diophantine equation in form:
* Jx + Ky = G (J, K are bucket sizes, G solution size, x = +/- J pours, y = +/- K pours)
* This equation will have no solutions or many solutions.
* Tests for solvability include
*
* @param sizeBucketA
* @param sizeBucketB
* @param sizesizeSolutionution
* @return
*/
protected boolean solvableOrNot(int sizeBucketA, int sizeBucketB, int sizeSolution) {
// make sure buckets can hold solution size
if (sizeSolution > sizeBucketA && sizeSolution > sizeBucketB) {
return false;
}
// positive and limited bucket, solution sizes
if (sizeBucketA < 0 || sizeBucketB < 0 || sizeSolution < 0) {
return false;
}
// quick test 1 if left side sizes even and right side size odd, not solvable
if (sizeBucketA % 2 == 0 && sizeBucketB % 2 == 0 && sizeSolution % 2 != 0) {
return false;
}
// sizeBucketA=0: sizeBucketB*y = sizeSolution : y = sizeSolution/sizeBucketB
if (0 == sizeBucketA && ( (0 == sizeBucketB) || (sizeSolution % sizeBucketB != 0) ) ) {
return false;
}
// sizeBucketB=0: sizeBucketA*y = sizeSolution : y = sizeSolution/sizeBucketA
if (0 == sizeBucketB && ( (0 == sizeBucketA) || (sizeSolution % sizeBucketA != 0) ) ) {
return false;
}
// bucket sizes always positive
int gd = gcd(sizeBucketA, sizeBucketB);
if (sizeSolution % gd != 0) {
return false;
}
return true;
}
/**
* Simple recursive calculation of greatest common divisor between two integers
* Always positive, and in this case bucket sizes positive
*
* @param a
* @param b
* @return
*/
protected int gcd(int a, int b) {
if (0 == b) {
return a;
}
return gcd(b, a % b);
}
/**
* Calculate solution by using BFS. The GraphSolver BFS implementation takes a starting root node
* for the graph, an implementation of a Goal function and an implementation of a state transition
* generation function. These implementations abstract the algorithm from the problem specifics.
* The result is encapsulated within a ResultSolution object, which has methods to generate either
* human readable instructions or machine readable commands.
*
* @param sizeBucketA
* @param sizeBucketB
* @param sizeSolution
* @return
*/
@SuppressWarnings("unchecked")
protected ResultSolution solution(int sizeBucketA, int sizeBucketB, int sizeSolution) {
return new ResultSolution(
new GraphSolver().bfs(
new BucketMix(0, 0, "Initial state"),
new SolutionGoal(sizeSolution),
new FindBucketStates(sizeBucketA, sizeBucketB)));
}
/**
* Implementation of the Goal interface; used to identify when goal state is reached
*
*
*/
public class SolutionGoal implements Goal<BucketMix> {
int sizeSolution;
public SolutionGoal(int sizeSolution) {
this.sizeSolution = sizeSolution;
}
@Override
public boolean isGoal(BucketMix candidate) {
if (candidate.sizeBucketA == sizeSolution || candidate.sizeBucketB == sizeSolution) {
return true;
}
return false;
}
}
/**
* Implemenation of the Transition interface; used to generate new transition states
* from a given node (blind search). Uses heuristics based on problem statement to
* determine a next state.
*
*
*/
public class FindBucketStates implements Transition<BucketMix> {
private int sizeBucketA;
private int sizeBucketB;
public FindBucketStates(int sizeA, int sizeB) {
this.sizeBucketA = sizeA;
this.sizeBucketB = sizeB;
}
@Override
public List<BucketMix> transitions(BucketMix currentMixture) {
List<BucketMix> list = new ArrayList<BucketMix>();
int x = currentMixture.sizeBucketA;
int y = currentMixture.sizeBucketB;
int b1 = sizeBucketA;
int b2 = sizeBucketB;
if (x < b1 && y > 0) {
// move partial from y to x
int partial = Math.min(y, b1 - x);
String transition = "Pour "+b2+"L bucket into "+b1+"L bucket";
list.add(new BucketMix(x + partial, y - partial, transition));
}
if (y < b2 && x > 0) {
// move partial from x to y
int partial = Math.min(x, b2 - y);
String transition = "Pour "+b1+"L bucket into "+b2+"L bucket";
list.add(new BucketMix(x - partial, y + partial, transition));
}
if (x > 0) {
// empty x
String transition = "Empty "+b1+"L bucket";
list.add(new BucketMix(0, y, transition));
}
if (y > 0) {
// empty y
String transition = "Empty "+b2+"L bucket";
list.add(new BucketMix(x, 0, transition));
}
if (x < b1) {
// fill x
String transition = "Fill "+b1+"L bucket";
list.add(new BucketMix(b1, y, transition));
}
if (y < b2) {
// fill y
String transition = "Fill "+b2+"L bucket";
list.add(new BucketMix(x, b2, transition));
}
return list;
}
}
/**
* Result of search. Used to provide String results for either human readable instructions (verbose) or
* machine readable commands (concise).
*
*/
protected class ResultSolution {
final List<BucketMix> sequence;
protected ResultSolution(List<BucketMix> sequence) {
this.sequence = sequence;
}
protected String conciseInstructions() {
StringBuilder builder = new StringBuilder();
for (BucketMix mixture : sequence) {
builder.append(mixture.toString());
builder.append(" ");
}
return builder.toString();
}
protected String verboseInstructions() {
StringBuilder builder = new StringBuilder();
for (BucketMix mixture : sequence) {
builder.append(mixture.toVerboseString());
builder.append(" ");
}
return builder.toString();
}
}
/**
* Data container
*/
protected class BucketMix {
int sizeBucketA;
int sizeBucketB;
String transition;
public BucketMix(int a, int b, String transition) {
this.sizeBucketA = a;
this.sizeBucketB = b;
this.transition = transition;
}
public String toVerboseString() {
return transition+" leaving "+toString();
}
public String toString() {
return "["+sizeBucketA+","+sizeBucketB+"]";
}
}
}
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 buckets 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) M(B,A) (2,1) E(A) (0,1) M(B,A)1 (1,0) F(B) (1,5) M(B,A) (2,4) However, if the work order is as follows, the total number of jobs required is 5 times. 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) 3732 2501 3 5 24 Example of output -1Explanation / Answer
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);
}
}
After including this in your package your code runs fine.
Hope this answers your question. If not, feel free to ask :)
Please rate if your query is solved :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.