Safe Haskell | None |
---|---|

Language | Haskell2010 |

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.

`>>>`

Trials: 100000 Bingos: 3615 Hit rate: 0.03615`runSimulation 100000`

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
`0`

to`35`

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