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

### 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)[0], xrange(10000))) / 1e4
print sum(map(lambda _: play(500)[0], 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[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}

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[][5], int n);
static int check_bingo(elem card[][5], int row, int col);

void single_card_bingo_simulate(void)
{
elem card[5][5];
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[][5], 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[][5], 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[2][2] = 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[0][0] == nil && @grid[1][1] == nil && @grid[2][2] == nil && @grid[3][3] == nil && @grid[4][4] == nil
return true if @grid[4][0] == nil && @grid[3][1] == nil && @grid[2][2] == nil && @grid[1][3] == nil && @grid[0][4] == 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[12] = 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[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;

}

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[12] = 0;
return bingo_grid;
}

bool is_bingoed(const std::array<int,25>& grid) {
// Check columns
if(grid[0] == 0 && grid[5] == 0 && grid[10] == 0 && grid[15] == 0 && grid[20] == 0)
return true;
if(grid[1] == 0 && grid[6] == 0 && grid[11] == 0 && grid[16] == 0 && grid[21] == 0)
return true;
if(grid[2] == 0 && grid[7] == 0 && grid[12] == 0 && grid[17] == 0 && grid[22] == 0)
return true;
if(grid[3] == 0 && grid[8] == 0 && grid[13] == 0 && grid[18] == 0 && grid[23] == 0)
return true;
if(grid[4] == 0 && grid[9] == 0 && grid[14] == 0 && grid[19] == 0 && grid[24] == 0)
return true;
// Check rows
if(grid[0] == 0 && grid[1] == 0 && grid[2] == 0 && grid[3] == 0 && grid[4] == 0)
return true;
if(grid[5] == 0 && grid[6] == 0 && grid[7] == 0 && grid[8] == 0 && grid[9] == 0)
return true;
if(grid[10] == 0 && grid[11] == 0 && grid[13] == 0 && grid[14] == 0)
return true;
if(grid[15] == 0 && grid[16] == 0 && grid[17] == 0 && grid[18] == 0 && grid[19] == 0)
return true;
if(grid[20] == 0 && grid[21] == 0 && grid[22] == 0 && grid[23] == 0 && grid[24] == 0)
return true;
// Check the two diagonals
if(grid[0] == 0 && grid[6] == 0 && grid[18] == 0 && grid[24] == 0)
return true;
if(grid[4] == 0 && grid[8] == 0 && grid[16] == 0 && grid[21] == 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();