Table of Contents

1. Introduction
- 1.1. Bingo
- 1.2. Bingo Card
2. Saving the Bingo Cards
- 2.1. Bingo Cards File Format
- 2.2. Card_File_IO Class
3. Generating the Cards
- 3.1. Generation Rules
- 3.2. Eliminating Duplicate Bingo Cards
- 3.3. Searching for Duplicate Bingo Cards
4. Executing Generate_Cards
5. Conclusion
6. References
7. Development Environment
8. History

The symbol returns the reader to the top of the Table of Contents.

1. Introduction

This article is the first of three articles describing the Bingo game suite that I developed over the past few months. The articles are published in the hope that the software may prove useful to the articles' readers. The three articles address the US version of Bingo that has 75 numbered balls.

1.1. Bingo

In the United States, bingo is a game of chance in which each player matches the numbers printed in different arrangements on cards. The game host (caller) draws at random, marking the selected numbers with tiles. When a player finds the selected numbers are arranged on their card in a row, they call out "Bingo!" to alert all participants to a winning card, which prompts the game host (or an associate assisting the host) to examine the card for verification of the win. Players compete against one another to be the first to have a winning arrangement for the prize or jackpot. After a winner is declared, the players clear their number cards of the tiles and the game host begins a new round of play.

Wikipedia, Bingo (American version) [^]

a form of lotto in which balls or slips, each with a number and one of the letters B, I, N, G, or O, are drawn at random and players cover the corresponding numbers printed on their cards, the winner being the first to cover five numbers in any row or diagonal or, sometimes, all numbers on the card.

Dictionary.com, bingo [^]

Bingo is a game of chance due to the random draws made by the caller and the random arrangement of numbers on a player's Bingo card. It is the latter that is addressed in this article.

In order for a game of Bingo to be played, it is necessary to generate and print the Bingo cards that players will use.

This article discusses the bolded items in the preceding figure.

1.2. Bingo Card

Bingo cards are composed of six rows of five columns. The first row is the card heading and contains the letters 'B', 'I', 'N', 'G', and 'O', each letter appearing in its own column. The following five rows contain random numbers that are generated by a set of rules that specify the values that are allowed to appear in a given column. An undecorated Bingo card appears as:

The center square of the 5 x 5 card is known as a "free space" that is considered as called. When 24 random numbers are inserted, the card may appear as follows.

The figure on the right was created with the requirement that stars be distributed throughout the Bingo cards. When this requirement is imposed, each Bingo card will have one star randomly placed thereon. The location of the star on each card is recorded in the Bingo card file.

The numeric value in the free space, in this case 2066057, is named the group_face and uniquely identifies the card. It is made up of the encoded card color (2 is LightCoral) and the card face number (starting at 1 up to the number of cards generated).

The layout of the card is the responsibility of the Print_Cards program (the subject of Part 2 of this series).

2. Saving the Bingo Cards

Although this article specifically addresses the generation of Bingo cards, once generated, the new Bingo cards are saved.

2.1. Bingo Cards File Format

The format of the Bingo cards file is a 128-byte header followed by a number of Bingo cards. Each card is composed of 25 bytes. The byte at the center of this collection (indexed as 13) is used to record the location of the "star" on the card.

The use of bytes as the form of the saved Bingo card was decided based upon the possibility of a large number of Bingo card being generated. For example, a file containing 800,000 25 byte Bingo cards requires a file of 20,000,128 bytes; while if unsigned 32-bit integers were to be used (in place of 8-bit bytes), the file size would be 80,000,128 bytes.

The Bingo cards file is a direct access file. The formula used to access a specific record numbered card_number is:

// in Utilities.Constants with a using statement
// using CONST = Utilities.Constants;

public  const   int     CARD_DATA_VALUES = 25;
public  const   int     CARD_VALUES_AT = 128;
public  const   int     CARD_VALUES_SIZE = 
                            CARD_DATA_VALUES * 
                            sizeof ( byte );
public  const   int     CARD_SIZE = CARD_VALUES_SIZE;

// in local compilation unit

card_offset = ( ( card_number - 1 ) * CONST.CARD_SIZE ) +
              CONST.CARD_VALUES_AT;

