8
\$\begingroup\$

This is the third in a series of puzzles that I will be posting every Monday at Midnight PST, and the final variant of "Take It or Leave It".

The first puzzle is located Here

The second 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 15,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $15,000 (no two envelopes contain the same dollar value).

You have 5 commands at your disposal:

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

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

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

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

  5. End(): Stop the game, and walk away the money currently in your wallet (your final score).

The Rules:

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

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

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

  4. If you use Take() or Pass() on turn T, $T is removed from your wallet.

Write an algorithm that finishes the game with the maximal amount of money.

Note 1: "Maximal" in this case means the median value in your wallet after N >= 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: This puzzle has a significant difference from the first two iterations (namely, needing to pay for each envelope you take). Feel free to use any strategies from the first puzzles as a base, but be warned: They will probably (read: definitely) get a negative score without some kind of modification.

Edit: The prize condition has been removed, in light of this post on meta.

\$\endgroup\$
  • 5
    \$\begingroup\$ I don't like the idea of giving out real-world prizes here. \$\endgroup\$ – Geobits Aug 10 '15 at 14:14
  • \$\begingroup\$ Can the final score be negative? I don't think I've seen any game shows where they make the contestants pay if they play poorly. :) Good strategies will hopefully get a positive score on a consistent basis, but it would still be useful to know how a bad run gets scored. \$\endgroup\$ – Reto Koradi Aug 10 '15 at 16:14
  • \$\begingroup\$ @Reto yes, the final score can be negative, but any good strategy should come out with a net positive score. I guess you can consider a negative final score to mean that the contestant walks away with nothing (as opposed to needing to pay). \$\endgroup\$ – LivingInformation Aug 10 '15 at 16:23
  • 7
    \$\begingroup\$ I read that as "a recursive billionaire" first \$\endgroup\$ – Claudiu Aug 11 '15 at 2:29
  • 5
    \$\begingroup\$ @LivingInformation Thanks for editing the prize offers out yourself! Just wanted to say, even though there are too many problems with doing so here, giving things out to strangers on the internet for nothing in return was a pretty awesome thing to do regardless. :) \$\endgroup\$ – Doorknob Aug 11 '15 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.