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?

About these ads

Pages: 1 2

17 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.
    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;
    }
    
    
  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 : 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;

    }

  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();
    	return total / 10000;
    }
    
  14. […] provide context, I’m working through Programming Praxis Bingo Challenge and wanted to see how fast I could make this code […]

  15. Ronnie said

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 599 other followers

%d bloggers like this: