Keep your distance!

Question

Every player has a number. Can yours be the farthest from them all?

Requirements

Write a Java, Python 2, or Ruby function named choose() that accepts three arguments:

• an integer - the number of rounds already completed
• an integer - the number of players
• an array of strings - the results of each previous round
  • each string is a space-separated list of integers, sorted from lowest to highest

For example, choose(2, 4, ["4 93 93 174", "1 84 234 555"]) means:

• there were already two rounds (this is the third round)
• there are a total of four players
• in the first round, the numbers chosen were 4, 93, 93, 174
• in the second round, the numbers chosen were 1, 84, 234, 555

You must return a whole number from 1 to 999 (inclusive).

For each other player, your score is the square root of the distance between your number and theirs. Your score for the round is the total of all of these scores.

100 rounds will be played. The highest total score wins!

Rules

• Your code may not use any I/O, including console, files, network, etc.
• You may not interfere with the control program or any other players.
• Programs which look like they violate the above rules will be excluded.
• Each call of a function should take under five seconds on my computer (Intel Core i5 2450M with 8GB of RAM).
• If a program throws an exception or returns an invalid value, it will be treated as if it returned 1.
• Each user may submit at most one program.

Miscellaneous

• The control program is on GitHub.
• There are three built-in players. They can be found in this answer.
• The winner will be chosen on January 28.

Leaderboard

The winner is Conservator.

Honorable mention to Gustav, the highest scoring player with a non-constant strategy.

• Conservator - 36226
• High - 36115
• FloorHugger - 35880
• NumberOne - 35791
• Overestimator - 35791
• Gustav - 35484
• Historian - 35201
• Sampler - 34960
• Incrementer - 34351
• JumpRightIn - 34074
• Vickrey - 34020
• Teenager - 33907
• Randu - 33891
• Weightlifter - 33682
• Middleman - 33647
• BounceInwards - 33529
• NastyMathematician - 33292
• Jumper - 33244
• Copycat - 33049

The full results can be found here. (I recommend disabling text wrapping.)

Answer 1

Python, Conservator

def choose(round, players, scores):
    return 999

Since every exception throws 1, it stays away as much as possible from it. Makes its fortune at the expense of the weak.

Fun fact: I thought about improving it, but couldn't find a better way than just hiding in a corner.

Answer 2

Number One, Java

The name explains this one completely.

public static int choose(int round, int players, String[] args) {
    return 1;
}

Answer 3

Python, AncientHistorian

Firmly believes that the future will be exactly like the past, but believes the last round is too recent to be histiry, so it just loops through 1 - 999 and chooses what would have been the best the previous rounds exept the last. First 2 round returns 500.

def choose(round, players, scores):
    calc = lambda n, scores: sum([abs(int(i)-n)**.5 for i in scores.split(' ')])
    return max(range(1, 1000), key=lambda n: sum([calc(n, j) for j in scores[1:]])) if round>1 else 500

Answer 4

Python, Vickrey

def choose(rounds, players, results):        
    if not results:
        return (id(0)/7)%999 + 1

    def best(array):
        score = lambda x: sum(abs(x-y)**.5 for y in array)
        m = max(score(x) for x in range(1, 1000))
        return [x for x in range(1, 1000) if score(x) == m]

    def second_best(array):
        array.extend(best(array))
        options = best(array)
        return options[(id(0)/7) % len(options)]

    results = [map(int, s.split()) for s in results]
    counts = {}

    for round_ in results:
        for number in round_:
            counts[number] = counts.get(number, 0) + 1

    most_common = sorted([(c, n) for n,c in counts.items()], reverse=True)
    to_avoid = [t[1] for t in most_common[:players]]

    return second_best(to_avoid)

Makes a list of numbers which have been played often, assumes that everyone else will play optimally and opts for the second best choice given the list.

For example, if the most common numbers are [1, 990, 999], then Vickrey inserts the optimal play 200 to give [1, 200, 990, 999], then picks the best option for the new array (which is 556).

Answer 5

Java, Overestimator

