Take It or Leave It II: A Game Show for Computers This is the second in a series of puzzles that I will be posting every Monday at Midnight PST. The first puzzle is located Here.
Context:

A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

This week's game:

The host provides you with API access to a stack of 10,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $10,000 (no two envelopes contain the same dollar value).
You have 4 commands at your disposal:

Read(): Read the dollar figure in the envelope at the top of the stack.

Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.

Pass(): Pop off the envelope on the top of the stack.

Oracle(M): Returns the mean value of the next M envelopes in the stack, not including the one you can currently Read().



The Rules:


If you use Pass() on an envelope, the money within is lost forever.

If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing &lt; $X. Take() on one of these envelopes will add $0 to your wallet.

If you use Oracle(M) on turn T, envelopes T+1 through T+M's mean will be returned. Oracle() is disabled until turn T+M.



Write an algorithm that finishes the game with the maximal amount of money.
If you're writing your algorithm in Python, feel free to use this controller provided by @Maltysen: https://gist.github.com/livinginformation/70ae3f2a57ecba4387b5
Notes 1: &quot;Maximal&quot; in this case means the median value in your wallet after N &gt;= 1000 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.
Note 2: as all solutions to the previous part of this puzzle are valid here, reposting them has little value. Only algorithmic improvements of previous puzzles will be considered for part II.
Edit: The prize condition has been removed, in light of this post on meta.
Groovy $713337 $817829 $818227

Bootstrap code:

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 &gt;= 10000)
            throw new NoSuchElementException()
        i++
    }

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

    double oracle(int m) {
        if (m &lt;= 0 || i &lt; nextOracle || i + m &gt;= 10000)
            throw new NoSuchElementException()

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

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


Algorithm

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 &lt; 10000 - 3) {
        int value = puzzle.read()
        int i = Arrays.binarySearch(memory, memStart, 10000, value) - memStart
        if (i &lt; 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 &gt; losing) { // If we pass, we lose money automatically
            puzzle.take()
            memStart += i + 1
        } else if ((losing - value * 16 / 7) * square(Math.log(i)) &gt; 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() &amp;&amp; (
            values.contains(value2)
            ? (value1 * 2 &lt; values.sum() &amp;&amp; values.min() == value2)
            : (value1 &lt; values.min() / 2 + (values - [value1]).max())
            )) {
        puzzle.pass()
    }

    // Finish it
    while (puzzle.i &lt; puzzle.values.size()) {
        puzzle.take()
    }

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


I compare remaining values with possible values. This script is not fast (takes 1-minute per 1000x simulations)... but it will perform the simulations simultaneously.

I have no idea why my algorithm works, but it was just trial and error: lumping mathematical operations together and manipulating the constants. I ran it 5000x for the current score, in an attempt to reduce the score's fluctuations (it's +/- $4000 depending on iteration count).

Even without the oracle at the end, it should still be (barely) beating @orlp's solution for the prior puzzle.