Każdy gracz ma numer. Czy twój może być najdalszy od nich wszystkich?

Wymagania

Napisz nazwaną funkcję Java, Python 2 lub Ruby, choose()która akceptuje trzy argumenty:

• liczba całkowita - liczba już ukończonych rund
• liczba całkowita - liczba graczy
• tablica ciągów - wyniki każdej poprzedniej rundy
  • każdy ciąg jest oddzieloną spacjami listą liczb całkowitych, posortowaną od najniższej do najwyższej

Na przykład choose(2, 4, ["4 93 93 174", "1 84 234 555"])oznacza:

• były już dwie rundy (jest to trzecia runda)
• w sumie jest czterech graczy
• w pierwszej rundzie wybrano 4, 93, 93, 174
• w drugiej rundzie wybrano 1, 84, 234, 555

Musisz zwrócić liczbę całkowitą od 1 do 999 (włącznie).

Dla każdego innego gracza twój wynik jest pierwiastkiem kwadratowym odległości między twoim numerem a jego. Twój wynik w rundzie jest sumą wszystkich tych wyników.

Rozegranych zostanie 100 rund. Najwyższy łączny wynik wygrywa!

Zasady

• Twój kod nie może wykorzystywać żadnych wejść / wyjść, w tym konsoli, plików, sieci itp.
• Nie możesz ingerować w program kontroli lub innych graczy.
• Programy, które wyglądają, jakby naruszały powyższe zasady, zostaną wykluczone.
• Każde wywołanie funkcji powinno zająć na moim komputerze mniej niż pięć sekund (Intel Core i5 2450M z 8 GB pamięci RAM).
• Jeśli program zgłosi wyjątek lub zwróci nieprawidłową wartość, zostanie potraktowany tak, jakby zwrócił 1.
• Każdy użytkownik może zgłosić maksymalnie jeden program.

Różne

• Program sterujący znajduje się na GitHub .
• Istnieją trzy wbudowane odtwarzacze. Można je znaleźć w tej odpowiedzi .
• Zwycięzca zostanie wybrany 28 stycznia.

Tabela liderów

Zwycięzcą zostaje Konserwator .

Wyróżnienie dla Gustava , gracza o najwyższym wyniku z niestałą strategią.

• Konserwator - 36226
• Wysoka - 36115
• FloorHugger - 35880
• NumberOne - 35791
• Overestimator - 35791
• Gustav - 35484
• Historyk - 35201
• Próbnik - 34960
• Inkrementator - 34351
• JumpRightIn - 34074
• Vickrey - 34020
• Nastolatek - 33907
• Randu - 33891
• Sztangista - 33682
• Pośrednik - 33647
• BounceInwards - 33529
• Nasty Matematyk - 33292
• Zworka - 33244
• Copycat - 33049

Pełne wyniki można znaleźć tutaj . (Zalecam wyłączenie zawijania tekstu).

Python, konserwator

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

Ponieważ każdy wyjątek wyrzuca 1, pozostaje jak najdalej od niego. Robi fortunę kosztem słabych.

Ciekawostka: myślałem o jej ulepszeniu, ale nie mogłem znaleźć lepszego sposobu niż tylko ukrywanie się w kącie.

Numer jeden, Java

Nazwa wyjaśnia to całkowicie.

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

Python, AncientHistorian

Mocno wierzy, że przyszłość będzie dokładnie taka, jak przeszłość, ale wierzy, że ostatnia runda jest zbyt niedawna, by być histiryną, więc po prostu przechodzi przez 1 - 999 i wybiera to, co byłoby najlepsze w poprzednich rundach oprócz ostatniej. Pierwsza 2 runda zwraca 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

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)

Tworzy listę często granych liczb, zakłada, że ​​wszyscy inni będą grać optymalnie i wybiera drugi najlepszy wybór na tej liście.

