Это вторая из серии головоломок, которые я буду публиковать каждый понедельник в полночь по тихоокеанскому времени. Первая головоломка находится здесь .

Контекст:

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

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

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

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

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

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

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

4. Oracle (M): возвращает среднее значение следующих M конвертов в стеке, не считая того, которое вы можете в данный момент прочитать ().

Правила:

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

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

3. Если вы используете Oracle (M) на очереди T, конверты от T + 1 до T + M будут возвращены. Oracle () отключен до поворота T + M.

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

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

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

Примечание 2: поскольку все решения предыдущей части этой головоломки верны здесь, их повторное размещение не имеет большого значения. Только алгоритмические улучшения предыдущих головоломок будут рассмотрены для части II.

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

Groovy $ 713337 $ 817829 $ 818227

Загрузочный код:

class Instance {
    List values = new ArrayList(1..10000); {
        Collections.shuffle(values)
    }
    int i = 0
    int value = 0
    int max = 0
    int nextOracle = 0

    def pass() {
        if (i >= 10000)
            throw new NoSuchElementException()
        i++
    }

    def take() {
        if (i >= 10000)
            throw new NoSuchElementException()
        int v = values[i]
        if (v > max) {
            max = v
            value += v
        }
        i++
    }

    double oracle(int m) {
        if (m <= 0 || i < nextOracle || i + m >= 10000)
            throw new NoSuchElementException()

        nextOracle = i + m
        values.subList(i + 1, i + m + 1).stream().reduce { l, r -> r+l }.get() / m
    }

    int read() {
        if (i >= 10000)
            throw new NoSuchElementException()
        values[i]
    }
}

Алгоритм

double square(double v) { v * v }
final double factor = Math.pow(1.5, 1.1)
int attempts = 5000
(1..attempts).stream().parallel().mapToLong {
    def puzzle = new Instance()

    int[] memory = 1..10000 // We will remember every envelope
    int memStart = 0

    while (memStart < 10000 - 3) {
        int value = puzzle.read()
        int i = Arrays.binarySearch(memory, memStart, 10000, value) - memStart
        if (i < 0) { // We can't use the money
            puzzle.pass()
            continue
        }
        if (i == 0) { // Of course we take the lowest
            puzzle.take()
            memStart++
            continue
        }
        int remaining = Arrays.stream(memory, i + 1 + memStart, 10000).sum() // Money we could win if taken
        int losing = Arrays.stream(memory, memStart, memStart + i).sum() // Money we cna't win if taken
        if (value > losing) { // If we pass, we lose money automatically
            puzzle.take()
            memStart += i + 1
        } else if ((losing - value * 16 / 7) * square(Math.log(i)) > remaining / factor) {
            System.arraycopy(memory, memStart, memory, ++memStart, i)
            puzzle.pass()
        } else {
            puzzle.take()
            memStart += i + 1
        }
    }

    // It's broken down to last three elements
    List values = Arrays.copyOfRange(memory, 10000 - 3, 10000)
    while (!values.contains(puzzle.read())) // Skip values we can't use
        puzzle.pass()
    int value1 = puzzle.read()
    int value2 = puzzle.oracle(1)
    if (value1 == values.max() && (
            values.contains(value2)
            ? (value1 * 2 < values.sum() && values.min() == value2)
            : (value1 < values.min() / 2 + (values - [value1]).max())
            )) {
        puzzle.pass()
    }

    // Finish it
    while (puzzle.i < puzzle.values.size()) {
        puzzle.take()
    }

    puzzle.value as Long
}.sum() / attempts // Sum runs and average

Я сравниваю оставшиеся значения с возможными значениями. Этот скрипт не быстрый (занимает 1 минуту на 1000x симуляций) ... но он будет выполнять симуляции одновременно.

Я понятия не имею, почему мой алгоритм работает, но это было просто методом проб и ошибок: объединение математических операций и манипулирование константами. Я запустил его в 5000 раз для текущей оценки, чтобы уменьшить колебания оценки (это +/- $ 4000 в зависимости от количества итераций).

Даже без оракула в конце, он все равно должен (едва) побить решение @ orlp для предыдущей головоломки.

C # - $ 803.603 сейчас -> $ 804,760 (с оракулом)

Загрузочный код

public static class ShuffleExtension
{
    private static Random rng = new Random();  

    public static void Shuffle<T>(this IList<T> list)  
    {  
        int n = list.Count;
        while (n > 1) {  
            n--;  
            int k = rng.Next(n + 1);  
            T value = list[k];  
            list[k] = list[n];  
            list[n] = value;  
        }  
    }
}

public class Puzzle
{
    public List<int> Values = new List<int>(10000);

    public Puzzle()
    {
        for ( int i = 1; i <= 10000; i++ )
        {
            Values.Add(i);
        }
        Values.Shuffle();
    }

    public int i = 0;
    public int value = 0;
    public int max = 0;
    public int nextOracle = 0;

    public void Pass() {
        if ( i >= Values.Count )
            throw new IndexOutOfRangeException();
        i++;
    }

    public void Take() {
        if (i >= Values.Count )
            throw new IndexOutOfRangeException();
        int v = Values[i];
        if (v > max) {
            max = v;
            value += v;
        }
        i++;
    }

    public double oracle(int m) {
    if (m <= 0) { 
        throw new IndexOutOfRangeException();
    }
    if ( i < nextOracle ) {
        throw new IndexOutOfRangeException();
    }
    if ( i + 1 + m > Values.Count ) {
        throw new IndexOutOfRangeException();
    }

    nextOracle = i + m;
    var oracleValues = new List<int>();
    for ( int l = 0; l < m; l++ )
    {
        oracleValues.Add(Values[i + 1 + l]);
    }
    return oracleValues.Average (v => v);
}

    public int Read() {
        if (i >= Values.Count )
            throw new IndexOutOfRangeException();
        return Values[i];
    }
}

Код игры:

    void Main()
{
    var m = 0;
    for ( int l = 0; l < 1000; l++ )
    {
        var game = new Puzzle();
        var maxVal = 0;
        var lastOracle = 0;
        var lastOracleValue = 0.0m;
        var oracleValueForIOf = 0;

        for ( int i = 0; i < 10000; i++ )
        {
            var val = game.Read();
            var oracleStep = 1;
            var canUseOracle = (i - lastOracle >= oracleStep) && i + oracleStep + 1 <= 10000;
            if ( canUseOracle )
            {
                var oracle = game.oracle(oracleStep);
                lastOracle = i;
                lastOracleValue = (decimal)oracle;
                oracleValueForIOf = i + 1;
            }
            if ( TakeTheMoney(val, maxVal, oracleValueForIOf, lastOracleValue, i) )
            {
                maxVal = val;
                game.Take();
            }
            else
            {
                game.Pass();
            }
        }
        m += game.value;
    }
    ((int)(m / 1000)).Dump();
}

private bool TakeTheMoney(int val, int maxVal, int oracleValueForIOf, decimal lastOracleValue, int i)
{
    if ( val > maxVal )
    {
        if ( oracleValueForIOf != i + 1
            &&
            (val < 466.7m + (0.9352m * maxVal) + (0.0275m * i))
            )
        {
            return true;
        }

        if (oracleValueForIOf == i + 1)
        {
            if ( val < 466.7m + (0.9352m * maxVal) + (0.0275m * i) )
            {
                return true;
            }
            if ( lastOracleValue > 466.7m + (0.9352m * val) + (0.0275m * i + 1) )
            {
                if ( val < 466.7m + (0.9352m * maxVal) + (0.0275m * i + 1) )
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Кредит принадлежит Рето Коради ( /codegolf//a/54181/30910 )

Изменить: Базовое использование Oracle реализовано. Если следующий оракул превышает пороговое значение для использования, разверните текущий конверт до индекса Oracle Index. Это не часто, но это улучшение ;-)

Python - $ 74112

Возьмите, только если текущее значение ниже следующего значения (т.е. вы можете взять оба).

def algo():
  try:
    o=oracle(1)
  except ValueError:
    take()
  r=read()
  if r>o:
    passe()
  else:
    take()

Python - (все еще вычисляет среднее)

Этот ответ занимает ОЧЕНЬ ДОЛГО в расчете. Это достигает около 670.000 $ . Я помню каждый конверт, который видел. Каждый раз, когда мне нужно принять решение, я генерирую два списка оставшихся конвертов, которые я мог бы потенциально добавить в свой кошелек, если я возьму текущий конверт или оставлю его соответственно.

Я не оптимизировал код.

def algo_2():
  global max_taken, past
  weight=0.92 #Empirically chosen.
  r=read()
  if len(past)==0:
    past.append(r)
    passe()
    return
  if r<max_taken:
    past.append(r)
    take() #the same as passe
    return
  coming=[x for x in range(1,10001) if x not in past and x>max_taken and x!=r ]
  comingIfTake=[x for x in range(1,10001) if x not in past and x>r ]
  if sum(coming)*weight<=sum(comingIfTake)+r:
    past.append(r)
    take()
  else:
    past.append(r)
    passe()

И init_game начинается так:

def init_game():
    global stack, wallet, max_taken, oracle_turns, past
    past=[]

C # - 780,176 $

Проверьте, находится ли следующее значение в пределах 5% от всех оставшихся значений. Будьте более расслаблены, когда мы доберемся до конца.

public class Taker
{
    private List<int> remaining;
    private Game game;

    public Taker(Game game)
    {
        this.game = game;
        remaining = Enumerable.Range(1, game.Size + 100).ToList();
    }

    int score = 0;

    public int PlayGame()
    {
        for (int i = 0; i < game.Size; i++)
        {
            if (game.Read() < game.Max ||
                game.Read() > selectThreshold() ||
                doOracle()
                )
            {
                remaining.Remove(game.Read());
                game.Pass();
                continue;
            }
            remaining = remaining.SkipWhile(j => j < game.Read()).ToList();
            score += game.Take();
        }
        return score;
    }

    private bool doOracle()
    {
        return game.Oracle(1) < game.Read() &&
            game.Oracle(1) > game.Max;
    }

    private int selectThreshold()
    {
        int selector = (int)(remaining.Count * 0.05);
        return remaining.ElementAt(selector);
    }
}

И мой класс игры, очень уродливый, класс игры даже не проверяет, разрешен ли оракул, но, поскольку я использую только Oracle (1), это не должно быть проблемой.

public class Game
{
    private int[] list;
    private int position = 0;
    private int max = 0;
    public int Max { get { return max; } }
    public int Size { get { return list.Length; } }

    public Game(int[] list)
    {
        this.list = list;
    }

    public int Read()
    {
        return list[position];
    }

    public int Take()
    {
        if (list[position] < max)
        {
            position++;
            return 0;
        }
        max = list[position];
        return list[position++];
    }

    public void Pass()
    {
        position++;
    }

    public int Oracle(int M)
    {
        int next = position + 1;
        M = Math.Max(0, Math.Min(M, list.Length - next));
        return new ArraySegment<int>(list, next, M).Sum();
    }
}

Ява, $ 804,991

Оценка от 1001 раундов. Вероятно, слишком близко, чтобы звонить между этим ответом и ответом Стефана Шинкеля .

Это основано на моем ответе в предыдущей задаче, так как он использует те же вычисления на основе энтропии для оценки выплат. Основное отличие состоит в том, что теперь он просто берет конверты попарно (1 и 2, затем 3 и 4 и т. Д.) И просматривает возможные комбинации «бери-бери», «бери-пас», «проходи-бери» и т. Д. Он также вычисляет точная оценка, когда количество действительных конвертов действительно мало.

«Обертка», которую я написал, на самом деле не является настоящей оберткой, она просто дает конверты в парах, а не вызывает Oracle(1)функцию каждый второй раунд.

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

игрок

import java.lang.Math;
public class Player2
{
    public int[] V;

    public Player2(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, int y)
    {
        //System.out.println("Look: " + x + " " + y);
        boolean [] move = new boolean[]{false,false};
        double max = 0;
        double val = 0;
        int[] nextV = V;

        ////System.out.println("look " + x);
        int i = find(V,x);
        if(i >= 0)  //if found
        {
            //try taking first envelope
            int[] newVt = takeSlice(V,i);
            //System.out.println("  T: " + ats(newVt));
            int j = find(newVt,y);
            if(j >= 0)
            {
                //try taking first and second
                int[] newVtt = takeSlice(newVt,j);
                val = x + y + calcVal(newVtt);
                //System.out.println("  TT: " + ats(newVtt) + " " + val);
                if(val > max)
                {
                    move = new boolean[]{true,true};
                    max = val;
                    nextV = newVtt;
                }
            }
            //try taking first and passing second
            int[] newVtp = passSlice(newVt,j);

            val = x + calcVal(newVtp);
            //System.out.println("  TP: " + ats(newVtp) + " " + val);
            if(val > max)
            {
                move = new boolean[]{true,false};
                max = val;
                nextV = newVtp;
            }
        }
        int[] newVp = passSlice(V,i);
        //System.out.println("  V: " + ats(V));
        //System.out.println("  P: " + ats(newVp));
        int j = find(newVp,y);
        if(j >= 0)
        {
            //try passing first and taking second
            int[] newVpt = takeSlice(newVp,j);
            val = y + calcVal(newVpt);
            //System.out.println("  PT: " + ats(newVpt) + " " + val);
            if(val > max)
            {
                move = new boolean[]{false,true};
                max = val;
                nextV = newVpt;
            }
        }
        //try taking first and passing second
        int[] newVpp = passSlice(newVp,j);

        val = calcVal(newVpp);
        //System.out.println("  PP: " + ats(newVpp) + " " + val);
        if(val > max)
        {
            move = new boolean[]{false,false};
            max = val;
            nextV = newVpp;
        }
        V = nextV;
        //System.out.println("  NEW: " + ats(V));
        return move;
    }

    public static String ats(int [] a)
    {
        String s = "";
        for(int i = 0; i < a.length; i++)
        {
            s += a[i] + ",";
        }
        return s;
    }

    public static int[] takeSlice (int[] list, int loc)
    {
        int [] newlist = new int[list.length - loc - 1];
        for(int j = loc + 1; j < list.length; j++)
        {
            newlist[j - loc - 1] = list[j];
        }
        return newlist;
    }

    public static int[] passSlice (int[] list, int loc)
    {
        int [] newlist = list;
        if(loc >= 0)
        {
            newlist = new int[list.length-1];
            for(int k = 0; k < loc; k++)
            {
                newlist[k] = list[k];
            }
            for(int k = loc + 1; k < list.length; k++)
            {
                newlist[k-1] = list[k];
            }
        }
        return newlist;
    }

    public static double calcVal(int [] list)
    {
        if(list.length < 8)
        {
            for(int i : list)
            {
                ////System.out.print(i + ",");
            }

                ////System.out.println();
            return computeMean(list);

        }
        return smoothEstimate(list);
    }

    public static double computeMean(int[] V)
    {
        if(V.length == 1)
        {
            return V[0];
        }
        else if(V.length > 1)
        {
            double[] Es = new double[V.length];
            for(int i = 0; i < V.length; i++)
            {
                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 = computeMean(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] + computeMean(newVt);
                if(take > pass)
                {
                    Es[i] = take;
                }
                else
                {
                    Es[i] = pass;
                }
            }
            double sum = 0;
            for(double d : Es)
            {
                sum += d;
            }
            return sum/V.length;
        }
        else
        {
            return 0;
        }
    }

    public static double smoothEstimate(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;// * 1.1287 + 0.05284);
    }

    public static int find(int[] list, int search)
    {
        int first  = 0;
        int last   = list.length - 1;
        int middle = (first + last)/2;

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

            middle = (first + last)/2;
        }

        if(first > last)
        {
            return -1;
        }
        return middle;
    }
}

контроллер

import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;
public class Controller2
{
    public static void main(String [] args)
    {
        int size = 10000;
        int rounds = 1001;
        ArrayList<Integer> results = new ArrayList<Integer>();
        for(int round = 0; round < rounds; round++)
        {
            int[] envelopes = new int[size];
            for(int i = 0; i<envelopes.length; i++)
            {
                envelopes[i] = i+1;
            }
            shuffleArray(envelopes);
            Player2 p = new Player2(size);
            int cutoff = 0;
            int winnings = 0;
            for(int i = 0; i<envelopes.length; i+=2)
            {
                boolean [] take = p.takeQ(envelopes[i],envelopes[i+1]);
                if(take[0] && envelopes[i] >= cutoff)
                {
                    winnings += envelopes[i];
                    cutoff = envelopes[i];
                }
                if(take[1] && envelopes[i+1] >= cutoff)
                {
                    winnings += envelopes[i+1];
                    cutoff = envelopes[i+1];
                }
            }
            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 void shuffleArray(int[] ar)
    {
        Random rnd = new Random();
        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;
        }
    }
}

Адрес биткойна: 1BVBs9ZEP8YY4EpV868nxi2R23YfL7hdMq

Python 3 - $ 615570

На самом деле не использует оракула ... Эх :)

def algo():
    global prevs

    try:
        prevs.append(read())
    except NameError:
        prevs = [read()]

    if len(prevs) > 10000:
        prevs = [prevs[-1]]

    if read() < round(len(prevs),-1):
        take()
    else:
        passe()

Составляет список всех предыдущих конвертов и проверяет, меньше ли текущий конверт, чем количество предыдущих конвертов с шагом 10 конвертов.

Python, 87,424

Вот простой и легкий алгоритм, счастливая семерка.

def LuckyNumber7():
Test = read()
if "7" in str(Test):
    take()
else:
    passe()

test(LuckyNumber7)

По сути, он конвертирует read () в строку и проверяет, есть ли в ней семерка. Если есть, он берет конверт. Если нет, то это проходит.

Это в среднем около 81 000, я не отслеживал.