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...
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...
Intro to JAVA Problem 1: Summing It Up Write a program, which takes two distinct integers...
Intro to 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...
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....
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),...
Part 1 Write a program that reads a line of input and display the characters between...
Part 1 Write a program that reads a line of input and display the characters between the first two '*' characters. If no two '*' occur, the program should display a message about not finding two * characters. For example, if the user enters: 1abc*D2Efg_#!*345Higkl*mn+op*qr the program should display the following: D2Efg_#! 1) Name your program stars.c. 2) Assume input is no more than 1000 characters. 3) String library functions are NOT allowed in this program. 4) To read a...
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...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT