Fun with C# and Bingo
Tags: csharp, dotnet, csadvent
Published: 2022-12-03 00:16:11

> This post is part of the **C# Advent 2022** event. Please visit https://www.csadvent.christmas/ for more C# fun!

I was recently considering what it would take to make a Bingo game engine in C#. Bingo is a relatively simple game with relatively simple rules, but as is usually the case, the perceived simplicity can be deceiving once you delve into the details. 

When I looked online for inspiration, I wasn't satisfied with what I found. Very few examples used much more than the most basic C# language features, and so were missing out on some possibilities for making the code a bit more readable and expressive. 

I decided I would use this as a learning opportunity for myself, to see if I could do better. This post is for me to share some of what I learned.

If you would like to follow along with the source code, it can be found on GitHub at https://github.com/eric-king/BingoEngine

So firstly, let's review: What is [Bingo](https://en.wikipedia.org/wiki/Bingo_(American_version)) exactly? As wikipedia puts it, (American) Bingo is

> a game of chance in which each player matches the numbers printed in different arrangements on cards.

A Bingo card is defined as:

> A typical Bingo game utilizes the numbers 1 through 75. The five columns of the card are labeled 'B', 'I', 'N', 'G', and 'O' from left to right. The center space is usually marked "Free" or "Free Space", and is considered automatically filled. The range of printed numbers that can appear on the card is normally restricted by column, with the 'B' column only containing numbers between 1 and 15 inclusive, the 'I' column containing only 16 through 30, 'N' containing 31 through 45, 'G' containing 46 through 60, and 'O' containing 61 through 75.


![A standard Bingo card](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fxuecci9hg555txhp54z.jpg)

Interestingly, I've not seen any Bingo code where those parameters are explicitly laid out in an easily readable format. Most of what I found had all the pieces embedded in various loops, and to recreate the rules as laid out above, a programmer would basically have to mentally debug the program.

I want to have that basic set of parameters in an easily glanceable block of code. Here's what I came up with:

