Jeder Spieler hat eine Nummer. Kann deins am weitesten von allen entfernt sein?

Bedarf

Schreiben Sie eine Java-, Python 2- oder Ruby-Funktion mit dem Namen choose(), die drei Argumente akzeptiert:

• eine ganze Zahl - die Anzahl der bereits abgeschlossenen Runden
• eine ganze Zahl - die Anzahl der Spieler
• eine Reihe von Zeichenfolgen - die Ergebnisse jeder vorherigen Runde
  • Jede Zeichenfolge ist eine durch Leerzeichen getrennte Liste von Ganzzahlen, die vom niedrigsten zum höchsten Wert sortiert sind

Zum Beispiel choose(2, 4, ["4 93 93 174", "1 84 234 555"])bedeutet:

• Es gab bereits zwei Runden (dies ist die dritte Runde)
• Es gibt insgesamt vier Spieler
• In der ersten Runde wurden die Zahlen 4, 93, 93, 174 gewählt
• In der zweiten Runde wurden die Zahlen 1, 84, 234, 555 gewählt

Sie müssen eine ganze Zahl von 1 bis 999 (einschließlich) zurückgeben.

Für jeden anderen Spieler ist Ihre Punktzahl die Quadratwurzel des Abstandes zwischen Ihrer und ihrer Zahl. Ihre Punktzahl für die Runde ist die Summe aller dieser Punkte.

Es werden 100 Runden gespielt. Die höchste Gesamtpunktzahl gewinnt!

Regeln

• Ihr Code verwendet möglicherweise keine E / A, einschließlich Konsole, Dateien, Netzwerk usw.
• Sie dürfen weder das Steuerungsprogramm noch andere Spieler stören.
• Programme, die gegen die oben genannten Regeln verstoßen, werden ausgeschlossen.
• Jeder Aufruf einer Funktion sollte auf meinem Computer (Intel Core i5 2450M mit 8 GB RAM) weniger als fünf Sekunden dauern.
• Wenn ein Programm eine Ausnahme auslöst oder einen ungültigen Wert zurückgibt, wird es so behandelt, als ob es 1 zurückgibt.
• Jeder Benutzer darf höchstens ein Programm einreichen.

Sonstiges

• Das Steuerungsprogramm ist auf GitHub .
• Es gibt drei eingebaute Spieler. Sie können in dieser Antwort gefunden werden .
• Der Gewinner wird am 28. Januar ermittelt.

Bestenliste

Der Gewinner ist Conservator .

Lobende Erwähnung an Gustav , den Spieler mit der höchsten Punktzahl und einer nicht konstanten Strategie.

• Konservator - 36226
• Hoch - 36115
• FloorHugger - 35880
• NumberOne - 35791
• Overestimator - 35791
• Gustav - 35484
• Historiker - 35201
• Sampler - 34960
• Inkrementierer - 34351
• JumpRightIn - 34074
• Vickrey - 34020
• Teenager - 33907
• Randu - 33891
• Gewichtheber - 33682
• Middleman - 33647
• BounceInwards - 33529
• NastyMathematician - 33292
• Jumper - 33244
• Nachahmer - 33049

Die vollständigen Ergebnisse finden Sie hier . (Ich empfehle, den Zeilenumbruch zu deaktivieren.)

Python, Konservator

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

Da jede Ausnahme 1 wirft, bleibt sie so weit wie möglich davon entfernt. Macht sein Vermögen auf Kosten der Schwachen.

Witzige Tatsache: Ich dachte darüber nach, es zu verbessern, konnte aber keinen besseren Weg finden, als mich nur in einer Ecke zu verstecken.

Nummer eins, Java

Der Name erklärt dies vollständig.

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

Python, AncientHistorian

Ist der festen Überzeugung, dass die Zukunft genau wie die Vergangenheit sein wird, glaubt jedoch, dass die letzte Runde zu aktuell ist, um noch nicht abgeschlossen zu sein. Sie durchläuft also nur 1 - 999 und wählt aus, welche der vorherigen Runden mit Ausnahme der letzten die besten gewesen wären. Die ersten 2 Runden bringen 500 zurück.

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

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)

Erstellt eine Liste mit häufig gespielten Zahlen, setzt voraus, dass alle anderen optimal spielen, und entscheidet sich für die zweite beste Wahl die Liste gegeben.

