Take It or Leave It: teleturniej na komputery

28

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)

LivingInformation
źródło
Zaimplementowałem w taki sposób, że po prostu zwraca False. Ponieważ możesz to przeczytać, nie ma sensu nie
udawać
4
Jeśli ktoś chce go użyć, oto kontroler, którego używałem
Maltysen
8
PS Ładne pytanie i witamy w Programowaniu Puzzle i Code Golf :)
trichoplax
3
@Maltysen Umieściłem twój kontroler w PO, dzięki za wkład!
LivingInformation
1
Nie mogłem znaleźć wyraźnej reguły dotyczącej nagród bitcoinowych, ale istnieje pewna meta dyskusja na temat nagród w świecie rzeczywistym, do których ludzie mogą się przyczynić.
trichoplax

Odpowiedzi:

9

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.

Dennis
źródło
5
Ponieważ używanie języka golfowego pomaga w jakikolwiek sposób. ; P +1 dla algo.
Maltysen
2
Nie mogę replikować wyników za pomocą klonu Python: gist.github.com/orlp/f9b949d60c766430fe9c . Zdobędziesz około 50 000 $. To jest rząd wielkości.
orlp
1
@LivingInformation Wersja próbna i błąd. Obecnie szukam użycia dokładnej kwoty zamiast szacunków, ale wynikowy kod jest bardzo wolny.
Dennis
2
Ta odpowiedź wymaga więcej głosów pozytywnych niż moja! Jest bardziej sprytny, zdobywa więcej punktów, a nawet gra w golfa!
Alex L
1
@LivingInformation To jest mój adres: 17uLHRfdD5JZ2QjSqPGQ1B12LoX4CgLGuV
Dennis
7

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!

Alex L.
źródło
1
Kontroler należy do Maltysena, nie do mnie.
orlp
2
Zatwardziały. Właśnie skonfigurowałem kontroler i otrzymałem bardzo podobne liczby dla twojego rozwiązania. Ściśle mówiąc, myślę, że musisz zachować wartość max_takenwłasnego kodu, ponieważ nie jest on częścią oficjalnego interfejsu API gry. Ale to trywialne.
Reto Koradi
1
Tak, max_taken znajduje się w kontrolerze @ Maltysen. Jeśli jest to przydatne, mogę opublikować całe rozwiązanie (kontroler + algorytm) w jednym bloku.
Alex L
To naprawdę nie jest wielka sprawa. Ale myślę, że najczystsze podejście byłoby użyć tylko read(), take()a pass()metody w kodzie dydaktyczna, ponieważ są to „3 komend do Państwa dyspozycji” na podstawie definicji zawartej w pytaniu.
Reto Koradi,
@ Reto Jestem gotów zrewidować pytanie tak, aby komendy były najbardziej sensowne. Przeczytaj, weź i podaj wszystkie 4 znaki i czułam się dobrze, ale jestem otwarta na sugestie (na przykład rozważałam zmianę „pass” na „odejść”, ponieważ zatytułowałem post „weź lub zostaw” „).
LivingInformation
5

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.

Reto Koradi
źródło
Zgadnij i sprawdź, rozumiem? A może użyłeś jakiegoś fuzzera wejściowego dla stałych?
LivingInformation
Uruchomiłem algorytm optymalizacyjny, aby ustalić stałe.
Reto Koradi,
Czy uważasz, że obliczenia dynamiczne w każdym punkcie byłyby bardziej skuteczne, czy też sądzisz, że zbliżają się one do maksymalnej możliwej do uzyskania wartości?
LivingInformation
Nie mam powodu sądzić, że jest to idealna strategia. Mam nadzieję, że jest to maksimum dla funkcji liniowej z tymi parametrami. Próbowałem dopuścić różne rodzaje nieliniowych terminów, ale jak dotąd nie znalazłem niczego znacznie lepszego.
Reto Koradi
1
Mogę potwierdzić, że symulowanie tego daje wynik nieco ponad 800 000 $.
orlp
3

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;
}
orlp
źródło
Ciekawy. Przyszło mi do głowy, że można poprawić, patrząc na wartości pozostawione dla kilku ostatnich kopert. Myślę, że grałeś w punkcie odcięcia, w którym zmieniasz strategie? Czy robi się zbyt wolno, jeśli zmienisz wcześniej? A może wyniki są coraz gorsze?
Reto Koradi
@RetoKoradi Grałem z punktem odcięcia, a wcześniejsze odcięcia były zbyt wolne i gorsze. Nie zbyt zaskakujące szczerze, przy 100 kopert jesteśmy już próbkowania zaledwie 1000 permutacje z możliwych 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
orlp
3

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

PhiNotPi
źródło
Przypadkowo wysłałem ci 20k satoshi ponad 805,479. Dla porównania, kwota miała być twoim wynikiem. Ciesz się moim błędem :)
LivingInformation
Czy będziesz prowadził liczby z większą liczbą rund? Na podstawie tego, co widzę, istnieje dość duża zmienność, a 500 nie wystarczy, aby uzyskać stabilną medianę. Mój wynik jest bardzo bliski twojemu, jeśli przeprowadzę tylko 500 rund, ale wszystko zależy od tego, jak spadają losowe liczby. Gdybym użył zmiennego materiału siewnego i wykonał 500 razy kilka razy, prawdopodobnie mógłbym uzyskać wyższy wynik.
Reto Koradi,
@RetoKoradi Zdecydowanie zrobię więcej rund.
PhiNotPi