Here’s a problem that I used to give to candidates. I stopped using it seriously a long time ago since I don’t believe in puzzles, but I think it’s kind of fun.
- Let’s say you have a function that simulates a random coin flip. It returns “H” or “T”. This is the only random generator available. How can write a new function that simulates a random dice roll (1…6)?
- Is there any method that guarantees that the second function returns in finite time?
- Let’s say you want to do this times where . What’s the most efficient way to do it? Efficient in terms of using the fewest amount of coin flips.
The first part is old, I think. The second and third part are follow up questions that I came up with.
I’ll give you some time to think about it!
Did you figure it out?
- There’s a multitude of ways to do this. The easiest way to do it is probably to flip the coin three times and map the outcomes like this: (HHH, 0), (HHT, 1), (HTH, 2), (HTT, 3), (THH, 4), (THT, 5), (TTH, 6), (TTT, 7). If you end up getting HHH or TTT, you flip again.
- Impossible! If you flip the coin times then there’s exactly outcomes. But we can’t partition this space evenly into 6 buckets since
- This one is trickier. Think about it in terms of the amount of information you extract. Every coin flip extracts 1 bit, but every dice roll consumes bits. This is a lower bound – you need at least that many coin flips per dice roll.
Is there a way to achieve that lower bound? Turns out there is: basically encode a long series of coin flip as a binary representation of a number between 0 and 1, then convert it to base 6. This idea resembles Arithmetic coding. Sample code:
Hope you enjoyed geeking out with a math problem this time!