Контекст:

Миллиардер-затворник создал игровое шоу для привлечения лучших и самых ярких программистов мира. По понедельникам в полночь он выбирает одного человека из числа претендентов на участие в неделе и предоставляет им игру. Вы счастливчик на этой неделе!

Игра на этой неделе:

Хост предоставляет API-доступ к стопке из 10 000 цифровых конвертов. Эти конверты сортируются случайным образом и содержат внутри себя долларовую стоимость от 1 до 10000 долларов (никакие два конверта не содержат одинаковую долларовую стоимость).

В вашем распоряжении 3 команды:

1. Чтение (): чтение цифры доллара в конверте в верхней части стопки.

2. Возьмите (): добавьте долларовую цифру в конверте в свой кошелек для игрового шоу и вытяните конверт из стопки.

3. Pass (): выскочить из конверта на вершине стека.

Правила:

1. Если вы используете Pass () на конверте, деньги внутри будут потеряны навсегда.

2. Если вы используете Take () на конверте, содержащем $ X, с этого момента вы никогда не сможете использовать Take () на конверте, содержащем <$ X. Take () на одном из этих конвертов добавит $ 0 к вашему кошельку.

Напишите алгоритм, который заканчивает игру с максимальной суммой денег.

Если вы пишете решение на Python, не стесняйтесь использовать этот контроллер для проверки алгоритмов, предоставлено @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Если вы используете контроллер, вы не сможете получить доступ к глобальным переменным, вы можете использовать только 3 предоставленные команды API и локальные переменные области действия. (@Beta Decay)

Примечания: «Максимальный» в этом случае означает медиану в вашем кошельке после N> 50 пробежек. Я ожидаю, хотя я бы хотел оказаться ошибочным, что медианное значение для данного алгоритма будет сходиться при увеличении N до бесконечности. Не стесняйтесь пытаться максимизировать среднее значение вместо этого, но у меня есть ощущение, что среднее значение, скорее всего, будет отброшено небольшим N, чем медиана.

Изменить: изменил количество конвертов до 10 КБ для упрощения обработки и сделал Take () более явным.

Изменить 2: условие приза было удалено, в свете этого поста на мета.

Текущие рекорды:

PhiNotPi - $ 805 479

Рето Коради - $ 803 960

Деннис - 770 272 долл. США (пересмотрено)

Алекс Л. - 714 962 $ (пересмотренный)

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

Эта программа имитирует всю игру несколько раз и вычисляет медиану.

Как бегать

Я набрал 100001 тестов:

$ 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

Подходить

Для каждого конверта мы делаем следующее:

• Оцените сумму денег, которая неизбежно будет потеряна, взяв конверт.

  Если R - это содержание, а M - это максимум, который был взят, сумма может быть оценена как R (R-1) / 2 - M (M + 1) / 2 , что дает деньги всем конвертам с содержанием X в интервал (M, R) содержит.

  Если конверты еще не были переданы, оценка будет идеальной.

• Рассчитайте сумму денег, которая неизбежно будет потеряна, передавая конверт.

  Это просто деньги, которые содержит конверт.

• Проверьте, не является ли отношение обоих менее 110 + 0,016E , где E - количество оставшихся конвертов (не считая конверты, которые больше не могут быть взяты).

  Если так, бери. В противном случае, пройти.

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

Принимает все большие и большие суммы в размере от 125 до 190 долларов. Побежал с N = 10000 и получил медиану $ 714962. Эти размеры шагов получены методом проб и ошибок и, конечно, не являются оптимальными.

Полный код, включая модифицированную версию контроллера @ Maltysen, которая печатает гистограмму во время работы:

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)

Адрес BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Ух ОП доставлено! Спасибо @LivingInformation!

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

Отмеченный результат - медиана из 10 001 игр.

C ++, ~ 815 000 долларов

Основывается на решении Рето Коради, но переключается на более сложный алгоритм, когда остается 100 (действительных) конвертов, перемешивая случайные перестановки и вычисляя наиболее тяжелую возрастающую их подпоследовательность. Он будет сравнивать результаты взятия и не взятия конверта и жадно выберет лучший выбор.

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

Ява, $ 806 899

Это из испытания 2501 раундов. Я все еще работаю над оптимизацией. Я написал два класса, обертку и плеер. Оболочка создает экземпляр игрока с количеством конвертов (для реальных вещей всегда 10000), а затем вызывает метод takeQсо значением верхнего конверта. Игрок затем возвращается, trueесли они его принимают, falseесли они его пропускают.

игрок

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

обертка

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

Более подробное объяснение скоро появится, когда я закончу оптимизацию.

Основная идея заключается в том, чтобы иметь возможность оценить вознаграждение за игру в заданном наборе конвертов. Если текущий набор конвертов {2,4,5,7,8,9}, а верхний конверт - 5, то есть две возможности:

• Возьми 5 и играй в игру с {7,8,9}
• Пройдите 5 и играйте в игру {2,4,7,8,9}

Если мы вычислим ожидаемое вознаграждение {7,8,9} и сравним его с ожидаемым вознаграждением {2,4,7,8,9}, мы сможем определить, стоит ли брать 5.

Теперь вопрос, учитывая набор конвертов типа {2,4,7,8,9}, какова ожидаемая стоимость? Я обнаружил, что ожидаемое значение кажется пропорциональным общей сумме денег в наборе, но обратно пропорционально квадратному корню из числа конвертов, на которые делятся деньги. Это произошло из-за «идеальной» игры в несколько небольших игр, в которых все конверты имеют почти одинаковую ценность.

Следующая проблема заключается в том, как определить « эффективное количество конвертов». Во всех случаях количество конвертов точно известно, отслеживая то, что вы видели и делали. Что-то вроде {234,235,236} определенно состоит из трех конвертов, {231,232,233,234,235} определенно равно 5, но {1,2,234,235,236} должно действительно считаться как 3, а не 5 конвертов, потому что 1 и 2 почти бесполезны, и вы никогда не пропустите на 234, поэтому позже вы могли бы взять 1 или 2. У меня была идея использовать энтропию Шеннона для определения эффективного числа конвертов.

Я нацелил свои расчеты на ситуации, когда значения конверта равномерно распределены по некоторому интервалу, что и происходит во время игры. Если я беру {2,4,7,8,9} и рассматриваю это как распределение вероятностей, его энтропия равна 1,50242. Затем я exp()получаю 4.49254 как эффективное количество конвертов.

Расчетное вознаграждение от {2,4,7,8,9} составляет 30 * 4.4925^-0.5 * 4/3 = 18.87

Точное число есть 18.1167.

Это не точная оценка, но я действительно горжусь тем, насколько хорошо это подходит для данных, когда конверты равномерно распределены по интервалу. Я не уверен в правильном множителе (сейчас я использую 4/3), но вот таблица данных, исключая множитель.

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

Линейная регрессия между ожидаемым и фактическим дает значение R ^ 2 0,999994 .

Мой следующий шаг по улучшению этого ответа - улучшить оценку, когда количество конвертов начинает уменьшаться, то есть когда конверты распределены примерно неравномерно и когда проблема начинает становиться гранулированной.

Изменить: Если это считается достойным биткойнов, я только что получил адрес по адресу 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Благодарность! (Это было здесь с того момента, когда автор конкурса раздавал призы.)