9
\$\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\$
10
  • 5
    \$\begingroup\$ I don't like the idea of giving out real-world prizes here. \$\endgroup\$
    – Geobits
    Aug 10, 2015 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\$ Aug 10, 2015 at 16:14
  • 8
    \$\begingroup\$ I read that as "a recursive billionaire" first \$\endgroup\$
    – Claudiu
    Aug 11, 2015 at 2:29
  • 1
    \$\begingroup\$ @Sparr I was conflicted on adding End(), I had a choice between one of two mutually exclusive mechanics. The first mechanic would have been paying only for the envelopes you Take() on, and the second was paying for every envelope you have the privilege of reading, incurring a fee on both a Take(), and a Pass(). I decided that the second mechanic was more interesting, as it requires the player to choose some fixed point to end the game, else they can't make any money at all. I have a feeling that this mechanic will have an interesting interplay with the Oracle. \$\endgroup\$ Aug 11, 2015 at 3:19
  • 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, 2015 at 18:42

1 Answer 1

1
\$\begingroup\$

Java, $3889.5 Median

        int highest=0;
        int topp=0,tott=0;
        for(int i=0;i<1000;i++){
            if(Read()>topp&&tott+Read()-i>tott){
                topp=Read();
                tott += Read();
                tott -= i;
                Take();
            }else{
                if(tott-i>i/2){
                    tott -= i;
                    Pass();
                }else{
                    End();
                    break;
                }
            }
            if(highest/1.1>tott){
                End();
                break;
            }
            if(tott>highest)
            highest=tott;
        }

Try it Online

\$\endgroup\$
6
  • \$\begingroup\$ Can you please add a TIO link and format your code? \$\endgroup\$
    – S.S. Anne
    Mar 26, 2020 at 22:06
  • \$\begingroup\$ When I test your algorithm I get much bigger amount of money. How did you test it? \$\endgroup\$ Mar 26, 2020 at 22:46
  • \$\begingroup\$ This code snippet is Java compatible but also C and C++ compatible and maybe other languages too. \$\endgroup\$ Mar 26, 2020 at 23:01
  • \$\begingroup\$ I ran it 1000 times and took the median, may you please clarify what you mean by format the code? \$\endgroup\$
    – John Smith
    Mar 26, 2020 at 23:44
  • \$\begingroup\$ Here is a link to my version of your code. onlinegdb.com/SyqqtXhII I must have written the test harness part wrong because I get much bigger numbers than you do. Maybe you could post all your code so I can see where I went wrong? \$\endgroup\$ Mar 28, 2020 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.