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

### 18 Responses to “Bingo”

1. Graham said

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

```#!/usr/bin/env python

import random

def card():
cols = [random.sample(xrange(a, b), 5) for (a, b) in
zip([1, 16, 31, 46, 61], [16, 31, 46, 61, 76])]
return [num for col in cols for num in col]

def bingo(c):
_test = lambda xs: sum(c[x] for x in xs) == 0
if any(map(_test, [
xrange(5),              # B
xrange(5, 10),          # I
[10, 11, 12, 13],       # N
xrange(14, 19),         # G
xrange(19, 24),         # O
[0, 5, 10, 14, 19],     # 1st row
[1, 6, 11, 15, 20],     # 2nd row
[2, 7, 16, 21],         # 3rd row
[3, 8, 12, 17, 22],     # 4th row
[4, 9, 13, 18, 23],     # 5th row
[0, 6, 17, 23],         # nw to se diag
[4, 8, 15, 19]])):      # ne to sw diag
return True
else:
return False

def find_winner(cards):
for i in xrange(len(cards)):
if bingo(cards[i]):
return i
return None

def play(n):
cards = [card() for _ in xrange(n)]
cage = range(1, 76)
random.shuffle(cage)
round, winner = 0, 0
while not winner:
if any(map(bingo, cards)):
winner = find_winner(cards)
return round, winner
else:
round += 1
call = cage.pop()
for c in cards:
for i in xrange(24):
if c[i] == call:
c[i] = 0

if __name__ == "__main__":
print sum(map(lambda _: play(1), xrange(10000))) / 1e4
print sum(map(lambda _: play(500), xrange(10000))) / 1e4
```
2. Sasha said

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 = 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}

3. […] 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 […]

4. Vikas Tandi said

Here is my single card bingo simulation.
As expected, the average number of calls for 500 cards is coming out much less then single card

