Core Java programming

[Mayur p]

Hi ,Can someone help me solve below case study for core Java programming.
Assignment Name : Thirsty Crow
There are N pots. Every pots have some water in it. They may be partially filled. So there is a Overflow
Number 0 associated with every pot which tell how many minimum stone pieces are require for that pot
to overflow. So if for a pot 0-value is 5 it means minimum 5 stone pieces should be put in that pot to
make it overflow. Initially a crow watched those pots and by seeing the water level he anticipated 0-
value correctly for every pot (that is he knew 01 to On).
But when he came back in evening he found that every pot is painted from outside and he is not able to
know which pot has what 0-value. Crow wants some K pots to overflow so that he can serve his child
appropriately. For overflow of pots he need to search for stone in forest (assume that every stone has
same size). He wants to use minimum number of stones required to overflow K pots.
But only he knows the 0-value of pots he doesn't know now which pot has what 0-value. So the task is
that in what minimum number of stones he can make K pots overflow in worst case.
Input Format:
You will be given a function which contains an integer array 0 corresponding to 0-value of N pots {01, 02,
On) and a K - Value representing the number of pots which the crow wants to overflow
Output Format:
You need to return the Minimum number of stones (in the form of integer) required to make K pots
overflow in worst case.
If input is invalid, return -1.
Sample Test Case 1
Sample Input: {5,58}, 1
Sample Output: 10
Explanation:
Let say there are two pots
pot 1 has 0 value of 5, 01= 5
pot 2 has 0 value of 58, 02= 58
Let say crow wants to make one of the pot to overflow. If he knows which pot has what 0-value, he
would simple search for 5 stones and put them in pot 1 to make it overflow. But in real case he doesn't
know which pot has what 0-value so just 5 stones may not always work.
However, he does know that one pot has 0-value 5 and other has 58. So even in worst case he can make
one of the pot overflow just by using 10 stones. He would put 5 stones in one pot if it doesn't overflow
he would try the remaining 5 in the other pot which would definitely overflow because one of the pot
has 0-value of 5.
So the answer for above question is minimum 10 stones even in worst case.
Sample Test Case 2
Sample Input: {65,69}, 1
Sample Output: 69
Explanation:
Let say there are two pots
pot 1 has 0 value of 65, 01= 65
pot 2 has 0 value of 69, 02= 69
In worst case, crow will approach the pot with 69 O value first. After putting in 65 stones, the pot does
not overflow. Now if pot is changed, 65 more stones would be required, whereas if just 4 more stones
are put into same pot, it will overflow.
So the answer in this case is 69.
Function to implement:
public static int minimumStonesInWorstCase(int[] pots, int k) {
//implement your logic
}

[wolle]

Here's a prettier print of the problem. It's problem 2,

http://opencsta.org/could-anyone-ple...rgent-on-hold/

It's probably by the same OP since it's posted the same day as here.

The Thirsty Crow problem is described in several other links on the internet with almost identical formulation. There doesn't seem to be a definite solution. This indicates the problem is not a well analyzed standard problem but a well kept secret at a certain place. Quite intriguing!

[wolle]

The problem stipulates there are N pots of which K should be overflown so it's a general problem even though the examples only cover the minimal case when N=2 and K=1. Even though the crow is supposed to be maximally unlucky when selecting pots it is clever enough to minimize losses by using an optimal strategy when distributing stones among two pots in order to spend as few as possible.

This raises a question. Is there also an optimal strategy for higher N and K and is the programmer supposed to figure it out as part of the exercise? To me it seems like a lot to ask for a programming language exercise. At least there should've been examples covering the N=3 with K=1 and K=2 cases as a hint.

Even so the crow must do something and most natural is to simply overflow the wanted number of pots from left to right. I call it the random strategy and since our crow is maximally unlucky it ends up with the worst case for this strategy. That will be the sum of the largest o-values with the additional quirk that for some combinations of N and K the minimal case is applicable (when the o-values of the last 2 bins become revealed during the pot filling process).

I'll suggest a variation of the random strategy that sometimes gives a lower worst case result. I call it random with minimal filling because here the crow doesn't overflow the pots. Instead it fills them up one by one with the number of stones given by the smallest o-value. This is repeated in a round-robin fashion until there is an overflow. Then the overflown pot is taken out of circulation and the filling continues with the now smallest o-value. I speculate that the worst case happens when the pots are encountered in sorted o-value order starting with largest.

Both above strategies give worst cases but not necessarily the same result so neither is optimal. Then which one to use? One can imagine that the crow selects a strategy at random and being maximally unlucky it always picks the one with the worst outcome. Or, having shown signs of cleverness in the minimal case, the crow sneakily runs both strategies and proudly presents the best outcome.

[wolle]

I've had another look att this problem and I think I've found an optimal strategy. I only sketch it since I don't intend to implement it. It's a combination of the two strategies in my previous post and it's based on statistical expectation.

It goes like this. We consider the pots from left to right and start with the first. We have two choices. We either overflow the pot immediately or we put in X stones in the pot and the same amount in subsequent pots until we find one that overflows. Knowing the o-values it is possible to calculate the statistical expectation for the number of stones needed to find an overflow for each of those cases. In the second case X for all o-values must be considered. We pick the smallest expectation (the cheapest way to find an overflow) and that will be an optimal choice.

When an overflow has been found that pot is removed and the process starts over again with the first of the remaining pots. This is repeated until a total of K pots have been overflown. Note that a pot initially can overflow with any of the o-values. This changes when stones are added to a pot. If it didn't overflow when X stones were added this means o-values smaller than X no longer apply to that pot. So each pot has an individual list of o-values that becomes shorter as stones are added indicating that information is increasing until certainty is reached when the pot overflows eventually.

To program this, all permutations of the o-values are generated, the pot-filling strategy is applied to each permutation and the needed number of stones is recorded. Afterwards the worst case is printed.

Calculating the expectation for one pot in the immediate case should be straightforward. The expectation in the deferred case would follow the Geometric probability distribution if the o-value lists of the pots never changed but they do so it will be a more involved distribution.

https://math.stackexchange.com/quest...ies-for-trials

---

Spontaneously I would say that this doesn't look like a Java programming exercise. It looks more like an applied math exercise with Java as implementation language.