15
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ Do I have any way of telling which was my own number in those previous rounds? \$\endgroup\$ – Martin Ender Jan 21 '15 at 21:43
  • \$\begingroup\$ @MartinBüttner No. \$\endgroup\$ – Ypnypn Jan 21 '15 at 21:44
  • 1
    \$\begingroup\$ I don't know any of those languages :( Could you add JavaScript? Like, run it with node.js? \$\endgroup\$ – Cilan Jan 22 '15 at 3:16
  • 1
    \$\begingroup\$ @TheWobbuffet, I don't know any of them either. Didn't stop me from making a Python entry. \$\endgroup\$ – Mark Jan 22 '15 at 3:21
  • 7
    \$\begingroup\$ I think it would have been more interesting if the space was a circle/loop so that the distance between 1 and 999 is 1. That would keep the "guess a single number every turn" from dominating, since there aren't "edges" to park on. Obviously too late to change now though ;) \$\endgroup\$ – Geobits Jan 23 '15 at 14:30

17 Answers 17

9
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Looks like I picked the wrong corner. :( \$\endgroup\$ – TheNumberOne Jan 23 '15 at 22:43
  • \$\begingroup\$ It is good for a simple reason: Others try to minimize the distance to you. They will automatically make your score better. A game changer would be an opponent who trys to get as close to you as possible. \$\endgroup\$ – Martin Thoma Jan 26 '15 at 21:34
  • 1
    \$\begingroup\$ Eww...a semicolon in Python? \$\endgroup\$ – KSFT Jan 30 '15 at 21:24
  • \$\begingroup\$ @KSFT hehe I'm rusty on Python, and I've never been that expert anyway \$\endgroup\$ – clabacchio Jan 31 '15 at 12:25
6
\$\begingroup\$

Number One, Java

The name explains this one completely.

public static int choose(int round, int players, String[] args) {
    return 1;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Why the down vote? \$\endgroup\$ – TheNumberOne Jan 22 '15 at 18:13
  • 5
    \$\begingroup\$ I especially like how the user name ties into the submission \$\endgroup\$ – Brian J Jan 22 '15 at 18:14
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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).

\$\endgroup\$
4
\$\begingroup\$

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;
 }
\$\endgroup\$
  • \$\begingroup\$ How come this played a constant "1"? Was there a bug? Mind you, playing "1" proved to be quite successful. :) \$\endgroup\$ – Emil Jan 29 '15 at 11:03
  • \$\begingroup\$ Sadly the code has a bug, yes - it never actually parses the scores it reads from the last round. (But I realised it too late and it seemed wrong to edit a submission by then, plus as you say it was doing pretty well so... whatever :p) \$\endgroup\$ – Alex Walker Jan 29 '15 at 11:39
4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Note: Even at round 100, it completes in under a second on my somewhat-slow PC. If it takes too long on yours for some reason, let me know so I can limit the recursion. \$\endgroup\$ – Geobits Jan 22 '15 at 16:30
  • \$\begingroup\$ It's very fast on my machine as well. \$\endgroup\$ – Ypnypn Jan 23 '15 at 16:05
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ What does it return for the first round? Oh never mind. Exceptions would return 1. \$\endgroup\$ – mbomb007 Jan 21 '15 at 22:55
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What does it return for the first round? 1? \$\endgroup\$ – mbomb007 Jan 21 '15 at 22:56
  • \$\begingroup\$ @mbomb007 Oh, I always forget these pesky initial rounds. Thanks, it now returns 500. \$\endgroup\$ – Martin Ender Jan 21 '15 at 22:59
3
+100
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Jumper (Ruby)

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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