## Bingo

### February 19, 2009

Bingo is a children’s game of chance, sometimes played by adults for fun or money. Each player has a card of numbers arranged in a five-by-five grid with five randomly-chosen numbers from 1 to 15 in the first column, from 16 to 30 in the second column, 31 to 45 in the third column, 46 to 60 in the fourth column, and 61 to 75 in the fifth column; the central space is “free” and is considered to be occupied. Then a caller randomly calls numbers from 1 to 75 without replacement, each player marking the corresponding number, if it is present on their card, as occupied. The first player to have five occupied numbers in a row horizontally, in a column vertically, or along either of the two major diagonals is the winner.

What is the average number of calls required before a single card achieves bingo? In a large game with five hundred cards in play, what is the average number of calls required before any card achieves bingo?

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