Bingo
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:
(define (card)
(list->vector (append
(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))))))
Card calls 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 (play
n)
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))))
cards)
(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)))
413249
> (sum (map (lambda (x) (car (play 500))) (range 0 10000)))
120647
We used several library functions in coding the solution. (range
first
past [
step])
returns a list from first inclusive to past exclusive, with an optional step size. (sum
xs)
returns the sum of a list of integers. (take
n
xs)
returns the first n elements of the list xs. (any?
pred?
xs)
returns #t
if any (
pred?
xs)
returns #t
, and #f
otherwise. (rand [
seed])
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). (randint
n)
returns a random non-negative integer less than n. (randint
m
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.
I’m trying to work my way through the old exercises. My Python solution is
basically a translation of the Scheme work above, with some “Pythonization.”
Mine involves generating the columns of the card, setting each number to ‘None’ as it is called.
{code:lang=python}
import random
class Card:
def __init__(self):
self.rows = [ [random.randint(1, 15),
random.randint(16, 30),
random.randint(31, 45),
random.randint(46, 60),
random.randint(61, 75)]
for x in range(5)]
# Middle one is marked
self.rows[2][2] = None
def callNum(self, num):
for row in range(5):
for col in range(5):
if self.rows[row][col] == num:
self.rows[row][col] = None
def checkBingo(self):
# Check rows
for row in self.rows:
if row == [None] * 5:
return True
# Check columns
for col in range(5):
if [self.rows[row][col] for row in range(5)] == [None] * 5:
return True
# Check diagonals
if [x[r][c] for (r,c) in enumerate(range(5))] == [None] * 5:
return True
if [self.rows[r][c] for (r,c) in enumerate(range(4, -1,-1))] == [None] * 5:
return True
return False
def play_bingo(no_of_cards):
cards = [Card() for x in range(no_of_cards)]
turns = 0
numstocall = range(1, 76)
while not any(card.checkBingo() for card in cards):
# Call a number
winningnum = random.choice(numstocall)
numstocall.remove(winningnum)
[card.callNum(winningnum) for card in cards]
turns += 1
#print “Bingo took %s turns.” % turns
return turns
turns = []
for i in range(100):
turns.append(play_bingo(1))
print “The average number of calls required before a single card achieves bingo is %.2f.” % (float(sum(turns))/len(turns))
turns = []
for i in range(100):
turns.append(play_bingo(500))
print “In a large game with five hundred cards in play, the average number of calls required before any card achieves bingo is %.2f.” % (float(sum(turns))/len(turns))
{code}
[…] given I it was the first program I wrote in the Io language Without further due here is the Io version of the Bingo game: §741 · April 16, 2011 · Challenge, Code · Tags: bingo, io-language […]
Here is my single card bingo simulation.
Checkout the implementation of 500 cards at given link: http://codepad.org/yjsI6jiz
As expected, the average number of calls for 500 cards is coming out much less then single card
[…] is my third Programming Praxis exercise, a small program which calculate the average number of calls before a win in an (American […]
Here is my solution in ruby.
Output:
The game with 1 player took 43 turns on average to end
The game with 500 players took 12 turns on average to end
I took the average over 100 games, which already took over 10 seconds to compute.
I wonder if there are any optimizations to my code.
Clojure version: default library helps to keep it short
Here is my code..
http://codepad.org/LhDnIWvt
//Bingo GAME : https://programmingpraxis.com/2009/02/19/bingo/
//rahul nanda
#include
#include
#include
using namespace std;
class Card
{
int numbers[5][5];
bool marking[5][5];
public:
Card()
{
bool numbersAssigned[75];
for(int i=0;i<75;i++)
numbersAssigned[i]=false;
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
marking[i][j]=false;//initialize marking…
int temp;
do{
temp=(rand()%15)+(i*15+1);
}while(numbersAssigned[temp-1]==true);
numbersAssigned[temp-1]=true;
numbers[i][j]=temp;//initialize numbers on the card…
}
}
}
void CheckAndMark(int calledNumber)
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
if(numbers[i][j]==calledNumber)
marking[i][j]=true;
}
}
}
bool checkBingo()
{
bool d=true;//for diagonal…
for(int i=0;i<5;i++)
{
bool r=true;;
for(int j=0;j<5;j++)
{
r=r&&marking[i][j];
d=d&&marking[j][j];
}
if(r) return true; //check Row i
if(d) return true;
bool c=true;
for(int j=0;j<5;j++)
{
c=c&&marking[j][i];
}
if(c) return true; //check column i
}
return false;
}
};
int generateUniqueCall(bool numbersCalled[])
{
int calledNumber;
do
{
calledNumber=(rand()%75)+1;
}while(numbersCalled[calledNumber-1]==true);
numbersCalled[calledNumber-1]=true;
return calledNumber;
}
int main()
{
srand(time(0));
int sum=0;
int players;
cout<>players;
players=500;
cout<>games;
games=500;
for(int count=0;count<games;count++){
int winner;
bool numbersCalled[75];
for(int i=0;i<75;i++)
numbersCalled[i]=false; //initializing numbersCalled…
Card *obj=new Card[players];
int calls=0; //calls refers to the number of calls made
bool gameOver=false;
do //game begins !
{
int calledNumber=generateUniqueCall(numbersCalled);
for(int i=0;i<players;i++)
{
obj[i].CheckAndMark(calledNumber);
if(obj[i].checkBingo())
{
gameOver=true;
winner=i+1;
break;
}
}
calls++;
}while(gameOver==false);
//system("cls");
//cout<<"\ngame "<<count+1<<" won by player "<<winner;
sum+=calls;
//cout<<"Number of calls made : "<<calls;
}
cout<<"\nAverage Number of calls made : "<<sum/games;
}
Matlab solution: https://github.com/moink/Monte-Carlo-Bingo-simulation
https://github.com/gcapell/ProgrammingPraxis/blob/master/03_bingo/bingo.go
500 boards, 1e5 games, ~2 seconds on macbook pro.
To find out when we’ve reached bingo, just count the number of hits in each row/col/diagonal. Build a data structure linking each number that can be called to a “list” of pointers to counters.
[…] Programming Praxis 3: Bingo […]
First solution I tried took about 25s to run 10,000 simulations so along with the profiler managed to knock it down to just under 5 on a Q6660
The generate_table() call takes up 60% of the total time and I think that could be sped up using intrinsics once I learn how :) and same with the is_bingoed() which could be done using a xor
[…] provide context, I’m working through Programming Praxis Bingo Challenge and wanted to see how fast I could make this code […]
I thought I’d say that the posted code was fast, but you can get a 10x improvement in speed using SSE instructions
My answer here speeds it up from taking 4.5s to just 0.38s StackOverflow
Golang: http://xojoc.pw/programming-praxis/bingo.html