When a player calls "Bingo!," the caller asks the player for the group_face number printed on the card. The group is stripped from the group_face yielding the card_number that will be used in accessing the Bingo card. Note that card numbers are not stored in the Bingo card file; rather they are implied.

As each unique Bingo card is generated, its 25 byte record is appended to the Bingo card file.

2.2. Card_File_IO Class

To save the Bingo cards, the FileStream Class [^] is used. The various methods needed for saving the card file are encapsulated in the Card_File_IO class in the Utilities project. Note that the following is not the whole class but only contains those methods that are used during the generation process. The missing pieces will be discussed in the other parts of this series.

using System;
using System.IO;
using System.Linq;

using CONST = Utilities.Constants;

namespace Utilities
    {

    // ******************************************** class Card_File_IO

    public class Card_File_IO
        {
                                        // the FileStream fs is known 
                                        // only within the 
                                        // Card_File_IO class
        private FileStream   fs = null;

        // *********************************************** create_file

        /// <summary>
        /// create a new FileStream for reading and writing
        /// </summary>
        /// <param name="path">
        /// fully qualified path of the file to create
        /// </param>
        /// <param name="error_message">
        /// reference to a string that will receive the error message 
        /// from the IO system if the creation process fails
        /// </param>
        /// <returns>
        /// true, if the file is created successfully; false otherwise
        /// </returns>
        public bool create_file (     string path,
                                  ref string error_message )
            {
            bool    success = false;

            error_message = String.Empty;

            try
                {
                fs = new FileStream ( path, 
                                      FileMode.CreateNew,
                                      FileAccess.ReadWrite, 
                                      FileShare.Read );
                success = true;
                }
            catch ( Exception e )
                {
                error_message = e.Message;
                success = false;
                }

            return ( success );

            } // create_file

        ⋮
        
        // **************************************** zero_bytes_in_file

        /// <summary>
        /// zeros the specified bytes in the FileStream
        /// </summary>
        /// <param name="start_at">
        /// long value specifying the location where the zeroing will
        /// begin
        /// </param>
        /// <param name="count">
        /// integer value specifying how many bytes are to be zeroed
        /// </param>
        /// <note>
        /// the file must have been successfully opened or created by 
        /// an earlier invocation of open_file or create_file
        /// </note>
        public void zero_bytes_in_file ( long   start_at,
                                         int    count )
            {

            if ( fs != null )
                {
                fs.Seek ( start_at, SeekOrigin.Begin );
                for ( int i = 0; ( i < count ); i++ )
                    {
                    fs.WriteByte ( ( byte ) 0 );
                    }
                }

            } // zero_bytes_in_file

        ⋮

        // *************************************** write_bytes_to_file

        /// <summary>
        /// writes bytes the card file
        /// </summary>
        /// <param name="bytes">
        /// reference to a byte array from which bytes are to be 
        /// written
        /// </param>
        /// <param name="file_offset">
        /// long value specifying the location within the file where 
        /// writing will begin
        /// </param>
        /// <param name="error_message">
        /// reference to a string that will receive the error message 
        /// from the IO system if the write process fails
        /// </param>
        /// <returns>
        /// true, if the file is written successfully; false otherwise
        /// </returns>
        /// <note>
        /// the file must have been successfully opened or created by 
        /// an earlier invocation of open_file or create_file
        /// </note>
        public bool write_bytes_to_file (     
                                            byte [ ]  bytes,
                                            long      offset,
                                        ref string    error_message )
            {
            bool    success = false;

            error_message = String.Empty;
            if ( fs != null )
                {
                try
                    {
                    fs.Seek ( offset, SeekOrigin.Begin );
                    for ( int i = 0; ( i < bytes.Length ); i++ )
                        {
                        fs.WriteByte ( bytes [ i ] );
                        }
                    fs.Flush ( );
                    success = true;
                    }
                catch ( Exception e )
                    {
                    error_message = e.Message;
                    success = false;
                    }
                }

            return ( success );

            } // write_bytes_to_file

        // ************************************** append_bytes_to_file

        /// <summary>
        /// appends (writes) bytes to the end of the card file
        /// </summary>
        /// <param name="bytes">
        /// reference to a byte array from which bytes are to be 
        /// written
        /// </param>
        /// <param name="byte_count">
        /// integer value containing the number of bytes to write
        /// </param>
        /// <param name="error_message">
        /// reference to a string that will receive the error message 
        /// from the IO system if the write process fails
        /// </param>
        /// <returns>
        /// true, if the file is written successfully; false otherwise
        /// </returns>
        /// <note>
        /// the file must have been successfully opened or created by 
        /// an earlier invocation of open_file or create_file
        /// </note>
        public bool append_bytes_to_file (     
                                            byte [ ]  bytes,
                                            int       byte_count,
                                        ref string    error_message )
            {
            bool    success = false;

            error_message = String.Empty;
            if ( fs != null )
                {
                try
                    {
                    fs.Seek ( 0, SeekOrigin.End );
                    fs.Write ( bytes, 0, byte_count );
                    fs.Flush ( );

                    success = true;
                    }
                catch ( Exception e )
                    {
                    error_message = e.Message;
                    success = false;
                    }
                }

            return ( success );

            } // append_bytes_to_file

        // ************************************************ close_file

        /// <summary>
        /// closes the open card file
        /// </summary>
        /// <param name="error_message">
        /// reference to a string that will receive the error message 
        /// from the IO system if the close process fails
        /// </param>
        /// <returns>
        /// true, if the file is closed successfully; false otherwise
        /// </returns>
        /// <note>
        /// the file must have been successfully opened or created by 
        /// an earlier invocation of open_file or create_file
        /// </note>
        public bool close_file ( ref string error_message)
            {
            bool    success = false;

            error_message = String.Empty;
            try 
                {
                if ( fs != null )
                    {
                    fs.Close ( );
                    }
                success = true;
                }
            catch ( Exception e )
                {
                error_message = e.Message;
                success = false;
                }

            return ( success );

            } // close_file

        // *************************************************** Dispose

        /// <summary>
        /// disposes the card file
        /// </summary>
        /// <param name="error_message">
        /// reference to a string that will receive the error message 
        /// from the IO system if the disposal process fails
        /// </param>
        /// <returns>
        /// true, if the file is disposed successfully; false,
        /// otherwise
        /// </returns>
        public bool Dispose ( ref string error_message )
            {
            bool    success = false;

            error_message = String.Empty;
            try 
                {
                if ( fs != null )
                    {
                    fs.Dispose ( );
                    fs = null;
                    }
                success = true;
                }
            catch ( Exception e )
                {
                error_message = e.Message;
                success = false;
                }

            return ( success );

            } // Dispose

        } // class Card_File_IO

    } // namespace Utilities

The FileStream (fs) is private to the Card_File_IO class. Within the Generate_Cards application, it is created once and closed by the application_cleanup event handler, triggered by the application exit.

// *************************************** application_cleanup

void application_cleanup ( object    sender,
                           EventArgs e )
    {

    cfio.close_file ( ref error_message );
    cfio.Dispose ( ref error_message );

    } // application_cleanup

There are really no surprises in the Card_File_IO class. All of the methods contained therein are simple and straight-forward.

3. Generating the Cards

The approach to generating unique Bingo cards is:

Generate a card
Generate a hash of the values in the card
Search the hashes binary tree for the newly generated hash
If hash is found in the hashes binary tree, go to step 1
If hash was not found in the hashes binary tree:
- Insert hash into the hashes binary tree
- Append the new Bingo card to the end of the Bingo card file
- If another card needs to be generated, go to step 1

Bingo cards are generated by the BackgroundWorker [^] generate_cards_DoWork.

// ************************************* generate_cards_DoWork

void generate_cards_DoWork ( object             sender, 
                             DoWorkEventArgs    e )
    {
    BackgroundWorker  worker = ( BackgroundWorker ) sender;

    watch.Start ( );

    zero_header ( );

    for ( int i = 0; ( i < cards_to_generate ); i++ )
        {
        byte [ ]    bytes;
        uint        hash = 0;

        thread_pause_state.Wait ( );

        if ( worker.CancellationPending ) 
            { 
            e.Cancel = true;
            return; 
            }
                                // loop generates non-
                                // duplicative Bingo cards
        do 
            {
                                // generate a Bingo card
            bytes = populate_card_array ( );
                                // generate the hash for the 
                                // Bingo card excluding the 
                                // star index value
            hash = generated_hash ( bytes, 
                                    CONST.CENTER_CELL_INDEX );
                                // determine if hash is a 
                                // duplicate
            } while ( duplicate_hash ( hash ) );
                                // no hash duplicate; the hash 
                                // has been added to hashes;
                                // append the card to the end 
                                // of the card file
        append_bingo_card ( bytes );
                                // update progress bar
        worker.ReportProgress ( 0, ( i + 1 ) );
        }
                                // all cards generated
    watch.Stop ( );

    elapsed_time = watch.Elapsed.TotalSeconds;
    e.Result = elapsed_time;

    } // generate_cards_DoWork

generate_cards_DoWork is a BackgroundWorker [^]. The algorithm is based on the observation:

If the hash of a Bingo card duplicates an earlier hash, then there is a non-zero probability that the latter Bingo card duplicates an earlier Bingo card.

Note that duplicate hashes do not mean that two Bingo cards are duplicates. Rather, it means that a collision of hashes has occurred. However, two hashes that are not duplicates means that the associated Bingo cards are not duplicates.

If a duplicate hash is encountered, the newly created Bingo card is not added to the growing file of Bingo cards and a new Bingo card is generated.

3.1. Generation Rules

The values in a given column must adhere to the following rules:

The 'B' column may contain only values from 1 - 15
The 'I' column may contain only values from 16 - 30
The 'N' column may contain only values from 31 - 45
The 'G' column may contain only values from 46 - 60
The 'O' column may contain only values from 61 - 75

No duplicate values may appear in any column.

The method responsible for generating the values in a card is populate_card_array.

// in Utilities.Constants with a using statement
// using CONST = Utilities.Constants;

public  const   int     CARD_DATA_VALUES = 25;
public  const   int     CARD_VALUES_AT = 128;
public  const   int     CARD_VALUES_SIZE = 
                            CARD_DATA_VALUES * 
                            sizeof ( byte );
public  const   int     CARD_SIZE = CARD_VALUES_SIZE;
public  const   int     CENTER_CELL_INDEX = 12;
public  const   int     COLUMNS = 5;
public  const   int     ROWS = 5;

// in local compilation unit

const   int     ALLOWED_IN_COLUMN = 15;

// *************************************** populate_card_array

byte [ ] populate_card_array ( )
    {
                                // allowed is int because 
                                // Enumerable.Range is int
    List < int >    allowed = new List < int > ( );
    byte [ ]        bytes = new byte [ card_size ];
    int             cell = 0;
    int             index = 0;

    for ( int column = 0; 
            ( column < CONST.COLUMNS ); 
              column++ )
        {
                                // generate the 15 allowed 
                                // values for this column
        allowed = Enumerable.Range (
            ( 1 + ( column * ALLOWED_IN_COLUMN ) ), 
            ALLOWED_IN_COLUMN ).ToList ( );
                                // for the center column there 
                                // are only 4 rows however we 
                                // generate the free space 
                                // value for simplicity then 
                                // replace it with the star 
                                // position for this card

                                // for each row, choose a 
                                // value from the allowed 
                                // values and add it to the 
                                // array of bytes
        for ( int row = 0; ( row < CONST.ROWS ); row++)
            {
                                // obtain a value from zero 
                                // to ( allowed.Count - 1 )
            index = random.Next ( allowed.Count );

            bytes [ cell++ ] = ( byte ) allowed [ index ];
                                // then remove the allowed 
                                // value at index (this 
                                // eliminates duplicates in 
                                // the column)
            allowed.RemoveAt ( index );
            }
        }
                                // generate the star index
                                // have 25 indices (0-24) less
                                // the center cell index (a 
                                // star is never placed in the 
                                // center square); randomly 
                                // choose the index of the 
                                // square that is to have the 
                                // star from star_indices 
    index = random.Next ( star_indices.Count );
                                // replace the center square 
                                // with the index of the star 
                                // position for this card
    bytes [ CONST.CENTER_CELL_INDEX ] = 
        ( byte ) star_indices [ index ];

    return ( bytes );

    } // populate_card_array

For each column, populate_card_array first generates a list (allowed) that contains the values allowed by the generation rules for the current column. Note that Enumerable.Range [^] is defined in the System.Link namespace and requires the using statement "using System.Linq;". Then for each row, a random number [^], between 0 and the current number of values in the allowed list is generated. (Note that the value returned by random.Next is always less than allowed.Count.) This value becomes an index into the allowed list that points to a value to be inserted into the card array (bytes). When the value is inserted into the bytes array, it is removed from the allowed list. This insures that duplicates are not inserted into any column.

