Question

The purpose of this problem is to gain familiarity with stacks and queues. You have three...

The purpose of this problem is to gain familiarity with stacks and queues.

You have three jugs that can hold c1, c2, and c3 liters of water, respectively. Initially, jug 1 is full and the other two jugs are empty. You can repeat the following procedure any number of times: Choose two of the jugs and pour the contents of one into the other until either the first is empty or the second is full. Your goal is to end up with exactly d liters in one of the jugs.

Write a program called WaterTransfer.java to determine the transfers required to reach the goal. The input is a single line containing four integers between 2 and 100 (inclusive) representing c1, c2, c3, and d. The output is a minimal sequence of jug contents, starting with the initial contents and ending with one of the jugs containing d liters. Each line of the output should consist of 3 integers separated by spaces. If no solution exists, then your program should produce no output.

Good test case: 10 5 3 4

and another test case: 76 45 32 18

For example, if the input is

20 5 3 4

then a valid output is

20 0 0
15 5 0
15 2 3
18 2 0
18 0 2
13 5 2
13 4 3

There may be other solutions, but none with fewer transfers (6) than this one.

Homework Answers

Answer #1

solution :-

Java Code:


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Scanner;
public class WaterJugs
{
public static void main(String args[])
{
Queue<State> q = new LinkedList<State>();
Stack<State> st = new Stack<State>();
ArrayList<State> visited = new ArrayList<State>();
System.out.println("Enter Input Values: ");
Scanner scan = new Scanner(System.in);
int[] cap = new int[3];
for (int i = 0; i < 3; ++i)
{
cap[i] = scan.nextInt();
}
int d = scan.nextInt();
State start = new State(cap);
State.setCapacities(cap);
visited.add(start);
q.add(start);
visited.add(start);
while(q.peek() != null)
{
State next = q.poll();
if (next.reachedGoal(d)) {
for (State x = next; x != null; x = x.pred)
st.push(x);
for (State y = next; y != null; y = y.pred)
{
st.pop().display();
}
break;
}
for(int i = 0; i <= 2; i++)
for(int j = 0; j <= 2; j++)
{
if(j == i) continue;
State p = next.move(i, j);
if(p == null || visited.contains(p)) continue;
visited.add(p);
q.add(p);

}
}
}
}
class State
{
static int[] capacity;
int[] contents;
State pred;
static void setCapacities(int[] c)
{
capacity = c;
}
State(int[] c) {
contents = new int[3];
contents[0] = c[0];
contents[1] = 0;
contents[2] = 0;
}
public State(State state)
{
contents = new int[3];
contents[0] = state.contents[0];
contents[1] = state.contents[1];
contents[2] = state.contents[2];
}
State move(int src, int dest)
{
State newState = new State(this);
if((contents[src] == 0) || (contents[dest] == capacity[dest])==true)
return null;
else{
int diff = capacity[dest] - newState.contents[dest];
if(newState.contents[src] >= diff)
{   
newState.contents[dest] += diff;   
newState.contents[src] -= diff;   
}
else
{
if(newState.contents[dest] + newState.contents[src] > capacity[dest]) return null;
newState.contents[dest] += newState.contents[src];
newState.contents[src] = 0;
}
}
newState.pred = this;
return newState;
}
boolean reachedGoal(int d)
{
return(contents[0] == d || contents[1] == d || contents[2] == d);
}
void display()
{
System.out.println(contents[0] + " " + contents[1] + " " + contents[2]);
}
}

OUTPUT:

Thank you Sir.....!

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Suppose you have three stacks. Stack source is full of random data and stacks aux and...
Suppose you have three stacks. Stack source is full of random data and stacks aux and dest are empty To sort the data in the source, you can repeatedly remove the largest value by popping each item off of source and pushing it onto aux, remembering the maximum value seen as you empty source. When source is empty, you pop each item off of aux and push it back onto source except for the largest one that you remembered, which...
Vollmer Manufacturing makes three components for sale to refrigeration companies. The components are processed on two...
Vollmer Manufacturing makes three components for sale to refrigeration companies. The components are processed on two machines: a shaper and a grinder. The times (in minutes) required on each machine are as follows: Machine Component Shaper Grinder 1 6 4 2 4 5 3 4 2 The shaper is available for 120 hours, and the grinder for 110 hours. No more than 200 units of component 3 can be sold, but up to 1,000 units of each of the other...
Use the following algorithm: (1) Create three stacks of characters: stk1, stk2, stk3. (2) Read the...
Use the following algorithm: (1) Create three stacks of characters: stk1, stk2, stk3. (2) Read the input infix expression one character at a time and push every character read ( other than ')' ) onto stk1. Do not push the character read if it is ')'. (3) As long as stk1 is not empty, do the following:            Fetch the top character ( call it c ) of stk1 and pop stk1.            if c is an alphabetic character (a-z),...
Write the Java(Java 7 or Java 8) program for this problem:- Thanos, in his mission to...
Write the Java(Java 7 or Java 8) program for this problem:- Thanos, in his mission to restore the ecological balance in the universe, has reached planet earth. He considers a planet ecologically balanced if more than half of the people on the planet have the same Consumption Capacity There are N people on planet earth, each having Consumption Capacity C1, C2, ...CN and Strength S1, S2... Sn . Thanos will make earth ecological balanced by killing some people(Possibly None). To...
JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers separated by...
JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers separated by space as input and prints the sum of all the integers between them, including the two given numbers. Note that the numbers can appear in either order. You may assume that both numbers are between –10, 000 and 10, 000. For example, if the input is as follows: 10 4 the output should be 49, since 10+9+8+7+6+5+4=49. Similarly, if the input is -3 10...
Create in JAVA Suppose you are designing a game called King of the Stacks. The rules...
Create in JAVA Suppose you are designing a game called King of the Stacks. The rules of the game are as follows:  The game is played with two (2) players.  There are three (3) different Stacks in the game.  Each turn, a player pushes a disk on top of exactly one of the three Stacks. Players alternate turns throughout the game. Each disk will include some marker to denote to whom it belongs.  At the end...
DESCRIPTION: You will be given a 2D array, called matrix, of Strings. The array has an...
DESCRIPTION: You will be given a 2D array, called matrix, of Strings. The array has an unknown number of cells filled with data. Your goal is to iterate through the 2D array and keep a count of how many cells are full. You will be given the dimensions of the array. INPUT: All input has been handled for you: Two integers denoting the dimensions of the array. These are the integer variables rows and cols. A partially filled 2-D array....
This is in java and you are not allowed to use Java API classes for queues,...
This is in java and you are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them. You should construct a BST by inserting node values starting with a null tree. You can re-use the code for the insert method given in the sample code from the textbook. -insert method is provided below Your code should have a menu driven user interface at the command line with...
Take Three Jojo just graduated and moved up to grade 4. Today is his first day...
Take Three Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of pandemic. So that the quality of learning remains good, Jojo’s teacher gives a hard task for 4th grader. After the 4th graders finished their first task which is prime factorization. Jojo’s teacher set up a game for the stundets. The game is very simple. Given N colored balls, each student has to take...
language: JAVA the Problem Below are a series of problems you need to solve using recursive...
language: JAVA the Problem Below are a series of problems you need to solve using recursive methods. You will write a program that will read commands from an input file, with each command referring to one of the recursive problems to be executed. Each command will be followed (on the same line of input) by the respective parameters required for that problem. (15 points for main method) DescArrayCheck   Write a recursive method that checks whether an array of integers -...