Kontekst:

Samotny miliarder stworzył teleturniej, aby przyciągnąć najlepszych i najzdolniejszych programistów na świecie. W poniedziałki o północy wybiera jedną osobę z grupy kandydatów na uczestnika tygodnia i zapewnia im grę. Jesteś szczęśliwym uczestnikiem tego tygodnia!

Gra w tym tygodniu:

Host zapewnia dostęp API do stosu 10 000 cyfrowych kopert. Te koperty są losowo sortowane i zawierają w nich wartość dolara od 1 do 10 000 USD (żadne dwie koperty nie zawierają tej samej wartości w dolarach).

Do dyspozycji masz 3 polecenia:

1. Czytaj (): Przeczytaj cyfrę dolara w kopercie u góry stosu.

2. Take (): dodaj cyfrę dolara z koperty do portfela teleturnieju i zdejmij kopertę ze stosu.

3. Pass (): Zdejmij kopertę na górze stosu.

Zasady:

1. Jeśli użyjesz Pass () na kopercie, pieniądze wewnątrz zostaną utracone na zawsze.

2. Jeśli użyjesz Take () na kopercie zawierającej $ X, od tego momentu nie możesz nigdy używać Take () na kopercie zawierającej <$ X. Take () na jednej z tych kopert doda 0 USD do Twojego portfela.

Napisz algorytm, który kończy grę z maksymalną kwotą pieniędzy.

Jeśli piszesz rozwiązanie w Pythonie, możesz użyć tego kontrolera do testowania algorytmów, dzięki uprzejmości @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Jeśli używasz kontrolera, nie masz dostępu do globałów, możesz użyć tylko 3 podanych komend API i zmiennych o zasięgu lokalnym. (Rozpad bety)

Uwagi: „Maksymalne” w tym przypadku oznacza medianę w portfelu po N> 50 uruchomieniach. Oczekuję, choć chciałbym, aby udowodniono, że się mylę, że wartość mediany dla danego algorytmu zbiegnie się, gdy N wzrośnie do nieskończoności. Spróbuj zamiast tego zmaksymalizować średnią, ale mam wrażenie, że średnia jest bardziej narażona na wyrzucenie przez małe N niż mediana.

Edycja: zmieniono liczbę kopert na 10k dla łatwiejszego przetwarzania i uściślono Take ().

Edycja 2: Warunek nagrody został usunięty w świetle tego postu na stronie meta.

Aktualne najlepsze wyniki:

PhiNotPi - 805 479 USD

Reto Koradi - 803 960 USD

Dennis - 76 272 USD (zmienione)

Alex L. - 714,962 USD (zmieniony)

CJam, 87 143 $ 700,424 $ 720 327 727,580 $ 76 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

Ten program symuluje całą grę wiele razy i oblicza medianę.

Jak biegać

Oceniłem swoje zgłoszenie, wykonując 100 001 testów:

$ 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

Podejście

Dla każdej koperty wykonujemy następujące czynności:

• Oszacuj kwotę pieniędzy, którą nieuchronnie stracisz, biorąc kopertę.

  Jeśli R jest zawartością, a M jest maksymalną, która została podjęta, kwotę można oszacować jako R (R-1) / 2 - M (M + 1) / 2 , co daje pieniądze wszystkim kopertom z zawartością X w przedział (M, R) zawiera.

  Gdyby nie przekazano jeszcze kopert, ocena byłaby idealna.

• Oblicz kwotę pieniędzy, która nieuchronnie zostanie utracona przez przekazanie koperty.

  To po prostu pieniądze, które zawiera koperta.

• Sprawdź, czy iloraz obu jest mniejszy niż 110 + 0,016E , gdzie E jest liczbą pozostałych kopert (nie licząc kopert, których nie można już zabrać).

  Jeśli tak, weź. W przeciwnym razie podaj.

Python, 680 646 714 962 USD

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

Coraz większe kwoty w krokach wielkości od 125 do 190 USD. Biegłem z N = 10 000 i otrzymałem medianę 714962 $. Te rozmiary kroków pochodzą z prób i błędów i na pewno nie są optymalne.

Pełny kod, w tym zmodyfikowana wersja kontrolera @ Maltysen, który drukuje wykres słupkowy podczas działania:

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)

Adres BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Wow dostarczony OP! Dzięki @LivingInformation!

C ++, 803,960 USD

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

Podany wynik to mediana z 10 001 gier.

C ++, ~ 815 000 USD

Oparty na rozwiązaniu Reto Koradi, ale przełącza się na bardziej wyrafinowany algorytm, gdy pozostało 100 (prawidłowych) kopert, tasując losowe permutacje i obliczając największa rosnącą ich podsekwencję. Porównuje wyniki pobrania i nie zabrania koperty i zachłannie wybierze najlepszy wybór.

#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 USD

To pochodzi z próby 2501 rund. Nadal pracuję nad optymalizacją. Napisałem dwie klasy, opakowanie i odtwarzacz. Opakowanie tworzy instancję odtwarzacza z liczbą kopert (zawsze 10000 w rzeczywistości), a następnie wywołuje metodę takeQz wartością najwyższej koperty. Następnie gracz powraca, truejeśli go weźmie, falsejeśli go spasuje.

Gracz

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

Obwoluta

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

Bardziej szczegółowe wyjaśnienie pojawi się wkrótce po zakończeniu optymalizacji.

Podstawową ideą jest możliwość oszacowania nagrody za grę z danego zestawu kopert. Jeśli bieżący zestaw kopert wynosi {2,4,5,7,8,9}, a górna koperta to 5, wówczas istnieją dwie możliwości:

• Weź 5 i zagraj w grę z {7,8,9}
• Podaj 5 i zagraj w {2,4,7,8,9}

Jeśli obliczymy oczekiwaną nagrodę w wysokości {7,8,9} i porównamy ją z oczekiwaną nagrodą w wysokości {2,4,7,8,9}, będziemy mogli stwierdzić, czy warto wziąć 5.

Teraz pytanie brzmi, biorąc pod uwagę zestaw kopert, takich jak {2,4,7,8,9}, jaka jest oczekiwana wartość? Odkryłem, że oczekiwana wartość wydaje się proporcjonalna do całkowitej kwoty pieniędzy w zestawie, ale odwrotnie proporcjonalna do pierwiastka kwadratowego z liczby kopert, na które pieniądze są podzielone. Wynika to z „perfekcyjnego” grania w kilka małych gier, w których wszystkie koperty mają prawie identyczną wartość.

Kolejnym problemem jest określenie „ efektywnej liczby kopert”. We wszystkich przypadkach liczba kopert jest dokładnie znana dzięki śledzeniu tego, co widziałeś i zrobiłeś. Coś takiego jak {234,235,236} to zdecydowanie trzy koperty, {231,232,233,234,235} to zdecydowanie 5, ale {1, 224 233 23636} naprawdę powinno się liczyć jako 3, a nie 5 kopert, ponieważ 1 i 2 są prawie bezwartościowe, i nigdy NIE PASUJESZ na 234, więc możesz później odebrać 1 lub 2. Miałem pomysł, aby użyć entropii Shannona do określenia efektywnej liczby kopert.

Swoje obliczenia skierowałem na sytuacje, w których wartości obwiedni rozkładają się równomiernie w pewnym przedziale czasowym, co dzieje się podczas gry. Jeśli wezmę {2,4,7,8,9} i potraktuję to jako rozkład prawdopodobieństwa, jego entropia wynosi 1,50242. Następnie robię, exp()aby uzyskać 4,49254 jako efektywną liczbę kopert.

Szacunkowa nagroda z {2,4,7,8,9} to 30 * 4.4925^-0.5 * 4/3 = 18.87

Dokładna liczba to 18.1167.

To nie jest dokładne oszacowanie, ale tak naprawdę jestem naprawdę dumny z tego, jak dobrze to pasuje do danych, gdy koperty są równomiernie rozmieszczone w odstępie czasu. Nie jestem pewien poprawnego mnożnika (na razie używam 4/3), ale oto tabela danych z wyłączeniem mnożnika.

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

Regresja liniowa między oczekiwaną a rzeczywistą daje wartość R ^ 2 wynoszącą 0,999994 .

Moim następnym krokiem do poprawy tej odpowiedzi jest poprawienie oszacowania, kiedy liczba kopert zaczyna się zmniejszać, czyli wtedy, gdy koperty nie są w przybliżeniu równomiernie rozmieszczone i kiedy problem zaczyna się granulować.

Edycja: Jeśli jest to warte bitcoinów, właśnie dostałem adres na 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Dzięki! (To było tutaj, od kiedy autor konkursu rozdawał nagrody.)