Pegue ou largue: um game show para computadores

28

Contexto:

Um bilionário recluso criou um game show para atrair os melhores e mais brilhantes programadores do mundo. Às segundas-feiras, à meia-noite, ele escolhe uma pessoa de um grupo de candidatos para ser o competidor da semana e oferece a eles um jogo. Você é o sortudo participante desta semana!

O jogo desta semana:

O host fornece acesso à API para uma pilha de 10.000 envelopes digitais. Esses envelopes são classificados aleatoriamente e contêm um valor em dólar entre US $ 1 e US $ 10.000 (dois envelopes não contêm o mesmo valor em dólar).

Você tem 3 comandos à sua disposição:

  1. Read (): Leia a figura do dólar no envelope na parte superior da pilha.

  2. Pegue (): adicione a figura do dólar no envelope à sua carteira de game show e tire o envelope da pilha.

  3. Pass (): Retire o envelope na parte superior da pilha.

As regras:

  1. Se você usar Pass () em um envelope, o dinheiro dentro será perdido para sempre.

  2. Se você usar Take () em um envelope contendo $ X, a partir desse momento, nunca poderá usar Take () em um envelope contendo <$ X. Take () em um desses envelopes adicionará US $ 0 à sua carteira.

Escreva um algoritmo que termine o jogo com a quantidade máxima de dinheiro.

Se você estiver escrevendo uma solução em Python, sinta-se à vontade para usar este controlador para testar algoritmos, cortesia de @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Se você usar o controlador, não poderá acessar globais, poderá usar apenas os 3 comandos API fornecidos e as variáveis ​​com escopo local. (@Beta Decay)

Notas: "Máximo", neste caso, significa o valor mediano na sua carteira após N> 50 execuções. Espero, apesar de gostar de provar que estou errado, que o valor mediano de um determinado algoritmo converja à medida que N aumenta para o infinito. Sinta-se à vontade para tentar maximizar a média, mas tenho a sensação de que é mais provável que a média seja descartada por um N pequeno do que a mediana.

Editar: alterou o número de envelopes para 10k para facilitar o processamento e tornou Take () mais explícito.

Edit 2: A condição do prêmio foi removida, à luz desta postagem na meta.

Pontuações máximas atuais:

PhiNotPi - $ 805.479

Reto Koradi - $ 803.960

Dennis - US $ 770.272 (revisado)

Alex L. - US $ 714.962 (revisado)

LivingInformation
fonte
Eu implementei de uma maneira que apenas retorne False. Desde que você pode lê-lo não há verdadeiro ponto de falhar o jogo inteiro em um take falhou ()
OganM
4
No caso de alguém quiser usá-lo, aqui é o controlador que eu tenho usado para testar meus algoritmos: gist.github.com/Maltysen/5a4a33691cd603e9aeca
Maltysen
8
Pergunta PS agradável e bem-vindo à programação Puzzles e Código Golf :)
Trichoplax
3
@ Maltysen Coloquei seu controlador no OP, obrigado pela contribuição!
LivingInformation
1
Não consegui encontrar uma regra explícita nos prêmios de bitcoin, mas há algumas meta-discussões sobre prêmios do mundo real com as quais as pessoas podem contribuir.
Trichoplax

Respostas:

9

CJam, $ 87.143 $ 700.424 $ 720.327 $ 727.580 $ 770.272

{0:T:M;1e4:E,:)mr{RM>{RR(*MM)*-E0.032*220+R*<{ERM--:E;R:MT+:T;}{E(:E;}?}&}fRT}
[easi*]$easi2/=N

Este programa simula o jogo inteiro várias vezes e calcula a mediana.

Como executar

Marquei minha inscrição fazendo 100.001 execuções de teste:

$ time java -jar cjam-0.6.5.jar take-it-or-leave-it.cjam 100001
770272

real    5m7.721s
user    5m15.334s
sys     0m0.570s

Aproximação

Para cada envelope, fazemos o seguinte:

  • Estime a quantidade de dinheiro que inevitavelmente será perdida ao pegar o envelope.

    Se R é o conteúdo e M é o máximo que foi obtido, a quantidade pode ser estimada em R (R-1) / 2 - M (M + 1) / 2 , que fornece ao dinheiro todos os envelopes com o conteúdo X no intervalo (M, R) contém.

    Se nenhum envelope tivesse sido passado ainda, a estimativa seria perfeita.

  • Calcule a quantia que inevitavelmente será perdida passando o envelope.

    Este é simplesmente o dinheiro que o envelope contém.

  • Verifique se o quociente de ambos é menor que 110 + 0,016E , onde E é o número de envelopes restantes (sem contar os envelopes que não podem mais ser utilizados).

    Se sim, pegue. Caso contrário, passe.

