The Thirsty Crow

Question

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;
    }

}

Answer 1

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.