Note that populate_card_array generates 25 values although only 24 values are valid. The center square of the Bingo card is to contain a random number that is an index to the location of the star on the Bingo card. To obtain this value efficiently, prior to the execution of generate_cards_DoWork, initialize_star_indices is invoked to generate the allowed index values in star_indices.

// *********************************** initialize_star_indices

// generates the allowed indices for the positioning of the 
// star

void initialize_star_indices ( )
    {

    star_indices = Enumerable.Range ( 
                        0,
                        CONST.CARD_DATA_VALUES ).ToList ( );
    star_indices.RemoveAt ( CONST.CENTER_CELL_INDEX );
    
    } // initialize_star_indices

Without initialize_star_indices the indices would have to be generated each time that a Bingo card was generated. populate_card_array randomly selects an index from star_indices and places that value in the center square.

3.2. Eliminating Duplicate Bingo Cards

The populate_card_array method insures that duplicate values do not occur in a Bingo card. However, there is another rule that must be satisfied — no two Bingo cards generated by this program may be duplicates. To this end, a hash of the values in a Bingo card array was needed.

The Bingo card is passed to generated_hash that generates and returns an unsigned 32-bit integer hash for the Bingo card array. The index of the center square (CONST.CENTER_CELL_INDEX) is passed as the exclusion index.

// ******************************************** generated_hash

/// <summary>
/// computes the FNV hash of its parameter
/// </summary>
/// <param name="bytes">
/// byte array containing items for which a hash is required
/// </param>
/// <param name="exclude">
/// integer index into bytes of an element that will be 
/// excluded from the generation of the hash; to include all 
/// values that are in bytes, set exclude to a value less than 
/// zero or greater than the length of bytes
/// </param>
/// <returns>
/// unsigned integer that is the hash of bytes
/// </returns>
/// <reference>
/// FNV hash in https://archive.vn/SFYTe#selection-477.0-477.8
/// </reference>
uint generated_hash ( byte [ ]  bytes,
                      int       exclude )       // zero based
    {
    uint hash = 2166136261;

    unchecked 
        {
        for ( int i = 0; ( i < bytes.Length ); i++ )
            {
            if ( i == exclude )
                {
                continue;
                }
            hash = ( hash * 16777619 ) ^ bytes [ i ];
            }
        }
        
    return ( hash );

    } // generated_hash

The square that will have a star printed therein should not participate in the hash generation and so is excluded. The hash returned by generated_hash is passed to duplicate_hash.

3.3. Searching for Duplicate Bingo Cards

During the generation of Bingo cards, it is necessary to avoid duplicates. Recall that if two objects have different hash codes, the two objects are not equal. There is a problem in that all hashes, generated for all previously generated Bingo cards, must be compared against the hash of a newly generated Bingo card. The structure that this program uses for the storage of these hashes is a binary tree of unsigned integers named hashes. It is declared in the Find_Or_Add class of the Utilities project.

using System.Collections.Generic;

namespace Utilities
    {
    
    // ********************************************* class Find_Or_Add
    
    public class Find_Or_Add : List < uint >
        {

        private static List < uint > hashes = new List < uint > ( );

        // *********************************************** find_or_add
        
        public bool find_or_add (     uint  hash,
                                  ref int   hash_collisions )
            {
            bool found = true;
            int  position = this.BinarySearch ( hash );
            
            found = ( position >= 0 );
            if ( found )
                {
                hash_collisions++;
                }
            else 
                {
                position = ~position;
                this.Insert ( position, hash );
                }
           
            return ( found );
            
            } // find_or_add

        } // class Find_Or_Add
    
    } // namespace Utilities

So if 400,000 Bingo cards were to be generated, hashes binary tree would have 400,000 nodes. Each time that a new Bingo card is generated, its hash must be computed and compared against the growing number of items in hashes.

using FOA = Utilities.Find_Or_Add;
⋮
FOA                 foa = new FOA ( );
⋮
// ******************************************** duplicate_hash

// there may be a hash collision, if there is, duplicate_hash 
// returns true

bool duplicate_hash ( uint  hash )
    {

    return ( foa.find_or_add (     hash,
                               ref hash_collisions ) );

    } // duplicate_hash

In the case where duplicate_hash returns true, the do-while loop

        do 
            {
            bytes = populate_card_array ( );
            hash = generated_hash ( bytes, 
                                    CONST.CENTER_CELL_INDEX );
            } while ( duplicate_hash ( hash ) );

is executed again. If duplicate_hash returns false, the new Bingo card is written to the Bingo card file, and the next, if any, Bingo card is generated.

When all Bingo cards have been generated, the Bingo file header is written.

// *********************************************** emit_header

void emit_header ( ) 
    {
    byte [ ] bytes;
    long     header_offset = ( long ) ( int ) CONST.HEADER_AT;

    bytes = header_values_to_byte_array ( version,
                                          number_cards,
                                          cards_start_at,
                                          card_size,
                                          date_created );

    cfio.write_bytes_to_file (     bytes,
                                   header_offset,
                               ref error_message  );

    } // emit_header

emit_header invokes the helper header_values_to_byte_array to convert the individual values that make up the header into the byte array that will be written as the header.

// ******************************* header_values_to_byte_array

// converts individual header items into a single header array

byte [ ] header_values_to_byte_array ( int  version,
                                       int  number_cards,
                                       int  cards_start_at,
                                       int  card_size,
                                       int  date_created )
    {

    using ( MemoryStream ms = new MemoryStream ( ) )
        {
        using ( BinaryWriter bw = new BinaryWriter ( ms ) )
            {
            bw.Write ( version );
            bw.Write ( number_cards );
            bw.Write ( cards_start_at );
            bw.Write ( card_size );
            bw.Write ( date_created );

            return ( ms.ToArray ( ) );
            }
        }

    } // header_values_to_byte_array

4. Executing Generate_Cards

In order to execute, Generate_Cards requires the following information:

The location where the Bingo card file is to be saved
The number of cards to generate

To avoid permission issues, the default directory for Generate_Cards is C:\Users\Public\Bingo. When the Browse button is clicked, the existing files in the default directory will be displayed. Choosing an existing file will result in a warning like:

Once an output file is specified, the number of cards to be generated is solicited, the Go button is clicked and Generate_Cards executes to conclusion.

In this case, 800,000 cards were specified.

To verify the card generation, I utilize the ViewFile [^] tool.

The value 0x03 (3 decimal) is the version number; the value 0xC3500 (800,000 decimal) is the number of cards contained in this file; the value 0x80 (128 decimal) is the starting byte of the Bingo cards; the value 0x19 (25 decimal) is the number of bytes in each Bingo card; and 0x134B03D (20230205 decimal) is the date that this Bingo card file was created. The first card is visible at byte 128. If ViewFile were to display the left-side in decimal (by clearing the hexadecimal checkbox), the display would be the following.

Starting at byte 128, the first five bytes are the values of the first ('B') column; the next five bytes are the values of the second ('I') column; the next two bytes are the first two values of the third ('N') column; the next byte is the index of the star (4); the next two bytes are the last two values of the third ('N') column; the next five bytes are the values of the fourth ('G') column; and the next five bytes are the values of the fifth ('O') column.

If these values were to be placed onto a Bingo card, they would appear as in the following figure. This is what Print_Cards does and is the subject of the next article in this series.

Note that the values in these columns adhere to the prior generation rules.

Finally, I thought it best to validate the stars positioning. The data was collected from the Bingo card file and converted to a DataTable that was converted to a CSV file. The CSV file was opened by Excel and a graph of the data was plotted.

The result was what was expected: the distribution of stars was relatively even and there were no stars placed in the center square. The sum of all distributions was 800,000, the number of cards that were generated.

5. Conclusion

Generate_Cards produces a file containing unique Bingo cards. The next step is to print these cards under user specifications. This is the subject of the second article in this series.

6. References

7. Development Environment

The software presented in this article was developed in the following environment:

Microsoft Windows 7 Professional Service Pack 1

Microsoft Visual Studio 2008 Professional

Microsoft .Net Framework Version 3.5 SP1

Microsoft Visual C# 2008

8. History

Bingo - Part 1 of 3 - Generate Cards

02/10/2023

Original Article

Bingo Game Suite - Part 1