As the name suggests, this program assumes all the other programs will try to play "well" by picking the best answer based on the last round - so this "overestimator" always picks the worst possible position based on the previous round.

 public static int choose(int round, int players, String[] args) {
     String[] lastRoundStrings = args[args.length - 1].split(" ");
     int[] lastRound = new int[lastRoundStrings.length];
     int worstSelection = 0;
     for (int i = 0; i < lastRound.length; i++) {
         double worstScore = Double.MAX_VALUE;
         for (int j = 1; j < 999; j++) {
             double computedScore = score(j, lastRound);
             if (computedScore < worstScore) {
                 worstScore = computedScore;
                 worstSelection = j;
             }
         }
     }
     return worstSelection;
 }

 public static double score(int position, int[] otherPositions) {
     double total = 0;
     for (int i = 0; i < otherPositions.length; i++) {
         total += Math.sqrt(Math.abs(otherPositions[i] - position));
     }
     return total;
 }

Answer 6

Java - Weightlifter

Loops through 1-999 to figure out which would be the best for each round. Weighs them according to recency (recent rounds have more weight), and returns its best overall guess. Hopefully if patterns form in later round, this will be able to pick up on it.

Edit: Now with +Inf% more recursion! Not being able to store/save/see what you chose on previous rounds is a drag. Taking your own inputs into account messes you up when trying to figure out what others are going to do. So, let's compute it! This will now recurse to figure out what it chose on the previous round and ignore that when calculating the next move.

Note that it only really ignores its own input from the last turn, but since that one is weighted the highest, it seems to work okay. This could be fixed with a bit more work, but I'll wait for the leaderboard to see if it's needed.

int choose(int rounds, int players, String[] hist){
    if(rounds < 1)
        return 1;

    int lastChoice = choose(rounds-1,players,java.util.Arrays.copyOf(hist, hist.length-1));

    int[][] history = new int[hist.length][players];
    for(int i=0;i<hist.length;i++){
        String[] tokens = hist[i].split(" ");
        boolean flag = false;
        for(int j=0;j<tokens.length;j++){
            history[i][j] = Integer.parseInt(tokens[j]);
            if(i==history.length-1 && history[i][j]==lastChoice && !flag){
                flag = true;
                history[i][j] = -1;
            }
        }
    }

    double best = 0;
    int guess = 1;
    for(int i=1;i<1000;i++){
        double score = 0;
        for(int j=0;j<history.length;j++){
            double weight = (double)(j+1)/history.length;
            for(int k=0;k<history[j].length;k++){
                if(history[j][k] > 0)
                    score += Math.sqrt(Math.abs(history[j][k]-i)) * weight;
            }
        }
        if(score > best){
            best = score;
            guess = i;
        }
    }
    return guess;
}

Answer 7

Ruby, JumpRightIn

def choose(round, players, args)
    return 500 if args.size == 0
    last_round = args[-1].split.map(&:to_i) + [1000]
    max_gap = 0
    last = 0
    move = 1
    last_round.each { |i|
        gap = i - last - 1
        if gap > max_gap
            max_gap = gap
            move = (i + last)/2
        end
        last = i
    }
    move
end

It's probably the most straight-forward strategy. It finds the largest gap in the last round, and chooses the number right in the middle of that gap.

Answer 8

Ruby, Copycat

Simply returns whichever number won last time.

def choose r, p, hist
  last = hist.last.split.map &:to_i
  scores = last.map{|n| last.map{|m| (n-m).abs ** 0.5 }.inject :+ }
  last[scores.index scores.max]
end

Answer 9

Gustav (Python 2)

This is a pretty straight forward meta strategy, shamelessly copied from one of my old answers in a similar KotH challenge. It considers a few simple strategies, looks how they would have performed over all previous rounds, and then follows the highest scoring one for the next round.

def choose(k, N, h):
    if k<2: return 999
    H = [[int(x) for x in l.split()] for l in h]
    score = lambda x,l: sum(abs(x-y)**.5 for y in l)
    S = [range(1,1000)
         + [max(range(1,1000), key=lambda x: score(x, H[i-1]))]
         + [max(range(1,1000), key=lambda x: score(x, H[i-2]))]
         + [min(range(1,1000), key=lambda x: score(x, H[i-1]))]
         + [min(range(1,1000), key=lambda x: score(x, H[i-2]))]
         for i in range(2,k+1)]
    scores = [sum(score(s[j],l) for s,l in zip(S[:-1], H[2:]))
              for j in range(len(S[0]))]
    return max(zip(scores, S[-1]))[1]

