| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
BingoSim.Simulation
Contents
Description
Simulates the likelyhood of winning a children's carnival bingo game.
The game itself works like this:
- There's a 6 x 6 grid, each with it's own special character identifying it.
- There are 36 tiles, one for each grid space.
- Initially, all tiles are face down.
- To play, a contestant chooses 15 of the 36 tiles and flips them over.
- The contestant places the flipped tiles onto the correct spots.
- If placing the 15 tiles forms a bingo in any row, column, or full diagonal, it's a win. Otherwise, it's a loss.
Our question is: if one of our friends wins this game, how lucky should they consider themself? Rather than compute the probability exactly, here we run a simulation to approximate the exact probability of a win.
To represent a bingo board and the operations on them, we've created the
Board type, which is a bit vector representing the grid in row major order
where a 1 means that a tile was placed on that grid space. There is also a
hasBingo helper to figure out whether a Board has a bingo.
This module has the logic to actually carry out the simulation:
runSimulation
(Note: This module is basically the Main module, except I couldn't figure
out how to generate Haddock documentation for an executable target, not a
library target.)
Documentation
Run the entire simulation, consisting of trials trials.
Prints the results to stdout when done.
>>>runSimulation 100000Trials: 100000 Bingos: 3615 Hit rate: 0.03615
This function is called directly by the bingo-sim executable's main
method, so you can get the same effect by running bingo-sim at the command
line, instead of the Haskell REPL:
❯ bingo-sim 100000 Trials: 100000 Bingos: 3615 Hit rate: 0.03615
Simulation helpers
randomBoard :: State -> IO (Board, State) Source #
Generate a random board.
Uses a somewhat contrived strategy:
- Start with a bit sequence with fifteen 1's (
0x7fff). - Use Fisher-Yates to shuffle the individual bits among the lower 36 bits of the sequence.
This is much faster than the naive strategy of:
- Generate the numbers
0to35in a list and shuffle them. - Take the first 15, to represent picking 15 random tiles.
- Flip on the bits corresponding to each tile we picked.
The Fisher-Yates on bits approach is faster because we don't have to generate a linked list of thunks and instead can operate on a single 64-bit word.
The sacrifice is that the naive strategy nearly exactly matches our intuition for how this game works in the real world.