//-----------------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

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 {

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 {

private int sizeBucketA;

private int sizeBucketB;

public FindBucketStates(int sizeA, int sizeB) {

this.sizeBucketA = sizeA;

this.sizeBucketB = sizeB;

}

@Override

public List transitions(BucketMix currentMixture) {

List list = new ArrayList();

int x = currentMixture.sizeBucketA;

int y = currentMixture.sizeBucketB;

int b1 = sizeBucketA;

int b2 = sizeBucketB;

if (x 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 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

// fill x

String transition = "Fill "+b1+"L bucket";

list.add(new BucketMix(b1, y, transition));

}

if (y

// 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 sequence;

protected ResultSolution(List 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 -1