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.

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 609 other followers

%d bloggers like this: