Le contexte:

Un milliardaire reclus a créé un jeu télévisé pour attirer les meilleurs programmeurs du monde. Le lundi à minuit, il choisit une personne parmi un groupe de candidats pour être le candidat de la semaine et leur propose un jeu. Vous êtes l'heureux candidat de cette semaine!

Jeu de cette semaine:

L'hôte vous offre un accès API à une pile de 10 000 enveloppes numériques. Ces enveloppes sont triées au hasard et contiennent en leur sein une valeur en dollars, entre 1 $ et 10 000 $ (il n’existe pas deux enveloppes ayant la même valeur en dollars).

Vous avez 3 commandes à votre disposition:

1. Lire (): lire le chiffre en dollars dans l'enveloppe en haut de la pile.

2. Take (): Ajoutez le chiffre en dollars dans l'enveloppe à votre portefeuille de jeu télévisé et sortez l'enveloppe de la pile.

3. Pass (): Retirez l'enveloppe sur le dessus de la pile.

Les règles:

1. Si vous utilisez Pass () sur une enveloppe, l'argent à l'intérieur est perdu pour toujours.

2. Si vous utilisez Take () sur une enveloppe contenant $ X, à partir de ce moment, vous ne pourrez jamais utiliser Take () sur une enveloppe contenant <$ X. Prenez () sur l'une de ces enveloppes ajoutera 0 $ à votre portefeuille.

Écrivez un algorithme qui termine le jeu avec le montant maximal d'argent.

Si vous écrivez une solution en Python, n'hésitez pas à utiliser ce contrôleur pour tester des algorithmes, gracieuseté de @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Si vous utilisez le contrôleur, vous ne pouvez pas accéder aux globaux, vous ne pouvez utiliser que les 3 commandes API fournies et les variables de portée locales. (@Beta Decay)

Remarques: "Maximal" dans ce cas signifie la valeur médiane de votre portefeuille après N> 50 exécutions. Je m'attends, bien que j'aimerais qu'on me prouve à tort, que la valeur médiane d'un algorithme donné convergera lorsque N augmentera à l'infini. N'hésitez pas à essayer de maximiser la moyenne à la place, mais j'ai le sentiment que la moyenne est plus susceptible d'être rejetée par un petit N que la médiane.

Modifier: a changé le nombre d'enveloppes à 10k pour un traitement plus facile et a rendu Take () plus explicite.

Edit 2: La condition de prix a été supprimée, à la lumière de ce post sur meta.

Meilleurs scores actuels:

PhiNotPi - 805 479 $

Reto Koradi - 803 960 $

Dennis - 770 272 $ (révisé)

Alex L. - 714 962 $ (révisé)

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

Ce programme simule le jeu entier plusieurs fois et calcule la médiane.

Comment courir

J'ai marqué ma soumission en effectuant 100 001 tests:

$ 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

Approche

Pour chaque enveloppe, nous procédons comme suit:

• Estimez le montant d'argent qui sera inévitablement perdu en prenant l'enveloppe.

  Si R est le contenu et M est le maximum qui a été pris, le montant peut être estimé comme R (R-1) / 2 - M (M + 1) / 2 , ce qui donne à l'argent toutes les enveloppes avec le contenu X dans le l'intervalle (M, R) contient.

  Si aucune enveloppe n'avait encore été passée, l'estimation serait parfaite.

• Calculez le montant d'argent qui sera inévitablement perdu en passant l'enveloppe.

  C'est simplement l'argent que contient l'enveloppe.

• Vérifiez si le quotient des deux est inférieur à 110 + 0,016E , où E est le nombre d'enveloppes restantes (sans compter les enveloppes qui ne peuvent plus être prises).

  Si oui, prenez. Sinon, passez.

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

Prend des quantités de plus en plus grandes par étapes de taille entre 125 $ et 190 $. A couru avec N = 10 000 et a obtenu une médiane de 714962 $. Ces tailles de pas proviennent d'essais et d'erreurs et ne sont certainement pas optimales.

Le code complet, y compris une version modifiée du contrôleur de @ Maltysen qui imprime un graphique à barres pendant son exécution:

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)

Adresse BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Wow OP livré! Merci @LivingInformation!

C ++, 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();
    }
}

