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?
Programming Praxis 
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