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

Pages: 1 2

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 : http://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