Dennis
fonte
5
Porque usar uma linguagem de golfe ajuda de qualquer maneira. ; P +1 para o algo.
Maltysen 31/07/2015
2
Não consigo replicar seus resultados usando um clone do Python: gist.github.com/orlp/f9b949d60c766430fe9c . Você ganha cerca de US $ 50.000. Isso é uma ordem de magnitude fora.
Orlp 01/08/2015
1
@LivingInformation Tentativa e erro. Atualmente, estou olhando para usar a quantidade exata em vez de estimativas, mas o código resultante é muito lento.
Dennis
2
Esta resposta precisa de mais votos do que a minha! É mais inteligente, pontua mais e ainda joga golfe!
Alex L
1
@LivingInformation Este é o meu endereço: 17uLHRfdD5JZ2QjSqPGQ1B12LoX4CgLGuV
Dennis
7

Python, $ 680.646 $ 714.962

f = (float(len(stack)) / 10000)
step = 160
if f<0.5: step = 125
if f>0.9: step = 190
if read() < max_taken + step:
    take()
else:
    passe()

Toma quantidades cada vez maiores em etapas de tamanho entre US $ 125 e US $ 190. Funcionou com N = 10.000 e obteve uma mediana de US $ 714962. Esses tamanhos de etapas vieram de tentativa e erro e certamente não são ideais.

O código completo, incluindo uma versão modificada do controlador do @ Maltysen, que imprime um gráfico de barras enquanto é executado:

import random
N = 10000


def init_game():
    global stack, wallet, max_taken
    stack = list(range(1, 10001))
    random.shuffle(stack)
    wallet = max_taken = 0

def read():
    return stack[0]

def take():
    global wallet, max_taken
    amount = stack.pop(0)
    if amount > max_taken:
        wallet += amount
        max_taken = amount

def passe():
    stack.pop(0)

def test(algo):
    results = []
    for _ in range(N):
        init_game()
        for i in range(10000):
            algo()
        results += [wallet]
        output(wallet)
    import numpy
    print 'max: '
    output(max(results))
    print 'median: '
    output(numpy.median(results))
    print 'min: '
    output(min(results))

def output(n):
    print n
    result = ''
    for _ in range(int(n/20000)):
        result += '-'
    print result+'|'

def alg():
    f = (float(len(stack)) / 10000)
    step = 160
    if f<0.5: step = 125
    if f>0.9: step = 190
    if read() < max_taken + step:
        #if read()>max_taken: print read(), step, f
        take()
    else:
        passe()

test(alg)

Endereço BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Uau OP entregue! Obrigado @LivingInformation!