Na przykład, jeśli najczęściej występującymi liczbami są [1, 990, 999], to Vickrey wstawia optymalną grę 200, aby dać [1, 200, 990, 999], a następnie wybiera najlepszą opcję dla nowej tablicy (czyli 556).

Java, Overestimator

Jak sama nazwa wskazuje, ten program zakłada, że ​​wszystkie inne programy będą próbowały grać „dobrze”, wybierając najlepszą odpowiedź na podstawie ostatniej rundy - więc ten „przeważnik” zawsze wybiera najgorszą możliwą pozycję na podstawie poprzedniej rundy.

 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 - sztangista

Pętle od 1 do 999, aby dowiedzieć się, który byłby najlepszy dla każdej rundy. Waży je zgodnie z aktualnością (ostatnie rundy mają większą wagę) i zwraca swoje najlepsze ogólne przypuszczenie. Mam nadzieję, że jeśli w późniejszej rundzie pojawią się wzory, będzie w stanie to odebrać.

Edycja: teraz z + Inf% większą rekurencją! Brak możliwości zapisywania / zapisywania / sprawdzania tego, co wybrałeś w poprzednich rundach, jest utrapieniem. Biorąc pod uwagę własne dane wejściowe, nie możesz się doczekać, kiedy spróbujesz dowiedzieć się, co zrobią inni . Obliczmy to! To teraz powróci, aby dowiedzieć się, co wybrał w poprzedniej rundzie i zignoruje to podczas obliczania następnego ruchu.

Zauważ, że tak naprawdę ignoruje tylko swój własny wkład z ostatniej tury, ale ponieważ ta jest ważona najwyżej, wydaje się, że działa dobrze. Można to naprawić przy odrobinie pracy, ale poczekam, aż tablica wyników sprawdzi, czy jest potrzebna.

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, naśladowca

Po prostu zwraca dowolną liczbę wygraną ostatnim razem.

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

To chyba najprostsza strategia. Znajduje największą lukę w ostatniej rundzie i wybiera liczbę dokładnie na środku tej luki.

Gustav (Python 2)

Jest to dość prosta strategia meta, bezwstydnie skopiowana z jednej z moich starych odpowiedzi w podobnym wyzwaniu KotH. Bierze pod uwagę kilka prostych strategii, wygląda, jak by się sprawdziły we wszystkich poprzednich rundach, a następnie podąża za najlepszą w następnej rundzie.

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]

Teraz zdaję sobie sprawę, że algorytm wciąż ma pewne wady. Np. Może „gonić się”, ponieważ nie odróżnia własnych ruchów od ruchów przeciwników. Jednak na razie zostawię to w ten sposób.

Python, Randu

Liczby wybrane przez najbardziej nieprzemyślany generator liczb losowych w historii .

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

Wbudowane są następujące trzy programy.

Wysoki (rubinowy)

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

Python, Sampler

Z listy miejsc wybierz tę, która jest najbardziej oddalona od ostatnio używanych liczb, ignorując poprzednią kolejkę.

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

Począwszy od 1, stopniowo zbliża się do 500, odbijając się między wyższą i niższą opcją.

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

NastyMathematician (Java)

Sprawdza dwie ostatnie rundy (jeśli najlepszymi liczbami były 70 i 80, wyświetli 90). Jest to paskudne, ponieważ stara się zdobyć jak najwięcej liczb, aby wygrać z przeciwnikami.

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 - nie chcę wymyślić imienia ...

Jeśli średnia liczb wybranych w poprzednich rundach jest mniejsza niż 500, wybiera 999. W przeciwnym razie wybiera 1.

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 (na podstawie konserwatora autorstwa @clabacchio)

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

Po tym, jak zauważyłem, że górna krawędź osiąga wysokie wyniki (i przewyższa dolną krawędź), zastanawiałem się, czy może być coś gorszego niż po prostu złapanie się na środku.

Sweter (Rubinowy)

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

Przełącza między dolnym, środkowym i górnym. (5500,995)