¡Mantén tu distancia!

15

Cada jugador tiene un número. ¿Puede el tuyo ser el más alejado de todos?

Requisitos

Escriba una función Java, Python 2 o Ruby llamada choose()que acepte tres argumentos:

  • un número entero: el número de rondas ya completadas
  • un número entero: el número de jugadores
  • una serie de cadenas: los resultados de cada ronda anterior
    • cada cadena es una lista de enteros separados por espacios, ordenados de menor a mayor

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

  • ya había dos rondas (esta es la tercera ronda)
  • hay un total de cuatro jugadores
  • en la primera ronda, los números elegidos fueron 4, 93, 93, 174
  • en la segunda ronda, los números elegidos fueron 1, 84, 234, 555

Debe devolver un número entero del 1 al 999 (inclusive).

Para cada otro jugador, su puntaje es la raíz cuadrada de la distancia entre su número y el de ellos. Su puntaje para la ronda es el total de todos estos puntajes.

Se jugarán 100 rondas. ¡El puntaje total más alto gana!

Reglas

  • Su código no puede usar ninguna E / S, incluida la consola, los archivos, la red, etc.
  • No puede interferir con el programa de control ni con ningún otro jugador.
  • Los programas que parecen violar las reglas anteriores serán excluidos.
  • Cada llamada de una función debería tomar menos de cinco segundos en mi computadora (Intel Core i5 2450M con 8GB de RAM).
  • Si un programa arroja una excepción o devuelve un valor no válido, se tratará como si devolviera 1.
  • Cada usuario puede enviar como máximo un programa.

Diverso

  • El programa de control está en GitHub .
  • Hay tres jugadores incorporados. Se pueden encontrar en esta respuesta .
  • El ganador será elegido el 28 de enero.

Tabla de clasificación

El ganador es Conservador .

Mención de honor a Gustav , el jugador con el puntaje más alto con una estrategia no constante.

  • Conservador - 36226
  • Alto - 36115
  • FloorHugger - 35880
  • NumberOne - 35791
  • Sobreestimador - 35791
  • Gustav - 35484
  • Historiador - 35201
  • Muestreador - 34960
  • Incrementador - 34351
  • JumpRightIn - 34074
  • Vickrey - 34020
  • Adolescente - 33907
  • Randu - 33891
  • Levantador de pesas - 33682
  • Intermediario - 33647
  • BounceInwards - 33529
  • Desagradable matemático - 33292
  • Puente - 33244
  • Copycat - 33049

Los resultados completos se pueden encontrar aquí . (Recomiendo deshabilitar el ajuste de texto).

Ypnypn
fuente
¿Tengo alguna forma de saber cuál era mi propio número en esas rondas anteriores?
Martin Ender
@ MartinBüttner No.
Ypnypn
1
No conozco ninguno de esos idiomas :( ¿Podría agregar JavaScript? Me gusta, ejecutarlo con node.js?
Cilan
1
@TheWobbuffet, tampoco conozco ninguno de ellos. No me impidió hacer una entrada en Python.
Mark
77
Creo que habría sido más interesante si el espacio fuera un círculo / bucle, de modo que la distancia entre 1 y 999 sea 1. Eso evitaría que dominara "adivinar un solo número cada turno", ya que no hay "bordes" para estacionar Obviamente, demasiado tarde para cambiar ahora;)
Geobits

Respuestas:

9

Python, conservador

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

Como cada excepción arroja 1, se mantiene lo más alejado posible. Hace su fortuna a expensas de los débiles.

Dato curioso: pensé en mejorarlo, pero no pude encontrar una mejor manera que solo esconderme en un rincón.

clabacchio
fuente
1
Parece que elegí la esquina equivocada. :(
TheNumberOne
Es bueno por una simple razón: otros intentan minimizar la distancia a usted. Mejorarán automáticamente su puntaje. Un cambiador de juego sería un oponente que trata de acercarse lo más posible a usted.
Martin Thoma
1
Eww ... un punto y coma en Python?
KSFT
@KSFT jeje Estoy oxidado en Python, y nunca he sido tan experto de todos modos
clabacchio
6

Número uno, Java

El nombre lo explica completamente.

public static int choose(int round, int players, String[] args) {
    return 1;
}
El numero uno
fuente
1
¿Por qué el voto negativo?
TheNumberOne
55
Me gusta especialmente cómo se vincula el nombre de usuario con el envío
Brian J
5

Python, AncientHistorian

Cree firmemente que el futuro será exactamente como el pasado, pero cree que la última ronda es demasiado reciente para ser histórica, por lo que solo recorre 1 - 999 y elige lo que hubiera sido lo mejor que las rondas anteriores a excepción de la última. Las primeras 2 rondas devuelven 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
fuente
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)

