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.”
#!/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))) / 1e4Mine 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
#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: if(i == 5 && j == 5) /* not 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; }[…] 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.
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"#!/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()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)))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
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(); return total / 10000; }[…] 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