5
\$\begingroup\$

Problem Statement

There are N pots. Every pot has some water in it. They may be partially
filled. So there is a Overflow Number O associated with every pot which tell how many minimum stone pieces are require for that pot to overflow. So if for a pot O-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 O-value correctly for every pot (that is he knew O1 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 O-value. The Crow wants some K pots to overflow so that he can serve his child appropriately. For overflowing the pots he needs to search for the stones in forest (assume that every stone has same size).

He wants to use minimum number of stones to overflow the K pots. But he doesn't know now which pot has what O-value. So the task is to find out the minimum number of stones that the crow requires to make the K pots overflow in the worst case.

Input Specification:

  1. A array O corresponding to O-value of N pots {O1, O2, ....... , On}
  2. Number of pots
  3. K -value ( number of pots which the crow wants to overflow)

Output Specification:

Minimum number of stones required to make K pots overflow in worst case or -1 if input is invalid.

Example:

Let's say there are two pots:

  1. Pot 1 has O value of 5 , O1= 5
  2. Pot 2 has O value of 58, O2= 58

Let's say the crow wants to make one of the pots overflow. If he knows which pot has what O-value he would simply search for 5 stones and put them in pot 1 to make it overflow. But in a real case he doesn't know which pot has what O-value so just 5 stones may not always work. However he does know that one pot has O-value 5 and other has 58. So even in the 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 O-value of 5. So the answer for above question is minimum 10 stones even in worst case.

Please let me know the corrections that I need to make the code better.

public class ThirstyCrow {

    public ThirstyCrow() {
        super();
    }
    private static final int INVALID_INPUT=-1;

    public int getMinimumNumberOfStonesRequiredToOverflowThePots(int[] overflowValues,int numberOfPotsPresent,
            int numberOfPotsToOverFlow){
        List<Pot> pots = null;
        if(overflowValues.length>numberOfPotsPresent)return INVALID_INPUT;
        if(numberOfPotsPresent<numberOfPotsToOverFlow) return INVALID_INPUT;
        try {
            pots = Pot.createPotsFromOverFlowLimits(overflowValues, numberOfPotsPresent);
        } catch (InvalidInputException e) {
            return INVALID_INPUT;
        }
        return getTotalNumberOfStonesUsedForOverflowing(pots, numberOfPotsPresent, numberOfPotsToOverFlow);
    }

    private int getTotalNumberOfStonesUsedForOverflowing(List<Pot> pots,int numberOfPotsPresent,
            int numberOfPotsToOverFlow){
        int numberOfPotsOverFlown=0;
        int totalNumberOfStonesUsedForOverflowing = 0;
        while(numberOfPotsOverFlown!=numberOfPotsToOverFlow){
            int minimumOverFlowValue = getMinimumOverFlowValue(pots) ;
            addTheStonesToAllPots(pots, minimumOverFlowValue);
            numberOfPotsOverFlown++;
            totalNumberOfStonesUsedForOverflowing+=(minimumOverFlowValue*pots.size());
            removeOverflowingPotFromTheList(pots);
        }
        return totalNumberOfStonesUsedForOverflowing;

    }

    private int getMinimumOverFlowValue(List<Pot> pots){
        if(pots.isEmpty())return 0;
        Collections.sort(pots);
        return pots.get(0).numberOfStoneRequiredForOverFlow();
    }

    private void removeOverflowingPotFromTheList(List<Pot> pots){
        if(pots==null) return;
        Iterator<Pot> potsListIterator = pots.iterator();
        while(potsListIterator.hasNext()){
            Pot pot = potsListIterator.next();
          if(pot.numberOfStoneRequiredForOverFlow()==0) potsListIterator.remove();
        }
    }

    private void addTheStonesToAllPots(List<Pot> pots,int numberOfStonesToAdd){
        if(pots==null) return;
        for (Pot pot : pots) {
            pot.addStonesToThePot(numberOfStonesToAdd);
        }
    }


}

class Pot implements Comparable<Pot>{
    private int overflowValue;
    private int numberOfStonesPresent=0;

    public Pot(int overflowValue) throws InvalidInputException{
        if(overflowValue<0) throw new InvalidInputException("Invalid Input Provided!!");
        this.overflowValue=overflowValue;
    }

    public Integer getOverFlowValue(){
        return overflowValue;
    }

    public Integer getNumberOfStonesPresent() {
        return numberOfStonesPresent;
    }

    public void addStonesToThePot(int numberOfStones){
        if(numberOfStonesPresent>=overflowValue) return; //If the Pot is Already overflowing
        numberOfStonesPresent+=numberOfStones;
    }

    public Integer numberOfStoneRequiredForOverFlow(){
        return overflowValue-numberOfStonesPresent;
    }

    @Override
    public int compareTo(Pot pot) {
        return this.numberOfStoneRequiredForOverFlow().compareTo(pot.numberOfStoneRequiredForOverFlow());
    }

    public static List<Pot> createPotsFromOverFlowLimits(int [] overFlowLimits,int numberOfPots) throws InvalidInputException{
        List<Pot> pots = new ArrayList<>();
        if(overFlowLimits==null || overFlowLimits.length==0) return pots;
        for (int i = 0; i < numberOfPots; i++) {
            pots.add(new Pot(overFlowLimits[i]));
        }
        return pots;
    }

}

class InvalidInputException extends Exception{

    private String message;
    private static final long serialVersionUID = 8332397639526918252L;

    public InvalidInputException(String message){
        this.message=message;
    }

    public String getMessage() {
        return message;
    }

}
\$\endgroup\$
  • \$\begingroup\$ I don't think your solution works for all test cases. For example, with two pots 5 and 7, your program would return 10 when the answer is 7. \$\endgroup\$ – JS1 Jul 28 '16 at 10:57
  • \$\begingroup\$ @JS1 In your example lets say I have to overflow one pot with the minimum number of stones and I know that one of the pots has an overflow threshold of 5 BUT I dont know which pot has that threshold value. So in the worst case I have to use 5 stones for each pot to check which one will overflow. So should'nt the answer be 10 here? \$\endgroup\$ – Aditya Cherla Jul 28 '16 at 11:06
  • \$\begingroup\$ @AdityaCherla you put 7 stones in 1 pot, then it overflows =) \$\endgroup\$ – Pimgd Jul 28 '16 at 11:10
  • \$\begingroup\$ @Pimgd I'm so sorry. I just realized the problem with my code. I misunderstood the question. Will edit my answer \$\endgroup\$ – Aditya Cherla Jul 28 '16 at 11:13
  • 1
    \$\begingroup\$ One of the problems here is your algorithm isn't necessarily correct. You can actually have a worse worse-case for some arrangements; contrast pots [1, 100] and pots [100, 101]. Given the crow knows all the pots values, an optimal heuristic can be synthesized despite not knowing individual pot values, but it has the potential to be fairly complex. An alternative is to brute-force the solution but that also has the potential to be complex to optimize, especially for lots of deep pots. \$\endgroup\$ – Danikov Jul 28 '16 at 15:28
4
\$\begingroup\$

Doesn't work on all cases

Consider a test case with 2 pots: 5, 7 and k=1. Your program will return 10, thinking that the crow must fill both pots with 5 stones. But actually the crow should just fill one pot with 7 stones, making the answer 7.

Alternative algorithms

I think that there are two strategies for eliminating a single pot:

  1. Fill one pot with enough stones to fill the biggest pot.

  2. Fill all pots each with enough stones to fill the smallest pot. This guarantees that the smallest pot will be filled.

Now, to fill \$k\$ pots, you can't just do the greedy strategy of "for the next pot, pick the minimum stones for case #1 and case #2". That is because case #1 only eliminates one pot from contention, but case #2 also fills all the other pots with some stones, which could have benefits for future iterations.

I can imagine a brute force solution that recursively tries both strategies at each step, but that would take \$O(2^k)\$ time. There is most likely a better way of doing this. Perhaps a linear time solution would be:

For each i in 0..k: Try filling i largest pots with strategy #1, and the k-i smallest pots with strategy #2. Then pick the i that required the least stones and that is the answer.

I haven't thought enough about the problem to know if the above algorithm actually produces the correct answer.

Another consideration

Consider a test case with 3 pots: 5, 5, 20 and k=1. In this case, the answer should be 10 and not 15, because after filling two pots with 5 stones, it is guaranteed to have filled one of the pots of size 5. So this should be considered when using strategy #2 above.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ about your last consideration, the one with 3 pots (5,5,20) and k=1, I'm not able to decide an ideal strategy for this case. I think we need to handle such cases seperately \$\endgroup\$ – Aditya Cherla Jul 29 '16 at 4:39
  • \$\begingroup\$ Both of the numbered strategies and the additional consideration are special cases of the parameterised strategy: suppose the pot capacities are ordered a_0 <= a_1 <= ... <= a_{n-1}. Place a_{n-i} stones in each of i pots, and at least one will overflow. Strategy 1 is the case i=1; strategy 2 is the case i=n; the example from the additional consideration is solved with i=2. However, there's yet another consideration: if the crow has to overflow more than one pot, the optimal strategy may involve case switches rather than a fixed sequence of applications of this strategy. \$\endgroup\$ – Peter Taylor Jul 6 '17 at 11:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.