I realize now that the algorithm still has some flaws. E.g. it might keep "chasing itself" because it does not distinguish its own moves from those of the opponents. However, I'll leave it like this for now.

Answer 10

Python, Randu

Numbers selected by the most ill-conceived random number generator ever.

def choose(round, players, scores):
    x = 15
    for i in range(round * players + 1):
        x = (x * 65539) % 2147483648
    y = int((x / 2147483648.0) * 999.0)+1
    return y

Answer 11

The following three programs are built-in.

High (Ruby)

def choose(round, players, args)
    return 990
end

Incrementer (Java)

public static int choose(int round, int players, String[] args) {
    return round * 10 + 5;
}

FloorHugger (Python)

def choose(round, players, args):
    if len(args) == 0:
        return 10
    last = args[-1].split();

# next line from http://stackoverflow.com/a/7368801/3148067
    last = map(int, last)

    dist = 0
    for i in range(1, 999):
        if i in last:
            dist = 0
        else:
            dist = dist + 1
            if dist == 10:
                return i
    return 500

Answer 12

Python, Sampler

Out of a list of places, choose the one that is farthest away from recently used numbers, ignoring the previous turn.

def choose(turn, players, history):
    sample = map(int, (' '.join( history[-5:-1] )).split())
    def distance(x): return sum(abs(x-y)**0.5 for y in sample)
    places = range(1, 1000, 13)
    score, place = max((distance(x), x) for x in places)
    return place

Answer 13

Java, BounceInwards

Starting at 1, it gradually gets closer to 500 while bouncing between the higher and lower option.

public static int choose(int round, int players, String[] args) {
    return round%2 == 0 ? round * 5 : 1000 - round * 5;
}

Answer 14

NastyMathematician (Java)

Examines the last two rounds (if the best numbers were 70 and 80, it will output 90). It is nasty because it tries to take as high numbers as possible to win against his opponents.

public static int choose(int round, int players, String[] args) {
    if (round == 0) {
        return 999;
    }

    int[][] results = new int[args.length][players];

    // parse input
    for (int i = 0; i < args.length; i++) {
        String[] rounds = args[i].split(" ");
        for (int j = 0; j < rounds.length; j++) {
            results[i][j] = Integer.parseInt(rounds[j]);
        }
    }

    int bestNumber = 0;
    double bestScore = -1;

    // get the best number for the last round
    for (int i = 1; i < 1000; i++) {
        double score = 0;
        for (int result : results[results.length - 1]) {
            score += Math.sqrt(Math.abs(i - result));
        }
        if (score >= bestScore) {
            bestScore = score;
            bestNumber = i;
        }
    }

    if (round == 1) {
        return bestNumber;
    }

    int bestNumber2 = 0;
    double bestScore2 = -1;

    // get the best number for the second last round
    for (int i = 1; i < 1000; i++) {
        double score = 0;
        for (int result : results[results.length - 2]) {
            score += Math.sqrt(Math.abs(i - result));
        }
        if (score > bestScore2) {
            bestScore2 = score;
            bestNumber2 = i;
        }
    }

    // add the difference between last round and second last round to get this rounds best number
    int difference = bestNumber - bestNumber2;
    bestNumber = bestNumber + difference;

    return bestNumber > 999 ? 999 : bestNumber;
}

Answer 15

Python - I don't want to think of a name...

If the average of the numbers chosen in the past rounds is less than 500, it picks 999. It picks 1 otherwise.

def choose(a,b,c):
    total=0
    for i in c:
        for j in i.split(" "):
            total+=int(i)
    average=total/(a*b)
    if average<500:
        return 999
    return 1

Answer 16

Python, Middleman (based on conservator by @clabacchio)

def choose(round, players, scores):
    return 500;

After I noticed that the upper edge scores high (and outperformed the lower edge), I wondered whether there could be anything worse than just getting caught in the middle.

Answer 17

Jumper (Ruby)

def choose(round, players, args)
    495*(round%3)+5
end

Alternates between bottom, middle and top. (5,500,995)