February 19, 2009
Our solution will use random numbers to simulate playing a large number of bingo games, counting the average length of a game. We represent a bingo card as a vector of length 24 with the cells of the card in column-major order. The fifteen numbers in each column are shuffled, then the appropriate count of numbers is selected from the beginning of the shuffle. Later, when a bingo game is played, each time a number is called it is changed to zero. The
card function returns a random card:
(take 5 (shuffle (range 1 16)))
(take 5 (shuffle (range 16 31)))
(take 4 (shuffle (range 31 46)))
(take 5 (shuffle (range 46 61)))
(take 5 (shuffle (range 61 76))))))
shuffle, which converts the input list to a vector, shuffles the vector by the Fisher-Yates algorithm, then converts the vector back to a list:
(define (shuffle x)
(do ((v (list->vector x)) (n (length x) (- n 1)))
((zero? n) (vector->list v))
(let* ((r (randint n)) (t (vector-ref v r)))
(vector-set! v r (vector-ref v (- n 1)))
(vector-set! v (- n 1) t))))
There are twelve ways to make bingo. Each is tested by summing the cells in the row, column, or diagonal; if any of them sum to zero, the card scores a bingo:
(define (bingo? card)
(define (test . xs)
(zero? (sum (map (lambda (x) (vector-ref card x)) xs))))
(or (test 0 1 2 3 4) ; B-column
(test 5 6 7 8 9) ; I-column
(test 10 11 12 13) ; N-column
(test 14 15 16 17 18) ; G-column
(test 19 20 21 22 23) ; O-column
(test 0 5 10 14 19) ; top row
(test 1 6 11 15 20) ; second row
(test 2 7 16 21) ; middle row
(test 3 8 12 17 22) ; fourth row
(test 4 9 13 18 23) ; bottom row
(test 0 6 17 23) ; nw-to-se diagonal
(test 4 8 15 19))) ; ne-to-sw diagonal
The heart of the simulation is a function that plays a game with n cards. The value returned by
) is a pair with the number of calls in the
car and the number of the winner (from 0 to n) in the
cdr. The birdcage is spun once at the beginning of the game, producing a random shuffle of the seventy-five numbers in the cage:
(define (play n)
(let ((cards (map (lambda (x) (card)) (range 0 n))))
(let loop ((k 0) (cage (shuffle (range 1 76))))
(if (any? bingo? cards)
(let loop ((i 0) (cards cards))
(if (bingo? (car cards))
(cons k i) ; number of calls, winner
(loop (+ i 1) (cdr cards))))
(let ((call (car cage)))
(map (lambda (card)
(do ((i 0 (+ i 1))) ((= i 24))
(if (= (vector-ref card i) call)
(vector-set! card i 0))))
(loop (+ k 1) (cdr cage)))))))
Playing 10,000 games, the average length of a game is a little bit more than 41 calls. In a large game with five hundred cards in play, the average length of a game is about twelve calls:
> (sum (map (lambda (x) (car (play 1))) (range 0 10000)))
> (sum (map (lambda (x) (car (play 500))) (range 0 10000)))
We used several library functions in coding the solution.
]) returns a list from first inclusive to past exclusive, with an optional step size.
) returns the sum of a list of integers.
) returns the first n elements of the list xs.
#t if any
]) returns a randomly-selected exact rational number between zero inclusive and one exclusive; if seed is given it resets the random seed before it returns a random number.
(randint) returns a random integer between 0 inclusive and 2^32 exclusive (the current seed).
) returns a random non-negative integer less than n.
) returns a random integer between m inclusive and n exclusive. The solution, including the needed library code, can be viewed at http://programmingpraxis.codepad.org/fQPItMI1.
It is possible, instead of doing simulations as above, to enumerate all possible bingo cards and all possible caller sequences and compute the exact probabilities. Bill Butler does the math at http://www.durangobill.com/Bingo.html.
Pages: 1 2