Make a WaterOverflow

Question

You and a friend are playing a game - who can overflow the most containers? There are n containers numbered 1 to n. Each container has a certain maximum capacity of water, in litres.

You take turns with your friend to pour discrete amounts of water into the containers. On your turn, you may pour 2 litres of water into one container (you can't distribute into multiple containers), and on your friend's turn, he must pour 3 litres. You may also choose, on your turn, to not pour water in any of the containers (you cannot, however, choose to only pour 1 litre). The person who manages to overflow the container - that is, after they finish their turn, the litres of water inside the container is greater than its maximum capacity - gets a point.

The input comes in the form of space separated integers. The leftmost one is labelled 1 and the rightmost one is labelled n. For instance:

Y 2 1 4 3

Note that the letter indicates who goes first. Y means that you go first, and F means that your friend goes first. The 2 litre container is labelled 1, the 1 litre container is labelled 2, etc. So we would call the 2 litre container "Container 1", because it is labelled 1.

Now, your friend has a very naïve strategy. He always pours all his 3 litres of water into the container that is closest to overflowing. If there is more than one container that is equally closest to overflowing, he will pour all his water in the one that is labelled with the lowest number.

Suppose I use the same naïve strategy of pouring all my 2 litres of water into the container that is closest to overflowing. The example input would work out like this:

1. I pour all my water into Container 2. It overflows, and I get one point.
2. My friend pours all his water into Container 1. It overflows, and he gets one point.
3. I pour all my water into Container 4. It now has 2L of water in it, so it needs another 2L to overflow.
4. My friend pours all his water into Container 4. It overflows, and he gets one point.
5. I pour all my water into container 3. It now has 2L of water in it, so it needs another 3L to overflow.
6. My friend pours all his water into Container 3. It overflows, and he gets one point.

Altogether, I only got one point, and my friend got three. That's not good. I can do better than that if I make use of my ability to pass on my turn without pouring water:

1. I pour all my water into Container 2. It overflows, and I get one point.
2. My friend pours all his water into Container 1. It overflows, and he gets one point.
3. I pass.
4. My friend pours all his water into Container 4. It now has 3L of water in it, so it needs another 1L to overflow.
5. I pour my water into Container 4. It overflows, and I get one point.
6. My friend pours all his water into Container 3. It has 3L of water in it now, so it needs another 2L to overflow.
7. I pour my water into Container 3. It overflows, and I get one point.

By strategically choosing which container to pour my water in, I have managed to obtain 3 points instead of 1. The output format is a list of space separated instructions, where P indicates a pass, and an integer from 1 to n indicates which container I poured water into. For instance, the naïve nonoptimal strategy listed above could be represented as:

2 4 3

Which means I poured into Container 2, then Container 4, then Container 3. The more optimal strategy would be represented as:

2 P 4 3

Which means I poured into Container 2, then passed, then Container 4, then Container 3 (This, by the way, is the output format).

Your program will take in input as described above and return the most optimal solution to get as many points as possible. If there is more than one optimal solution, output either.

Answer 1

Python, 217 202 176

import sys
A=sys.argv[1:]
t=A>["G"]
C=[[int(A[i]),i]for i in range(1,len(A))]
while C:
 c=min(C);d=1.5
 if t:d=c[0]%5<2;print["P",c[1]][d],
 c[0]-=2*d;t^=1
 if[0]>c:C.remove(c)

Reads input from the command line.

Strategy:

• If the remaining capacity in the container with the least remaining capacity is congruent 0 or 1 modulo 5, pour 2 litres (it either overflows, or our friend pours 3 more litres into the same container, bringing us back to the same point.)
• Otherwise, no move improves our position, so do nothing (note that this isn't necessarily the shortest optimal strategy.)

Answer 2

Java - 718

To generalize, the optimal amount of water in the bucket at the beginning of my turn should be capacity-1 or full. So the previous turn (ideally) it should have been capacity-4 or capacity-3, and capacity-7 or capacity-6.

So the only option that is bad for me would be capacity - n where n % 3 == 2. So my strategy is to wait until the end, then grab the bucket at the last minute, taking care to keep the bucket level in the "ok range". If all the buckets are in the range, then do nothing!

Because you cannot win when the capacity is 2, I simply ignored it.

I think this could be the optimal solution. It beats the friend 100% of the time when the capacities are greater than 2.

Here is the function (for use in simulator above):

BucketChoice makeMove(){
    ArrayList<Bucket> bucketsNotOk = new ArrayList<Bucket>();
    ArrayList<Bucket> bucketsOk = new ArrayList<Bucket>();
    //sort buckets
    for(Bucket b:buckets){
        if(b.litersLeft() % 3 == 2){bucketsNotOk.add(b);}
        if(b.litersLeft() % 3 == 0){bucketsOk.add(b);}
        if(b.litersLeft() % 3 == 1){bucketsOk.add(b);}
    }
    //first I want to grab any buckets ready for overflowing
    for(Bucket b:bucketsOk){
        if(b.litersLeft()<2){System.out.println(buckets.indexOf(b));return new BucketChoice(b,2);}
    }
    //next change buckets to OK
    for(Bucket b:bucketsNotOk){
        //no use adding water if it is doomed
        if(b.litersLeft()>2){System.out.println(buckets.indexOf(b));
            return new BucketChoice(b,2);
        }
    }
    return new BucketChoice(buckets.get(0),0);  
}

golfed...hmmm seems long :(

import java.util.*;class o{List<int[]>b=new ArrayList<int[]>(),r=new ArrayList<int[]>();public o(String[]a){for(int x=1;x<a.length;x++){b.add(new int[]{Integer.valueOf(a[x]),0});}while(b.size()>0){if(a[0].equals("F")){e();}int m=0,n=-1,i=0;for(;i<b.size();i++){int[]g=b.get(i);if(g[0]-g[1]<2){n=i;m=1;g[1]+=2;break;}}for(i=0;i<b.size();i++){int[]g=b.get(i);if((g[0]-g[1])%3==2&&m==0){n=i;g[1]+=2;break;}}for(int[]h:b){if(h[0]-h[1]<0){r.add(h);}}for(int[]h:r){b.remove(h);}if(a[0].equals("Y")){e();}if(n!=-1){System.out.print(n+" ");}else{System.out.print("p ");}}}void e(){int[]r={99999,0};for(int[]i:b){if(i[0]-i[1]<r[0]-r[1]){r=i;}}r[1]+=3;if(r[0]-r[1]<0){b.remove(r);}}public static void main(String[]a){new o(a);}}

Answer 3

A Java Simulator

I know there are lazy people out there! Here it is:

To continue, just press any key + enter in the console.

OverflowChallenge:

import java.util.ArrayList;
import java.util.Scanner;

    public class OverflowChallenge {
        ArrayList<Bucket> buckets = new ArrayList<Bucket>();
        int myScore=0,friendScore=0;
        public static void main(String[] args) {
            new OverflowChallenge(args);
        }
        public OverflowChallenge(String[]args){
            for(int x=1;x<args.length;x++){
                buckets.add(new Bucket(Integer.valueOf(args[x])));
            }
            while(buckets.size()>0){
                Scanner s = new Scanner(System.in);     
                if(args[0].equals("F")){naivePlayerMove();}

                BucketChoice myMove=null;
                if(buckets.size()>0){myMove = makeMove();}else{System.exit(0);}
                myMove.bucket.addWater(myMove.litersAdded);
                if(myMove.bucket.overflowing){buckets.remove(myMove.bucket);}

                System.out.println("you added "+myMove.litersAdded+" to bucket "+buckets.indexOf(myMove.bucket));
                if(myMove.bucket.overflowing){System.out.println("...and you overflowed it!");}

                if(!args[0].equals("F")){naivePlayerMove();}
                for(Bucket b:buckets){
                    System.out.println("bucket "+buckets.indexOf(b)+" has " + b.litersFilled +"/"+b.capacity);
                }
                System.out.println("friend score = "+friendScore);
                System.out.println("my score = "+myScore);
                s.next();
            }
        }
        BucketChoice makeMove(){
            return new BucketChoice(buckets.get(0),2);
        }
        void naivePlayerMove(){
            Bucket lowestBucket=new Bucket(999999999);
            for(int x=0;x<buckets.size();x++){
                if(buckets.get(x).litersLeft()<lowestBucket.litersLeft()){
                    lowestBucket=buckets.get(x);
                }
            }
            lowestBucket.addWater(3);
            System.out.println("your friend added 3 liters to bucket "+buckets.indexOf(lowestBucket));
            if(lowestBucket.overflowing){
                friendScore++;
                buckets.remove(lowestBucket);
                System.out.println("...and overflowed it!");
            }
        }
}

Bucket:

public class Bucket {
    int capacity,litersFilled;
    boolean overflowing = false;
    public Bucket(int capacity){
        litersFilled=0;
        this.capacity=capacity;
    }
    public int litersLeft(){
        return capacity-litersFilled;
    }
    public void addWater(int liters){
        litersFilled+=liters;
        if(litersFilled>capacity){
            overflowing=true;
        }
    }
}

BucketChoice:

public class BucketChoice {
    public BucketChoice(Bucket myBucket, int liters){
        bucket = myBucket;
        litersAdded = liters;
    }
    public Bucket bucket;
    public int litersAdded;
}

Enjoy!