Are you sick of the stupid “weighing 8 objects on a scale” interview question? How about this one:
In “The Legend of Zelda: The Minish Cap,” Link finds a vending machine which sells figurines of all the monsters in Hyrule – these machines are called gashapon in Japanese. Link wants to collect all the monsters in the machine, which accepts the local currency, “shells.”
- There are figurines of 136 monsters
- a single figure costs 1 shell
- the machine will dispense a random figure for 1 shell
- …but the machine will only vend figures of monsters Link has seen before
- for an additional 1 shell per purchase, Link can increase the probability of getting a figure he doesn’t already have, at a rate of 1% per shell. Link can spend an unlimited number of shells (up to 100%) per transaction.
- Link throws away any duplicate figurines he receives
The question: describe a strategy to acquire every figure which economizes on the number of shells spent assuming there are 136 unique monsters and figures, and :
- Link has met every monster in Hyrule before he buys any figures
- Link has never met any monsters, but has the ability to do so in between purchases
- Link has met N monsters, and has bought no figures
- Link has met N monsters, and has bought M unique figures already