Le résultat signalé est la médiane de 10 001 matchs.

C ++, ~ 815 000 $

Basé sur la solution de Reto Koradi, mais passe à un algorithme plus sophistiqué une fois qu'il reste 100 enveloppes (valides), mélangeant les permutations aléatoires et calculant la sous-séquence croissante la plus lourde d'entre elles. Il comparera les résultats de la prise et de la non prise de l'enveloppe, et sélectionnera avidement le meilleur choix.

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

Java, 806 899 $

Il s'agit d'un essai de 2501 tours. Je travaille toujours sur son optimisation. J'ai écrit deux classes, un wrapper et un joueur. L'encapsuleur instancie le lecteur avec le nombre d'enveloppes (toujours 10000 pour la vraie chose), puis appelle la méthode takeQavec la valeur de l'enveloppe supérieure. Le joueur revient ensuite trues'il le prend, falses'il le passe.

Joueur

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

Wrapper

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

Une explication plus détaillée arrivera bientôt, une fois les optimisations terminées.

L'idée centrale est de pouvoir estimer la récompense d'un jeu à partir d'un ensemble d'enveloppes donné. Si le jeu d'enveloppes actuel est {2,4,5,7,8,9} et que l'enveloppe supérieure est le 5, il y a deux possibilités:

• Prenez les 5 et jouez avec {7,8,9}
• Passez les 5 et jouez une partie de {2,4,7,8,9}

Si nous calculons la récompense attendue de {7,8,9} et la comparons à la récompense attendue de {2,4,7,8,9}, nous serons en mesure de dire si prendre le 5 en vaut la peine.

Maintenant, la question est, étant donné un ensemble d'enveloppes comme {2,4,7,8,9} quelle est la valeur attendue? J'ai trouvé que la valeur attendue semble être proportionnelle au montant total de l'argent dans l'ensemble, mais inversement proportionnelle à la racine carrée du nombre d'enveloppes dans lesquelles l'argent est divisé. Cela venait de "parfaitement" jouer à plusieurs petits jeux dans lesquels toutes les enveloppes ont une valeur presque identique.

Le problème suivant est de savoir comment déterminer le " nombre effectif d'enveloppes». Dans tous les cas, le nombre d'enveloppes est connu exactement en gardant une trace de ce que vous avez vu et fait. Quelque chose comme {234,235,236} est certainement trois enveloppes, {231,232,233,234,235} est certainement 5, mais {1,2,234,235,236} devrait vraiment compter comme 3 et non 5 enveloppes car les 1 et 2 sont presque sans valeur, et vous ne PASSERIEZ JAMAIS sur un 234 donc vous pourriez plus tard prendre un 1 ou 2. J'ai eu l'idée d'utiliser l'entropie de Shannon pour déterminer le nombre effectif d'enveloppes.

J'ai ciblé mes calculs sur des situations où les valeurs de l'enveloppe sont uniformément réparties sur un certain intervalle, ce qui se produit pendant le jeu. Si je prends {2,4,7,8,9} et que je la traite comme une distribution de probabilité, son entropie est de 1,50242. Alors je faisexp() pour obtenir 4,49254 comme nombre effectif d'enveloppes.

La récompense estimée de {2,4,7,8,9} est 30 * 4.4925^-0.5 * 4/3 = 18.87

Le nombre exact est 18.1167 .

Ce n'est pas une estimation exacte, mais je suis vraiment très fier de la façon dont cela correspond aux données lorsque les enveloppes sont réparties uniformément sur un intervalle. Je ne suis pas sûr du bon multiplicateur (j'utilise 4/3 pour l'instant) mais voici un tableau de données excluant le multiplicateur.

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

La régression linéaire entre les valeurs attendues et réelles donne une valeur R ^ 2 de 0,999994 .

Ma prochaine étape pour améliorer cette réponse consiste à améliorer l'estimation lorsque le nombre d'enveloppes commence à devenir petit, c'est-à-dire lorsque les enveloppes ne sont pas réparties de manière approximativement uniforme et lorsque le problème commence à devenir granuleux.

Edit: Si cela est jugé digne des bitcoins, je viens de recevoir une adresse à 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Merci! (C'était ici quand l'auteur du défi distribuait des prix.)