Alex L
fonte
1
O controlador é de Maltysen, não meu.
orlp 01/08/15
2
Confirmado. Acabei de configurar um controlador e recebo números muito semelhantes para sua solução. A rigor, acho que você precisa manter o valor de max_takenseu próprio código, pois ele não faz parte da API oficial do jogo. Mas isso é trivial de se fazer.
Reto Koradi
1
Sim, max_taken está no controlador de @ Maltysen. Se for útil, posso postar a solução inteira (controlador + algoritmo) em um bloco.
Alex L
Realmente não é grande coisa. Mas acho que a abordagem mais limpa seria usar apenas os métodos read(), take()e pass()no código postado, pois esses são os "3 comandos à sua disposição" com base na definição na pergunta.
Reto Koradi
@Reto Estou disposto a revisar a pergunta para qualquer comando que faça mais sentido. Leia, Aceite e Passe eram todos os quatro caracteres e me pareciam adequados, mas estou aberto a sugestões (por exemplo, considerei mudar "passar" para "sair", porque intitulei a postagem "pegue ou largue" ").
LivingInformation
5

C ++, US $ 803.960

for (int iVal = 0; iVal < 10000; ++iVal)
{
    int val = game.read();
    if (val > maxVal &&
        val < 466.7f + 0.9352f * maxVal + 0.0275f * iVal)
    {
        maxVal = val;
        game.take();
    }
    else
    {
        game.pass();
    }
}

O resultado relatado é a mediana dos 10.001 jogos.

Reto Koradi
fonte
Adivinha e confira, eu aceito? Ou você usou algum tipo de fuzzer de entrada para as constantes?
LivingInformation
Eu executei um algoritmo de otimização para determinar as constantes.
Reto Koradi
Você acha que um cálculo dinâmico em cada ponto seria mais eficaz ou acha que isso está se aproximando do valor máximo que você pode receber?
LivingInformation
Não tenho motivos para acreditar que seja a estratégia ideal. Espero que seja o máximo para uma função linear com esses parâmetros. Eu tenho tentado permitir vários tipos de termos não lineares, mas até agora não encontrei nada significativamente melhor.
Reto Koradi
1
Posso confirmar que, ao simular isso, a pontuação relatada é de pouco mais de US $ 800.000.
orlp 2/08/2015
3

C ++, ~ $ 815.000

Baseado na solução de Reto Koradi, mas alterna para um algoritmo mais sofisticado quando restarem 100 envelopes (válidos), embaralhando permutações aleatórias e calculando a subsequência crescente mais pesada deles. Ele comparará os resultados de pegar e não levar o envelope e selecionará avidamente a melhor opção.

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>


void setmax(std::vector<int>& h, int i, int v) {
    while (i < h.size()) { h[i] = std::max(v, h[i]); i |= i + 1; }
}

int getmax(std::vector<int>& h, int n) {
    int m = 0;
    while (n > 0) { m = std::max(m, h[n-1]); n &= n - 1; }
    return m;
}

int his(const std::vector<int>& l, const std::vector<int>& rank) {
    std::vector<int> h(l.size());
    for (int i = 0; i < l.size(); ++i) {
        int r = rank[i];
        setmax(h, r, l[i] + getmax(h, r));
    }

    return getmax(h, l.size());
}

template<class RNG>
void shuffle(std::vector<int>& l, std::vector<int>& rank, RNG& rng) {
    for (int i = l.size() - 1; i > 0; --i) {
        int j = std::uniform_int_distribution<int>(0, i)(rng);
        std::swap(l[i], l[j]);
        std::swap(rank[i], rank[j]);
    }
}

std::random_device rnd;
std::mt19937_64 rng(rnd());

struct Algo {
    Algo(int N) {
        for (int i = 1; i < N + 1; ++i) left.insert(i);
        ival = maxval = 0;
    }

    static double get_p(int n) { return 1.2 / std::sqrt(8 + n) + 0.71; }

    bool should_take(int val) {
        ival++;
        auto it = left.find(val);
        if (it == left.end()) return false;

        if (left.size() > 100) {
            if (val > maxval && val < 466.7f + 0.9352f * maxval + 0.0275f * (ival - 1)) {
                maxval = val;
                left.erase(left.begin(), std::next(it));
                return true;
            }

            left.erase(it);
            return false;
        }

        take.assign(std::next(it), left.end());
        no_take.assign(left.begin(), it);
        no_take.insert(no_take.end(), std::next(it), left.end());
        take_rank.resize(take.size());
        no_take_rank.resize(no_take.size());
        for (int i = 0; i < take.size(); ++i) take_rank[i] = i;
        for (int i = 0; i < no_take.size(); ++i) no_take_rank[i] = i;

        double take_score, no_take_score;
        take_score = no_take_score = 0;
        for (int i = 0; i < 1000; ++i) {
            shuffle(take, take_rank, rng);
            shuffle(no_take, no_take_rank, rng);
            take_score += val + his(take, take_rank) * get_p(take.size());
            no_take_score += his(no_take, no_take_rank) * get_p(no_take.size());
        }

        if (take_score > no_take_score) {
            left.erase(left.begin(), std::next(it));
            return true;
        }

        left.erase(it);
        return false;
    }

    std::set<int> left;
    int ival, maxval;
    std::vector<int> take, no_take, take_rank, no_take_rank;
};


struct Game {
    Game(int N) : score_(0), max_taken(0) {
        for (int i = 1; i < N + 1; ++i) envelopes.push_back(i);
        std::shuffle(envelopes.begin(), envelopes.end(), rng);
    }

    int read() { return envelopes.back(); }
    bool done() { return envelopes.empty(); }
    int score() { return score_; }
    void pass() { envelopes.pop_back(); }

    void take() {
        if (read() > max_taken) {
            score_ += read();
            max_taken = read();
        }
        envelopes.pop_back();
    }

    int score_;
    int max_taken;
    std::vector<int> envelopes;
};


int main(int argc, char** argv) {
    std::vector<int> results;
    std::vector<int> max_results;
    int N = 10000;
    for (int i = 0; i < 1000; ++i) {
        std::cout << "Simulating game " << (i+1) << ".\n";
        Game game(N);
        Algo algo(N);

        while (!game.done()) {
            if (algo.should_take(game.read())) game.take();
            else game.pass();
        }
        results.push_back(game.score());
    }

    std::sort(results.begin(), results.end());
    std::cout << results[results.size()/2] << "\n";

    return 0;
}
orlp
fonte
Interessante. Havia me passado pela cabeça que seria possível melhorar observando os valores deixados nos últimos envelopes. Eu acho que você jogou com o ponto de corte em que você muda de estratégia? Está ficando muito lento se você mudar mais cedo? Ou os resultados estão realmente piorando?
Reto Koradi
@RetoKoradi Joguei com o ponto de corte, e os pontos de corte anteriores ficaram muito lentos e piores. Não é muito surpreendente, honestamente, a 100 envelopes já estamos amostragem uns meros 1000 permutações de um possível 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
orlp
3

Java, $ 806.899

Isto é de um teste de 2501 rodadas. Ainda estou trabalhando para otimizá-lo. Eu escrevi duas aulas, um invólucro e um jogador. O invólucro instancia o player com o número de envelopes (sempre 10000 para a coisa real) e depois chama o método takeQcom o valor do envelope superior. O jogador então retorna truese eles pegarem, falsese passarem.

Jogador

import java.lang.Math;

public class Player {
  public int[] V;

  public Player(int s) {
    V = new int[s];
    for (int i = 0; i < V.length; i++) {
      V[i] = i + 1;
    }
    // System.out.println();
  }

  public boolean takeQ(int x) {

    // System.out.println("look " + x);

    // http://www.programmingsimplified.com/java/source-code/java-program-for-binary-search
    int first = 0;
    int last = V.length - 1;
    int middle = (first + last) / 2;
    int search = x;

    while (first <= last) {
      if (V[middle] < search)
        first = middle + 1;
      else if (V[middle] == search)
        break;
      else
        last = middle - 1;

      middle = (first + last) / 2;
    }

    int i = middle;

    if (first > last) {
      // System.out.println(" PASS");
      return false; // value not found, so the envelope must not be in the list
                    // of acceptable ones
    }

    int[] newVp = new int[V.length - 1];
    for (int j = 0; j < i; j++) {
      newVp[j] = V[j];
    }
    for (int j = i + 1; j < V.length; j++) {
      newVp[j - 1] = V[j];
    }
    double pass = calcVal(newVp);
    int[] newVt = new int[V.length - i - 1];
    for (int j = i + 1; j < V.length; j++) {
      newVt[j - i - 1] = V[j];
    }
    double take = V[i] + calcVal(newVt);
    // System.out.println(" take " + take);
    // System.out.println(" pass " + pass);

    if (take > pass) {
      V = newVt;
      // System.out.println(" TAKE");
      return true;
    } else {
      V = newVp;
      // System.out.println(" PASS");
      return false;
    }
  }

  public double calcVal(int[] list) {
    double total = 0;
    for (int i : list) {
      total += i;
    }
    double ent = 0;
    for (int i : list) {
      if (i > 0) {
        ent -= i / total * Math.log(i / total);
      }
    }
    // System.out.println(" total " + total);
    // System.out.println(" entro " + Math.exp(ent));
    // System.out.println(" count " + list.length);
    return total * (Math.pow(Math.exp(ent), -0.5) * 4.0 / 3);
  }
}

Embrulho

import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;

public class Controller {
  public static void main(String[] args) {
    int size = 10000;
    int rounds = 2501;
    ArrayList<Integer> results = new ArrayList<Integer>();
    int[] envelopes = new int[size];
    for (int i = 0; i < envelopes.length; i++) {
      envelopes[i] = i + 1;
    }
    for (int round = 0; round < rounds; round++) {
      shuffleArray(envelopes);

      Player p = new Player(size);
      int cutoff = 0;
      int winnings = 0;
      for (int i = 0; i < envelopes.length; i++) {
        boolean take = p.takeQ(envelopes[i]);
        if (take && envelopes[i] >= cutoff) {
          winnings += envelopes[i];
          cutoff = envelopes[i];
        }
      }
      results.add(winnings);
    }
    Collections.sort(results);
    System.out.println(
        rounds + " rounds, median is " + results.get(results.size() / 2));
  }

  // stol... I mean borrowed from
  // http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
  static Random rnd = new Random();

  static void shuffleArray(int[] ar) {
    for (int i = ar.length - 1; i > 0; i--) {
      int index = rnd.nextInt(i + 1);
      // Simple swap
      int a = ar[index];
      ar[index] = ar[i];
      ar[i] = a;
    }
  }
}

Uma explicação mais detalhada estará disponível em breve, depois que eu terminar as otimizações.

A idéia central é poder estimar a recompensa de jogar um jogo de um determinado conjunto de envelopes. Se o conjunto atual de envelopes for {2,4,5,7,8,9} e o envelope superior for o 5, existem duas possibilidades:

  • Pegue o 5 e jogue com {7,8,9}
  • Passe o 5 e jogue {2,4,7,8,9}

Se calcularmos a recompensa esperada de {7,8,9} e compará-la com a recompensa esperada de {2,4,7,8,9}, seremos capazes de dizer se tirar 5 vale a pena.

Agora, a pergunta é: dado um conjunto de envelopes como {2,4,7,8,9} qual é o valor esperado? Descobri que o valor esperado parece ser proporcional à quantidade total de dinheiro no conjunto, mas inversamente proporcional à raiz quadrada do número de envelopes em que o dinheiro é dividido. Isso veio "perfeitamente" jogando vários jogos pequenos nos quais todos os envelopes têm valor quase idêntico.

O próximo problema é como determinar o " número efetivo de envelopes". Em todos os casos, o número de envelopes é conhecido exatamente acompanhando o que você viu e fez. Algo como {234.235.236} é definitivamente três envelopes, {231.232.233.234.235} é definitivamente 5, mas {1.2.234.235.236} deve realmente contar como 3 e não 5 envelopes, porque o 1 e o 2 são quase inúteis, e você nunca passaria em um 234. você poderia pegar um 1 ou 2. Mais tarde, tive a ideia de usar a entropia de Shannon para determinar o número efetivo de envelopes.

Eu direcionei meus cálculos para situações em que os valores do envelope são distribuídos uniformemente por algum intervalo, que é o que acontece durante o jogo. Se eu pegar {2,4,7,8,9} e tratar isso como uma distribuição de probabilidade, sua entropia é 1,50242. Então eu faço exp()para obter 4,49254 como o número efetivo de envelopes.

A recompensa estimada de {2,4,7,8,9} é 30 * 4.4925^-0.5 * 4/3 = 18.87

O número exato é 18.1167.

Essa não é uma estimativa exata, mas estou realmente orgulhosa de como isso se encaixa nos dados quando os envelopes são distribuídos uniformemente por um intervalo. Não tenho certeza do multiplicador correto (estou usando 4/3 por enquanto), mas aqui está uma tabela de dados excluindo o multiplicador.

Set of Envelopes                    Total * (e^entropy)^-0.5      Actual Score

{1,2,3,4,5,6,7,8,9,10}              18.759                        25.473
{2,3,4,5,6,7,8,9,10,11}             21.657                        29.279
{3,4,5,6,7,8,9,10,11,12}            24.648                        33.125
{4,5,6,7,8,9,10,11,12,13}           27.687                        37.002
{5,6,7,8,9,10,11,12,13,14}          30.757                        40.945
{6,7,8,9,10,11,12,13,14,15}         33.846                        44.900
{7,8,9,10,11,12,13,14,15,16}        36.949                        48.871
{8,9,10,11,12,13,14,15,16,17}       40.062                        52.857
{9,10,11,12,13,14,15,16,17,18}      43.183                        56.848
{10,11,12,13,14,15,16,17,18,19}     46.311                        60.857

A regressão linear entre o esperado e o real fornece um valor de R ^ 2 de 0,999994 .

Meu próximo passo para melhorar esta resposta é melhorar a estimativa quando o número de envelopes começar a ficar pequeno, ou seja, quando os envelopes não estiverem aproximadamente uniformemente distribuídos e quando o problema começar a ficar granulado.


Edit: Se isso é considerado digno de bitcoins, acabei de receber um endereço em 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Obrigado! (Foi aqui que o autor do desafio estava distribuindo prêmios.)

PhiNotPi
fonte
Enviou acidentalmente 20 mil satoshi para 805.479. Para referência, o valor deveria ser sua pontuação. Aprecie meu erro :)
LivingInformation
Você estará executando números com mais rodadas? Com base no que estou vendo, há bastante variação e 500 não são suficientes para obter uma mediana estável. Minha pontuação está muito próxima da sua, se eu correr apenas 500 rodadas, mas tudo depende de como os números aleatórios caem. Se eu usasse uma semente variável e fiz 500 corridas algumas vezes, provavelmente conseguiria uma pontuação mais alta.
Reto Koradi
@RetoKoradi Definitivamente vou fazer mais rodadas.
PhiNotPi