Mantenha distância!

15

Todo jogador tem um número. O seu pode ser o mais distante deles?

Exigências

Escreva uma função Java, Python 2 ou Ruby nomeada choose()que aceite três argumentos:

  • um inteiro - o número de rodadas já concluídas
  • um número inteiro - o número de jogadores
  • uma matriz de strings - os resultados de cada rodada anterior
    • cada sequência é uma lista de números inteiros separados por espaço, classificados do menor para o maior

Por exemplo, choose(2, 4, ["4 93 93 174", "1 84 234 555"])significa:

  • já havia duas rodadas (esta é a terceira rodada)
  • há um total de quatro jogadores
  • na primeira rodada, os números escolhidos foram 4, 93, 93, 174
  • na segunda rodada, os números escolhidos foram 1, 84, 234, 555

Você deve retornar um número inteiro de 1 a 999 (inclusive).

Para cada outro jogador, sua pontuação é a raiz quadrada da distância entre seu número e o deles. Sua pontuação para a rodada é o total de todas essas pontuações.

100 rodadas serão jogadas. A pontuação total mais alta vence!

Regras

  • Seu código não pode usar nenhuma E / S, incluindo console, arquivos, rede, etc.
  • Você não pode interferir com o programa de controle ou com outros jogadores.
  • Programas que parecem violar as regras acima serão excluídos.
  • Cada chamada de uma função deve levar menos de cinco segundos no meu computador (Intel Core i5 2450M com 8 GB de RAM).
  • Se um programa lançar uma exceção ou retornar um valor inválido, será tratado como se retornasse 1.
  • Cada usuário pode enviar no máximo um programa.

Diversos

  • O programa de controle está no GitHub .
  • Existem três players embutidos. Eles podem ser encontrados nesta resposta .
  • O vencedor será escolhido no dia 28 de janeiro.

Entre os melhores

O vencedor é Conservator .

Menção honrosa a Gustav , o jogador com maior pontuação com uma estratégia não constante.

  • Conservator - 36226
  • Alto - 36115
  • FloorHugger - 35880
  • NumberOne - 35791
  • Superestimador - 35791
  • Gustav - 35484
  • Historiador - 35201
  • Amostrador - 34960
  • Incrementador - 34351
  • JumpRightIn - 34074
  • Vickrey - 34020
  • Adolescente - 33907
  • Randu - 33891
  • Halterofilista - 33682
  • Middleman - 33647
  • BounceInwards - 33529
  • NastyMathematician - 33292
  • Jumper - 33244
  • Copiador - 33049

Os resultados completos podem ser encontrados aqui . (Eu recomendo desativar a quebra de texto.)

Ypnypn
fonte
Eu tenho alguma maneira de dizer qual era meu número nas rodadas anteriores?
Martin Ender
@ MartinBüttner No.
Ypnypn
1
Eu não conheço nenhuma dessas línguas :( Você pode adicionar JavaScript Como, executá-lo com node.js?
Cilan
1
@ TheWobbuffet, também não conheço nenhum deles. Não me impediu de fazer uma entrada em Python.
Mark
7
Eu acho que teria sido mais interessante se o espaço fosse um círculo / loop, de modo que a distância entre 1 e 999 seja 1. Isso impediria o "palpite de um número único a cada turno" de dominar, já que não há "arestas" para estacionar. Obviamente tarde demais para mudar agora embora;)
Geobits

Respostas:

9

Python, Conservator

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

Como toda exceção gera 1, ela fica afastada o máximo possível. Faz fortuna às custas dos fracos.

Curiosidade: pensei em melhorá-lo, mas não consegui encontrar uma maneira melhor do que apenas me esconder em um canto.

clabacchio
fonte
1
Parece que escolhi o canto errado. :(
TheNumberOne 23/01
É bom por uma razão simples: outros tentam minimizar a distância para você. Eles automaticamente melhorarão sua pontuação. Um divisor de águas seria um oponente que tenta chegar o mais perto possível de você.
Martin Thoma
1
Eca ... um ponto e vírgula em Python?
KSFT 30/01
@KSFT hehe Estou enferrujado em Python, e eu nunca fui esse especialista de qualquer maneira
clabacchio
6

Número Um, Java

O nome explica este completamente.

public static int choose(int round, int players, String[] args) {
    return 1;
}
O número um
fonte
1
Por que o voto negativo?
TheNumberOne 22/01
5
Eu particularmente gosto de como o nome de usuário laços para a apresentação
Brian J
5

Python, AntigoHistória

Acredita firmemente que o futuro será exatamente como o passado, mas acredita que a última rodada é muito recente para ser histórica, por isso apenas passa de 1 a 999 e escolhe o que teria sido o melhor das rodadas anteriores, com exceção da última. O primeiro turno 2 retorna 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
Maltysen
fonte
4

Vickrey Python

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)