```#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define CYCLES 1000

typedef struct elem
{
int number;
int found;
}elem;

static int check_number(elem card[], int n);
static int check_bingo(elem card[], int row, int col);

void single_card_bingo_simulate(void)
{
elem card;
int cycle;
long long sum;
int avg;

srand((unsigned int)time(NULL));

/* run bingo simulation for CYCLES times */
for(cycle = 0, sum = 0; cycle < CYCLES; cycle++)
{
int num_call;
int i, j, range, offset;

/* fill card with random numbers */
for(i = 0, range = 15, offset = 1; i < 5; i++, offset += 15)
{
for(j = 0; j < 5; j++)
{
card[i][j].number = (rand() % range) + offset;
card[i][j].found = 0;
}
}

/* keep calling until bingo */
for(num_call = 0; ;)
{
int rand_num;
/* selet a random number between 1 to 75 including 1 and 75 */
rand_num = (rand() % 75) + 1;
num_call++;

/* check if the random number is present in card */
if(check_number(card, rand_num))
break;
}
sum += num_call;
}

/* print average number of calls */
avg = sum/CYCLES;
printf("average number of calls = %d\n", avg);
}

/* set found if the number is found. Then check condition for bingo and return 1 if true; otherwise return 0; */
static int check_number(elem card[], int n)
{
int i, j;

for(i = 0; i < 5; i++)
{
for(j = 0; j < 5; j++)
{
if(card[i][j].found == 0 && card[i][j].number == n)
{
card[i][j].found = 1;
goto FOUND;
}
}
}

FOUND:
return 0;

return check_bingo(card, i, j);
}

/* return 1 if bingo; otherwise return 0 */
static int check_bingo(elem card[], int row, int col)
{
int i, j;

/* check row */
for(i = 0; (i < 5) && (card[row][i].found == 1); i++);
if(i == 5)
return 1;

/* check column */
for(i = 0; (i < 5) && (card[i][col].found == 1); i++);
if(i == 5)
return 1;

/* check first diagonal */
if(row == col)
{
for(i = 0; (i < 5) && (card[i][i].found == 1); i++);
if(i == 5)
return 1;
}

/* check second diagonal */
if((row + col) == 4)
{
for(i = 0, j = 4; (i < 5) && (card[i][j].found == 1); i++, j--);
if(i == 5)
return 1;
}
return 0;
}

```
5. […] is my third Programming Praxis exercise, a small program which calculate the average number of calls before a win in an (American […]

6. Rens said

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.

```module Bingo
GRID_SIZE = 5
FREE_TOKEN = nil
class Card
def initialize
@grid = []
randomize
end

def randomize
(0...GRID_SIZE).each do |i|
first, last = i*15+1, (i+1)*15
pool = (first..last).to_a.sort_by { rand }
@grid << pool[0...GRID_SIZE].sort
end

# The center grid is FREE
@grid = FREE_TOKEN
end

def to_s
@grid.each {|a| puts a.join(' ')}
end

def bingo?
# check horozontaly
(0...GRID_SIZE).each { |i| return true if @grid[i].count(nil) == GRID_SIZE }
# check horozontaly
(0...GRID_SIZE).each { |i| return true if @grid.transpose[i].count(nil) == GRID_SIZE }
# check diagolaly
return true if @grid == nil && @grid == nil && @grid == nil && @grid == nil && @grid == nil
return true if @grid == nil && @grid == nil && @grid == nil && @grid == nil && @grid == nil
# no bingo
false
end

def call(n)
@grid.each_with_index { |c, i| c.each_with_index { |r, j| @grid[i][j] = nil if r == n } }
bingo?
end
end

class Game
# number of players
def initialize(n)
@cards = []
n.times { @cards << Card.new }
@callable = (1..75).to_a.sort_by { rand }
end

def play
bingo = false
calls = 0
until bingo do
number = random_number
calls += 1

@cards.each do |c|
bingo = true if c.call(number)
end
end
calls
end

def random_number
raise "No more numbers" unless @callable.size > 0
@callable.pop
end
end
end

average = (0..100).inject { |sum| sum += Bingo::Game.new(1).play } / 100
puts "The game with 1 player took #{average} turns on average to end"
average = (0..100).inject { |sum| sum += Bingo::Game.new(500).play } / 100
puts "The game with 500 players took #{average} turns on average to end"
```
7. ftt said
```#!/usr/bin/env python

import random

WIN_INDICES = [
range(0, 5), # columns
range(5, 10),
range(10, 15),
range(15, 20),
range(20, 25),
range(0, 25, 5), # rows
range(1, 25, 5),
range(2, 25, 5),
range(3, 25, 5),
range(4, 25, 5),
[0, 6, 12, 18, 24], # diagonals
[4, 8, 12, 16, 20]
]

def make_card():
card = []
# fill by columns
card.extend(random.sample(xrange(1, 15), 5))
card.extend(random.sample(xrange(16, 30), 5))
card.extend(random.sample(xrange(31, 45), 5))
card.extend(random.sample(xrange(46, 60), 5))
card.extend(random.sample(xrange(61, 75), 5))
card = 0
return card

def check_bingo(card, number):
for i in xrange(25):
if card[i] == number:
card[i] = 0
for indices in WIN_INDICES:
if sum(card[i] for i in indices) == 0:
return True
return False

def play(cards):
pool = range(1, 76)
random.shuffle(pool)
calls = 0
while pool:
number = pool.pop()
calls += 1
for c in cards:
if check_bingo(c, number):
return calls
return calls

def main():
print 'Average number of calls required before a single card achieves bingo: {0}'.format(sum(play([make_card()]) for i in xrange(100)) * 0.01)
print 'Average number of calls required before any card among five hundred in play achieves bingo: {0}'.format(sum(play([make_card() for j in xrange(500)]) for i in xrange(100)) * 0.01)

if __name__ == '__main__':
main()
```
8. kawas said

Clojure version: default library helps to keep it short

```(defn card-new []
(vec (concat (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))))))

(defn card-nths [card & nths] (for [i nths] (nth card i)))

(defn card-columns [card]
(map #(apply card-nths card %)
[[0 1 2 3 4] [5 6 7 8 9] [10 11 12 13] [14 15 16 17 18] [19 20 21 22 23]]))

(defn card-lines [card]
(map #(apply card-nths card %)
[[0 5 10 14 19] [1 6 11 15 20] [2 7 16 21] [3 8 12 17 22] [4 9 13 18 23]]))

(defn card-diags [card]
(map #(apply card-nths card %) [[0 6 17 23] [4 8 15 19]]))

(defn card-mark [v card]
(vec (map #(if (= v %) nil %) card)))

(defn bingo? [card]
(or (some #(every? nil? %) (card-columns card))
(some #(every? nil? %) (card-lines card))
(some #(every? nil? %) (card-diags card))))

(defn play [ncard]
(let [cards (for [_ (range ncard)] (card-new))
rand75 (fn [] (inc (rand-int 75)))]
(loop [cards cards v (rand75) marked #{}]
(if (marked v)
(recur cards (rand75) marked)
(let [new-cards (map #(card-mark v %) cards)
new-marked (conj marked v)]
(if (some bingo? new-cards)
(count new-marked)
(recur new-cards (rand75) new-marked)))))))

(apply + (map (fn [_] (play 1)) (range 10000)))
```
9. rahul said

//Bingo GAME : https://programmingpraxis.com/2009/02/19/bingo/
//rahul nanda
#include
#include
#include
using namespace std;
class Card
{
int numbers;
bool marking;
public:
Card()
{
bool numbersAssigned;
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;
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;

}

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

11. ianpakismet said

http://ianp.org/2013/01/17/praxis-winning-at-bingo/

My solution differs from most (all?) of the others here in that it calculates exact probabilities rather than using a Monte Carlo approach to solving the problem.

12. […] Programming Praxis 3: Bingo […]

13. Ronnie said

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

```boost::pool_allocator<int> pool;
template<typename T>
static void fisher_yates(T& source) {
const size_t len = source.size();
for(size_t i = 1; i < len;++i) {
std::swap(source[i],source[rand() % (i+1)]);
}
}
std::array<int,25> generate_table() {
std::array<int,25> bingo_grid;
for(int i = 0 ; i < 25;++i) {
switch(i) {
case 0: case 1: case 2: case 3: case 4:
bingo_grid[i] = rand() % 15 + 1;
break;
case 5: case 6: case 7: case 8: case 9:
bingo_grid[i] = rand() % 15 + 16;
break;
case 10: case 11: case 12: case 13: case 14:
bingo_grid[i] = rand() % 15 + 31;
break;
case 15: case 16: case 17: case 18: case 19:
bingo_grid[i] = rand() % 15 + 46;
break;
case 20: case 21: case 22: case 23: case 24:
bingo_grid[i] = rand() % 15 + 61;
break;
}
}
bingo_grid = 0;
return bingo_grid;
}

bool is_bingoed(const std::array<int,25>& grid) {
// Check columns
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
// Check rows
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
// Check the two diagonals
if(grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
if(grid == 0 && grid == 0 && grid == 0 && grid == 0)
return true;
return false;
}
void display_bingo(boost::multi_array<int,2>& bingo_grid) {
printf("\n");
for(int j = 0;j < bingo_grid.size();j++) {
for(int i = 0; i < 5;i++) {
printf("%d ",bingo_grid[j][i]);
}
printf("\n");
}
}
static bool mark_card(const int card,std::array<int,25>& bingo_grid) {
for(auto &i : bingo_grid)
if(card == i) {
i = 0;
return true;
}
return false;
}

int play_game() {
// Bingo is 5 columns, each column(n) is random permutation of 1-15*n
// Fisher-Yates to generate random permutations

// Create 500 playing cards
const int max = 500;
std::vector<std::array<int,25>> bingo_cards;
bingo_cards.reserve(max);
for(int i = 0; i<max;++i) {
bingo_cards.push_back(generate_table());
//display_bingo(bingo_cards[i]);
}
// Random shuffle 75 cards
auto iter = boost::counting_range(1,76);
std::vector<int> cards(std::begin(iter),std::end(iter));
fisher_yates(cards);
bool is_finished = false;
int counter = 0;
for(auto card : cards) {
for(auto& playing_card : bingo_cards) {
if(mark_card(card,playing_card)) {
//display_bingo(playing_card);
if(is_bingoed(playing_card))
return counter;
}
}
counter++;
}
return counter;
}
int bingo() {
srand(time(NULL));
int total = 0;
for(int i = 0 ; i < 10000;i++) {
total+=play_game();
}
boost::singleton_pool<boost::pool_allocator_tag, sizeof(int)>::release_memory();