``` csharp
var columnParams = new Dictionary<string, (int MinCellValue, int MaxCellValue)>
{
	{ "B", (01,15) },
	{ "I", (16,30) },
	{ "N", (31,45) },
	{ "G", (46,60) },
	{ "O", (61,75) }
};
```
The `string` represents the label of the column that the rule applies to, and the `(int, int)` [tuple](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/value-tuples) (a C# 7.0 feature) represents the min and max values for that column. Anybody should be able to glance at that set of parameters and verify that it matches the paragraph above.

## Generating a Bingo Board

We can use that set of parameters to build a standard Bingo layout, which is basically a two-dimensional string array `string[,]`. We can start by using the column rules above to generate the random column values.

Defined elsewhere are the column labels
``` csharp
public string[] ColumnLabels { get; } = new [] { "B", "I", "N", "G", "O" };
```

and the standard row and column counts for a Bingo board.
``` csharp
public const int STANDARD_COL_COUNT = 5;
public const int STANDARD_ROW_COUNT = 5;
```

Numbers can't be repeated in the Bingo board, so the algorithm should ensure that it only adds random numbers to the column if the column doesn't already contain that number. Here's the entire column-generating algorithm:

``` csharp
private string[,] GenerateStandardBingoColumns()
{
	var columns = new string[Constants.STANDARD_COL_COUNT, Constants.STANDARD_ROW_COUNT];

	// The valid cell values are numbers between 1-75,
	// based on these column parameters
	var columnParams = new Dictionary<string, (int MinCellValue, int MaxCellValue)>
	{
		{ "B", (01,15) },
		{ "I", (16,30) },
		{ "N", (31,45) },
		{ "G", (46,60) },
		{ "O", (61,75) }
	};

	var random = new Random();
	foreach (var columnParam in columnParams)
	{
		// make sure we're working with the correct column,
		// based on the column label
		var colIndex = Array.IndexOf(ColumnLabels, columnParam.Key);

		// cell values can't repeat, so we need to keep track
		// of the previously generated values in this column
		var previouslyGeneratedValues = new List<int>();

		// calculate each cells distinct value based on the column's
		// designated value bucket as described above
		for (int rowIndex = 0; rowIndex < Constants.STANDARD_ROW_COUNT; rowIndex++)
		{
			int cellValue = GenerateDistinctRandomInRange(random, columnParam.Value, previouslyGeneratedValues);
			columns[colIndex, rowIndex] = cellValue.ToString();
			previouslyGeneratedValues.Add(cellValue);
		}
	}

	return columns;
}
```

Nice and understandable, at a glance.

The distinct random number function looks like this:

``` csharp
private static int GenerateDistinctRandomInRange(Random random, (int minValue, int maxValue) range, List<int> previouslyGeneratedValues)
{
	int newValue;
	do
	{
		newValue = random.Next(range.minValue, range.maxValue + 1);
	}
	// try again if we've already got that value
	while (previouslyGeneratedValues.Any(previousValue => newValue == previousValue));

	return newValue;
}
```

By using the same `(int, int)` tuple for the value range as before, it makes it very easy to use the `columnParam.Value` directly. Also, something tells me we may be able to re-use this function later, when drawing random Bingo numbers. 🙂

So far, so good, we can generate a grid of numbers following the standard Bingo column rules. But how do we handle win conditions?

## Win Conditions

For a standard Bingo game,

> A player wins by completing a row, column, or diagonal. The center space is usually marked "Free" or "Free Space", and is considered automatically filled. 

This means that there are 12 distinct "patterns" that a grid can form that result in a standard win condition. Each of the 5 columns, each of the 5 rows, and the 2 diagonals from corner to corner. Some examples of how we can visualize them are:

**The entire "B" column**
■□□□□
■□□□□
■□□□□
■□□□□
■□□□□

**The entire 4th row**
□□□□□
□□□□□
□□□□□
■■■■■
□□□□□

**Diagonal top-left to bottom-right** (the center square is not needed as it is "Free")
■□□□□
□■□□□
□□□□□
□□□■□
□□□□■

But beyond the "standard" game, there are other possibilities:

> In addition to a straight line, other patterns may be considered a valid bingo in special games. For example, a 2×2 square of marked squares in the upper-right-hand corner could be considered a "postage stamp". Another common special game requires players to cover the four corners. There are several other patterns, such as a Roving 'L', which requires players to cover all B's and top or bottom row or all O's and top or bottom row. Another common pattern is a blackout, covering all 24 numbers and the free space.

We may visualize those patterns like so:

**Postage Stamp**
□□□■■
□□□■■
□□□□□
□□□□□
□□□□□

**Four Corners**
■□□□■
□□□□□
□□□□□
□□□□□
■□□□■

For our code, it makes sense to create a `BingoPattern` class that contains a list of `WinCondition`s. Some patterns may only have one win condition, but others (like the "standard" pattern) may have many. A `WinCondition` will consist of a list of `Cell`s, each of which define a location (column, row) in the grid that's required so satisfy the win condition. We should also define a `Name` for the Pattern, and also for each `Wincondition`.

The approach I took is to create an interface to define the basic structure of a `BingoPattern`.

``` csharp
public interface IBingoPattern
{
    string PatternName { get; }
    List<WinCondition> WinConditions { get; init; }
}
```
Note the use of an [init only setter](https://learn.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-9#init-only-setters), a feature added with C# 9.0, for `WinConditions`.

I want each Pattern implementation to contain a default empty constructor which initializes the `WinCondition` list, so I'm enforcing that by providing an [abstract base class](https://learn.microsoft.com/en-us/dotnet/csharp/fundamentals/object-oriented/inheritance#abstract-base-classes) that looks like this:

``` csharp
public abstract class BasePattern : IBingoPattern
{
    public abstract string PatternName { get; }
    public List<WinCondition> WinConditions { get; init; }

    public BasePattern()
    {
        WinConditions = BuildWinConditions();
    }

    protected abstract List<WinCondition> BuildWinConditions();
}
```

Which means that I can create a class for each type of Pattern that I want to implement, and all each class needs to do is provide a name and a list of win conditions:

``` csharp
public class StandardPattern : BasePattern
{
    public override string PatternName => "Standard Bingo";

    protected override List<WinCondition> BuildWinConditions()
    {
        return new List<WinCondition>
        {
           // but what goes here?
        };
    }
}
```

Now we have to define the win conditions. The challenge, however, is how can we do it in as human-readable yet programmatically correct way as we can? Here's a challenge for you:

Which of the following coordinates (column, row) represent the "Four Corners" pattern? Which the "Postage Stamp" pattern?

1. (0,0), (0,4), (4,0), (4,4)
2. (0,3), (0,4), (1,3), (1,4)
3. (0,0), (1,1), (3,3), (4,4)

Admittedly that's not that hard to figure out, but I bet you still had to "step through" the coordinates and map them to a mental model of the Bingo board's grid before you were sure.

On the other hand, what if we could use those "pictograms" I provided as examples above? How fast can you recognize the patterns then?

1.
□□□■■
□□□■■
□□□□□
□□□□□
□□□□□

2.
■□□□■
□□□□□
□□□□□
□□□□□
■□□□■

3.
■□□□□
□■□□□
□□□□□
□□□■□
□□□□■

My guess is that your recognition of the patterns was near instant, and that any deviation from the expected is also nearly instantly recognizable. _I want my code to have those characteristics where possible._ So, let's do it.

C# 11.0 introduces a feature called [raw string literals](https://learn.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-11#raw-string-literals) which we can make use of here.

With a raw string literal, I can imagine `WinCondition` constructor that looks like this:

``` csharp
new WinCondition("Entire B column",
"""
■□□□□
■□□□□
■□□□□
■□□□□
■□□□□
""");
```

How good does that look? To implement that, we just have to do some basic string parsing. First, I define a `PatternCell` to hold the Column and Row of each spot on the grid that represents a part of the win condition. I do so using a [record type](https://learn.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-9#record-types), introduced as a feature of C# 9.0. 

``` csharp
public record PatternCell(int ColIndex, int RowIndex);
```

I've also defined as constants the values of the "dark square" and "light square" characters I'm using to create the pictograms.

``` csharp
public const char DARK_SQUARE = '\u25a0';
public const char LIGHT_SQUARE = '\u25a1';
```

And so now our `WinCondition` class can be defined as follows, where it receives the pictogram as a constructor parameter, splits it into individual lines, and then parses though the lines to find any character in the row that is a dark square. When it finds one, it registers that row/col as a `PatternCell` in the `WinCondition`.

``` csharp
public class WinCondition 
{
	public PatternCell[] Cells { get; init; }
    public string Description { get; init; }

    public WinCondition(string description, string pictogram)
    {
        Cells = BuildPatternCells(pictogram);
        Description = description;
    }


    private static PatternCell[] BuildPatternCells(string pictogram)
    {
        List<PatternCell> patternCells = new();
        var rows = pictogram.Split(Environment.NewLine);
        for (int rowIndex = 0; rowIndex < Constants.STANDARD_ROW_COUNT; rowIndex++)
        {
            for (int colIndex = 0; colIndex < Constants.STANDARD_COL_COUNT; colIndex++)
            {
                if (rows[rowIndex][colIndex] == Constants.DARK_SQUARE)
                {
                    patternCells.Add(new PatternCell(colIndex, rowIndex));
                }
            }
        }
        return patternCells.ToArray();
    }
}
```

This allows us to create a new Pattern with a class as simple as

``` csharp
public class PostageStampPattern : BasePattern
{
    public override string PatternName => "Postage Stamp";

    protected override List<WinCondition> BuildWinConditions()
    {
        return new List<WinCondition>
        {
            new WinCondition("4 cells at the top right corner",
            """
            □□□■■
            □□□■■
            □□□□□
            □□□□□
            □□□□□
            """),
        };
    }
}
```

or as complicated as 

``` csharp
public class StandardPattern : BasePattern
{
    public override string PatternName => "Standard Bingo";

    protected override List<WinCondition> BuildWinConditions()
    {
        return new List<WinCondition>
        {
            new WinCondition("Entire B column",
            """
            ■□□□□
            ■□□□□
            ■□□□□
            ■□□□□
            ■□□□□
            """),

            new WinCondition("Entire I column",
            """
            □■□□□
            □■□□□
            □■□□□
            □■□□□
            □■□□□
            """),

            new WinCondition("Entire N column",
            """
            □□■□□
            □□■□□
            □□□□□
            □□■□□
            □□■□□
            """),

            new WinCondition("Entire G column",
            """
            □□□■□
            □□□■□
            □□□■□
            □□□■□
            □□□■□
            """),

            new WinCondition("Entire O column",
            """
            □□□□■
            □□□□■
            □□□□■
            □□□□■
            □□□□■
            """),

            new WinCondition("Entire first row",
            """
            ■■■■■
            □□□□□
            □□□□□
            □□□□□
            □□□□□
            """),

            new WinCondition("Entire second row",
            """
            □□□□□
            ■■■■■
            □□□□□
            □□□□□
            □□□□□
            """),

            new WinCondition("Entire third row",
            """
            □□□□□
            □□□□□
            ■■□■■
            □□□□□
            □□□□□
            """),

            new WinCondition("Entire fourth row",
            """
            □□□□□
            □□□□□
            □□□□□
            ■■■■■
            □□□□□
            """),

            new WinCondition("Entire fifth row",
            """
            □□□□□
            □□□□□
            □□□□□
            □□□□□
            ■■■■■
            """),

            new WinCondition("Diagonal top left to bottom right",
            """
            ■□□□□
            □■□□□
            □□□□□
            □□□■□
            □□□□■
            """),

            new WinCondition("Diagonal top right to bottom left",
            """
            □□□□■
            □□□■□
            □□□□□
            □■□□□
            ■□□□□
            """)
        };
    }
}
```

To round things off, the WinCondition should be able to convert itself back into a pictogram, for places where we want to graphically display it.

``` csharp
public string ToPictogram() 
{
	StringBuilder stringBuilder = new();
	for (int rowIndex = 0; rowIndex < Constants.STANDARD_ROW_COUNT; rowIndex++)
	{
		for (int colIndex = 0; colIndex < Constants.STANDARD_COL_COUNT; colIndex++)
		{
			PatternCell cellToCheck = new(colIndex, rowIndex);
			bool isPartOfWinCondition = Cells.Any(cell => cell == cellToCheck);
			stringBuilder.Append(isPartOfWinCondition ? Constants.DARK_SQUARE : Constants.LIGHT_SQUARE);
		}
		stringBuilder.AppendLine();
	}

	return stringBuilder.ToString().TrimEnd();
}
```

The check here 

``` csharp
PatternCell cellToCheck = new(colIndex, rowIndex);
bool isPartOfWinCondition = Cells.Any(cell => cell == cellToCheck);
```

works because `PatternCell` is a record type, which provides [value equality](https://learn.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-9#value-equality) for free! And also note the syntax of `PatternCell cellToCheck = new(colIndex, rowIndex);` and `StringBuilder stringBuilder = new();` which both use the C# 9.0 feature [target-typed new expression](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/proposals/csharp-9.0/target-typed-new) instead of `var`.

So now we have a way to generate random Bingo boards, and we have a library of Patterns we can apply as win conditions. But how to we know when a Bingo board is a winner?

## Judging a Bingo Board 

The challenge: A typical Bingo game will probably have the players with their Boards in a different place as the Number Caller for a particular game. This means I'd like to be able to represent a particular board's configuration by some serializable code that can be easily transferred from one system to another.

There are 552,446,474,061,128,648,601,600,000 possible "standard" Bingo card configurations based on the rules we are using, so indexing each of them with a unique pre-determined code is out of the question. 🙂 So I'm going to take advantage of a library called [Hashids](https://hashids.org/net/) to generate a code that's a combination of a Standard Bingo board's 25 "cells" and a code that represents a particular game "session".  

The idea here isn't cryptographic security, but instead just a controlled way to encode a bingo board configuration in the context of a game session so it can be easily shared with a "Judge", which can then reconstitute the game board from the code and check it against the current game's win conditions and the numbers that have been called so far.

Using the Hashids library, we can take the Board's `Grid` (what I'm calling the collection of all of the board's cells) values, combine them with a string that represents a game session (it could be anything, like "BobsGame20221211") and generate a single string representation that I'm calling the `BoardCode`.

The implementation is simple.

``` csharp
private string BuildBoardCode(string sessionCode)
{
	int[] gridValues = Grid.SelectMany(row => row.Cells.Select(cell => int.Parse(cell.Value))).ToArray();
	Hashids hashids = new(sessionCode);
	string boardCode = hashids.Encode(gridValues);
	return boardCode;
}
``` 

Using this function, a board with a sessionCode of `"Test"` and a Grid that looks like

```
13      17      43      59      73
2       20      35      47      71
5       23      39      57      62
8       24      45      55      72
4       29      42      54      65
```

will generate a BoardCode of `"l6TlfeUwXfr4fEsQibcZbHnrU4HGFxIebUNKiLCYtrrf89TXKsoujUzhjeSpE"`

And the grid values can be decoded from a `sessionCode` and a `boardCode` similarly:

``` csharp
Hashids hashids = new(sessionCode);
int[] gridValues = hashids.Decode(boardCode);
```

This will give us the 25 cell values in order, which we can loop through and use to recreate the rows and columns of the board.

That gives us all we need to create a StandardBoardJudge class which can determine whether a particular Board meets any of the win conditions of the given Bingo Pattern. As a matter of fact, the code is relatively simple.

``` csharp
public static class StandardBoardJudge
{
    public static WinCondition? Evaluate(string sessionCode, string boardCode, IBingoPattern pattern, int[] numbersCalled)
    {
        // reconstitute the board with all of its values based on the board code 
        StandardBoard board = new(sessionCode, boardCode);

        // boards may match more than one win condition
        // but we only need the first one
        return pattern.WinConditions.FirstOrDefault(condition =>
        {
            // if ALL of the cells in the win condition had their
            // number called, then we have a winner
            return condition.Cells.All(cell =>
            {
                // get the value of the win condition cell in the board
                string boardCellValue = board.Grid[cell.RowIndex].Cells[cell.ColIndex].Value;

                // check to see if it was called
                return numbersCalled.Contains(int.Parse(boardCellValue));
            });
        });
    }
}
```

This code finds the first `WinCondition` where every cell in the win condition is found in numbers called and returns that win condition. If no win condition is fulfilled, the function returns null.

## Putting it all together

So now we have all the pieces we need to build a game from our simple "Bingo Engine". 

By defining a `IBingoPattern` interface, we've given ourselves a way to dynamically build a list of all of the patterns available for use. By using a `BasePattern` to ensure that each Pattern has a default empty constructor, we can easily instantiate one of each, complete with win conditions. 

We can do so with a little bit of reflection:

``` csharp
IBingoPattern[] GetPatterns()
{
    // dynamically parse all of the classes that implement 
    // the IBingoPattern interface
    var patternInterface = typeof(IBingoPattern);
    var assembly = Assembly.GetAssembly(patternInterface);

    // this shouldn't ever be null, but handled anyway
    if (assembly == null)
    {
        return Array.Empty<IBingoPattern>();
    }

    // exclude the BasePattern, which is an abstract class and cannot be instantiated
    Type[] types = assembly.GetTypes()
        .Where(x => x.GetInterfaces().Contains(patternInterface))
        .Where(x => !x.IsAbstract)
        .ToArray();

    var patterns = types.Select(x => Activator.CreateInstance(x) as IBingoPattern ?? new StandardPattern());

    return patterns.ToArray();
}
```

This means our system conforms (in a way) to the [Open-Closed Principal](https://en.wikipedia.org/wiki/Open%E2%80%93closed_principle), in that we can introduce new Patterns into the system merely by creating new classes that implement the IBingoPattern, and we don't have to touch any other part of the engine for it to work.

Included in the [source code for this article](https://github.com/eric-king/BingoEngine) is a simple Console application that begins to use the game engine to run a game of Bingo. It's not a full-blown Bingo game with multiple Players and multiple Boards per player, but it gives a starting point. 

{% youtube https://youtu.be/bBLGvzQzTV4 %}

I hope you've learned a few things here, and perhaps turning this into full-blown game can be another series of posts, if you don't beat me to it!

[![C# Advent Logo](https://www.csadvent.christmas/images/csadvent%20logo.png)](https://www.csadvent.christmas/)