Faz uma lista dos números que foram reproduzidos com frequência, assume que todos os demais reproduzem da melhor maneira e opta pelo segunda melhor opção, dada a lista.

Por exemplo, se os números mais comuns são [1, 990, 999], então Vickrey insere o jogo ideal 200 a [1, 200, 990, 999]ser fornecido e escolhe a melhor opção para o novo array (que é 556).

Sp3000
fonte
4

Java, superestimador

Como o nome sugere, este programa assume que todos os outros programas tentarão "jogar bem" escolhendo a melhor resposta com base na última rodada - portanto, esse "superestimador" sempre escolhe a pior posição possível com base na rodada anterior.

 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;
 }
Alex Walker
fonte
Como é que isso tocou um "1" constante? Houve algum erro? Lembre-se, jogar "1" provou ser bastante bem-sucedido. :)
Emil
Infelizmente, o código tem um erro, sim - ele nunca analisa as pontuações que lê da última rodada. (Mas eu percebi tarde demais e parecia errado para editar uma submissão até então, além de como você diz que estava fazendo muito bem até ... o: p)
Alex Walker
4

Java - Halterofilista

Repete de 1 a 999 para descobrir qual seria o melhor para cada rodada. Pesa-os de acordo com o tempo recente (as rodadas recentes têm mais peso) e retorna sua melhor estimativa geral. Esperemos que, se os padrões se formarem na rodada seguinte, isso será possível.

Edit: Agora com + Inf% mais recursão! Não conseguir armazenar / salvar / ver o que você escolheu nas rodadas anteriores é uma chatice. Levar em consideração suas próprias entradas atrapalha você quando tenta descobrir o que os outros farão. Então, vamos calcular! Agora será necessário descobrir o que ele escolheu na rodada anterior e ignorar isso ao calcular o próximo movimento.

Observe que ele realmente apenas ignora suas próprias informações desde o último turno, mas como essa é a mais alta, parece funcionar bem. Isso pode ser corrigido com um pouco mais de trabalho, mas vou aguardar o placar de líderes para ver se é necessário.

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;
}
Geobits
fonte
Nota: Mesmo na rodada 100, ele é concluído em menos de um segundo no meu PC um tanto lento. Se demorar algum tempo no seu por algum motivo, avise-me para que eu possa limitar a recursão.
Geobits
É muito rápido na minha máquina também.
Ypnypn 23/01
3

Ruby, Copycat

Simplesmente retorna o número ganho na última vez.

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
Maçaneta da porta
fonte
1
O que ele retorna na primeira rodada? Oh não importa. Exceções voltaria 1.
mbomb007
3

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

É provavelmente a estratégia mais direta. Ele encontra a maior lacuna na última rodada e escolhe o número bem no meio dessa lacuna.

Martin Ender
fonte
O que ele retorna na primeira rodada? 1?
mbomb007
@ mbomb007 Ah, eu sempre esqueço essas rodadas iniciais traquinas. Obrigado, agora retorna 500.
Martin Ender
3

Gustav (Python 2)

Esta é uma meta-estratégia bastante direta, copiada descaradamente de uma das minhas respostas antigas em um desafio semelhante ao KotH. Ele considera algumas estratégias simples, analisa como elas teriam se saído em todas as rodadas anteriores e depois segue a de maior pontuação na próxima rodada.

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]

Percebo agora que o algoritmo ainda tem algumas falhas. Por exemplo, pode continuar "perseguindo a si próprio" porque não distingue seus próprios movimentos dos dos oponentes. No entanto, vou deixar assim por enquanto.

Emil
fonte
1

Os três programas a seguir estão embutidos.

Alto (Ruby)

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

Incrementador (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
Ypnypn
fonte
1

Python, Sampler

Fora de uma lista de lugares, escolha o que está mais distante dos números usados ​​recentemente, ignorando a curva anterior.

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
Cavaleiro Lógico
fonte
1

Java, BounceInwards

Começando em 1, ele gradualmente se aproxima de 500 enquanto alterna entre a opção superior e a inferior.

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

NastyMathematician (Java)

Examina as duas últimas rodadas (se os melhores números forem 70 e 80, produzirá 90). É desagradável porque tenta levar o maior número possível de vitórias contra seus oponentes.

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;
}
CommonGuy
fonte
1

Python - não quero pensar em um nome ...

Se a média dos números escolhidos nas rodadas anteriores for inferior a 500, ele escolhe 999. Ele escolhe 1 caso contrário.

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
KSFT
fonte
0

Python, Middleman (baseado no conservador de @clabacchio)

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

Depois que notei que a borda superior tem uma pontuação alta (e superou a borda inferior), perguntei-me se poderia haver algo pior do que ficar preso no meio.

Dennis Jaheruddin
fonte
0

Jumper (Ruby)

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

Alterna entre inferior, médio e superior. (5.500.995)

MegaTom
fonte