Wenn zum Beispiel die häufigsten Zahlen sind [1, 990, 999], fügt Vickrey das optimale Spiel 200 ein, um es zu geben [1, 200, 990, 999], und wählt dann die beste Option für das neue Array aus (das ist 556).

Java, Overestimator

Wie der Name schon sagt, geht dieses Programm davon aus, dass alle anderen Programme versuchen werden, "gut" zu spielen, indem sie die beste Antwort basierend auf der letzten Runde auswählen. Daher wählt dieser "Überschätzer" immer die schlechteste Position basierend auf der vorherigen Runde.

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

Java - Gewichtheber

Durchläuft 1-999, um herauszufinden, welches für jede Runde das Beste ist. Wiegt sie nach Aktualität (die letzten Runden haben mehr Gewicht) und gibt die beste Gesamtschätzung zurück. Wenn sich später Muster bilden, können diese hoffentlich aufgreifen.

Edit: Jetzt mit + Inf% mehr Rekursion! Nicht in der Lage zu sein, zu speichern oder zu sehen, was Sie in früheren Runden ausgewählt haben, ist ein Hindernis. Wenn Sie Ihre eigenen Eingaben berücksichtigen, werden Sie durcheinander gebracht, wenn Sie versuchen, herauszufinden, was andere tun werden. Also, lasst es uns berechnen! Dies wird nun wiederkehren, um herauszufinden, was es in der vorherigen Runde gewählt hat, und dies ignorieren, wenn der nächste Zug berechnet wird.

Beachten Sie, dass es nur seine eigenen Eingaben aus der letzten Runde wirklich ignoriert, aber da diese am höchsten gewichtet sind, scheint es in Ordnung zu funktionieren. Dies könnte mit ein bisschen mehr Arbeit behoben werden, aber ich werde auf die Bestenliste warten, um zu sehen, ob sie benötigt wird.

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

Ruby, Nachahmer

Gibt einfach die Zahl zurück, die beim letzten Mal gewonnen wurde.

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

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

Es ist wahrscheinlich die einfachste Strategie. Es findet die größte Lücke in der letzten Runde und wählt die Zahl genau in der Mitte dieser Lücke.

Gustav (Python 2)

Dies ist eine ziemlich direkte Metastrategie , die schamlos von einer meiner alten Antworten in einer ähnlichen KotH-Herausforderung kopiert wurde. Es werden ein paar einfache Strategien betrachtet, wie sie sich in allen vorherigen Runden entwickelt hätten, und dann die höchste Punktzahl für die nächste Runde.

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]

Mir ist jetzt klar, dass der Algorithmus noch einige Fehler aufweist. ZB könnte es "sich selbst jagen", weil es seine eigenen Züge nicht von denen der Gegner unterscheidet. Ich lasse es aber erstmal so.

Python, Randu

Zahlen, die vom schlechtesten Zufallsgenerator aller Zeiten ausgewählt wurden .

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

Die folgenden drei Programme sind integriert.

Hoch (Rubin)

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

Inkrementierer (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

Python, Sampler

Wählen Sie aus der Liste der Orte den aus, der von den zuletzt verwendeten Zahlen am weitesten entfernt ist, und ignorieren Sie dabei den vorherigen Zug.

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

Java, BounceInwards

Ab 1 nähert es sich allmählich dem Wert 500, während zwischen der höheren und der niedrigeren Option gewechselt wird.

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

NastyMathematician (Java)

Untersucht die letzten beiden Runden (wenn die besten Zahlen 70 und 80 waren, wird 90 ausgegeben). Es ist böse, weil es versucht, so viele Zahlen wie möglich zu sammeln, um gegen seine Gegner zu gewinnen.

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

Python - Ich möchte nicht an einen Namen denken ...

Wenn der Durchschnitt der in den letzten Runden gewählten Zahlen weniger als 500 beträgt, werden 999 ausgewählt. Andernfalls wird 1 ausgewählt.

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

Python, Middleman (basierend auf Conservator von @clabacchio)

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

Nachdem ich gemerkt hatte, dass die obere Kante hoch abschneidet (und die untere Kante übertrifft), fragte ich mich, ob es etwas Schlimmeres geben könnte, als nur in der Mitte hängen zu bleiben.

Jumper (Rubin)

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

Wechselt zwischen unten, Mitte und oben. (5.500.995)