Hace una lista de números que se han jugado a menudo, supone que todos los demás jugarán de manera óptima y opta por la segunda mejor opción dada la lista.

Por ejemplo, si los números más comunes son [1, 990, 999], entonces Vickrey inserta la jugada óptima 200 para dar [1, 200, 990, 999], luego elige la mejor opción para la nueva matriz (que es 556).

Sp3000
fuente
4

Java, sobreestimador

Como su nombre lo indica, este programa asume que todos los demás programas intentarán jugar "bien" eligiendo la mejor respuesta basada en la última ronda, por lo que este "sobreestimador" siempre elige la peor posición posible en función de la ronda 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
fuente
¿Cómo es que esto jugó un "1" constante? ¿Hubo un error? Eso sí, jugar "1" demostró ser bastante exitoso. :)
Emil
Lamentablemente, el código tiene un error, sí, en realidad nunca analiza los puntajes que lee de la última ronda. (Pero me di cuenta de que era demasiado tarde y parecía incorrecto editar una presentación para entonces, además, como dices, lo estaba haciendo bastante bien, así que ... lo que sea: p)
Alex Walker
4

Java - levantador de pesas

Recorre 1-999 para descubrir cuál sería el mejor para cada ronda. Los pesa de acuerdo con lo reciente (las rondas recientes tienen más peso) y devuelve su mejor estimación general. Con suerte, si los patrones se forman en una ronda posterior, esto podrá detectarlo.

Editar: ¡Ahora con + Inf% más recursividad! No poder almacenar / guardar / ver lo que elegiste en rondas anteriores es un lastre. Tener en cuenta sus propios aportes lo arruina cuando intenta averiguar qué van a hacer los demás . ¡Entonces, calculemoslo! Esto ahora se repetirá para descubrir qué eligió en la ronda anterior e ignorarlo al calcular el próximo movimiento.

Tenga en cuenta que sólo realmente ignora su propia entrada desde la última vez, pero desde que uno se pondera el más alto, parece que funciona bien. Esto podría solucionarse con un poco más de trabajo, pero esperaré a que la tabla de clasificación vea si es necesario.

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
fuente
Nota: Incluso en la ronda 100, se completa en menos de un segundo en mi PC algo lenta. Si se demora demasiado en el tuyo por alguna razón, avísame para que pueda limitar la recurrencia.
Geobits
También es muy rápido en mi máquina.
Ypnypn
3

Rubí, imitador

Simplemente devuelve el número ganado la ú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
Pomo de la puerta
fuente
1
¿Qué devuelve para la primera ronda? Oh no importa. Las excepciones regresarían 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

Es probablemente la estrategia más directa. Encuentra la brecha más grande en la última ronda y elige el número justo en el medio de esa brecha.

Martin Ender
fuente
¿Qué devuelve para la primera ronda? 1?
mbomb007
@ mbomb007 Oh, siempre olvido estas molestas rondas iniciales. Gracias, ahora devuelve 500.
Martin Ender
3

Gustav (Python 2)

Esta es una metaestrategia bastante directa, copiada descaradamente de una de mis viejas respuestas en un desafío KotH similar. Considera algunas estrategias simples, observa cómo se habrían desempeñado en todas las rondas anteriores y luego sigue la puntuación más alta para la próxima ronda.

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]

Ahora me doy cuenta de que el algoritmo todavía tiene algunos defectos. Por ejemplo, podría seguir "persiguiéndose a sí mismo" porque no distingue sus propios movimientos de los de los oponentes. Sin embargo, lo dejaré así por ahora.

Emil
fuente
1

Los siguientes tres programas están integrados.

Alto (rubí)

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
fuente
1

Python, Sampler

De una lista de lugares, elija el que esté más alejado de los números usados ​​recientemente, ignorando el turno 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
Caballero Lógico
fuente
1

Java, BounceInwards

Comenzando en 1, gradualmente se acerca a 500 mientras rebota entre la opción más alta y más baja.

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

NastyMathematician (Java)

Examina las dos últimas rondas (si los mejores números fueron 70 y 80, arrojará 90). Es desagradable porque trata de obtener el mayor número posible para ganar contra sus 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
fuente
1

Python: no quiero pensar en un nombre ...

Si el promedio de los números elegidos en las rondas anteriores es inferior a 500, elige 999. De lo contrario, elige 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
KSFT
fuente
0

Python, Middleman (basado en el conservador de @clabacchio)

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

Después de notar que el borde superior tiene un puntaje alto (y superó al borde inferior), me pregunté si podría haber algo peor que quedar atrapado en el medio.

Dennis Jaheruddin
fuente
0

Saltador (Ruby)

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

Alterna entre la parte inferior, media y superior. (5,500,995)

MegaTom
fuente