Programming Challenge: BINGO Part 2

In my last post I started looking at generating random Bingo cards as an educational game for my children. I started by generating a random row. In this post I'm going to look at generating an individual card.

If you remember, a standard UK Bingo card has 3 rows and 9 columns. Each row has 5 number cells and 4 blank cells. Each column must have at least one number cell but could have 2 or 3 number cells.

In an imperative programming model there are two common approaches to solving this problem:

1. Generate a grid for the entire card then for each cell check if it has to be a number/blank cell (to meet row and column rules) or can be randomly set
2. Use the row generating mechanism but supply hints on which cells are safe to generate Numbers/Blanks and which cells are not

As an experiment I took an altogether different approach. Instead of writing loads of logic to make sure that I generate a valid card each time I instead opted for an approach whereby I generate all three rows of the card without worrying about whether the card is valid. I then validate the card and if it's not valid then I back out the last row, generate a new one and try again at the validation. This happens up to 5 times - at which point if I'm still failing I back out the last two rows and repeat. And so on until I get a valid card.

It turns out that because the number of individual card permutations is fairly low that I on average manage to generate a card with at least one number in each column with just 3 attempts. Many times it's possible to generate it perfect on the first attempt, the worst I've seen in 25 attempts.

Quite clearly this is probably less efficient than generating a perfect card every time. However, the simplified code (i.e. very little conditional logic) makes the solution much easier to reason about for correctness. Like everything in software it's a tradeoff. For this project high volume and ultimate performance are not essential, so I'm happy to live with the downsides because of the simpler code that results.

Here's what I ended up with for the card generator:

1:  class CardGenerator(rowCount: Int, columnCount: Int, slotCount: Int, random: java.util.Random) {
2:  
3:   private[this] val Retries = 5
4:   private[this] val rowGenerator = new RowGenerator(columnCount, slotCount, random)
5:  
6:   def makeCard(): Card = {
7:    var rows = List[Row]()
8:    while ( !fullCard(rows) ) rows = addRows(rows)
9:    Card(rows)
10:   }
11:  
12:   private[this] def fullCard(rows: List[Row]) = rows.length == rowCount
13:  
14:   private[this] def addRows(rows: List[Row]): List[Row] =
15:    if ( fullCard(rows) ) rollbackIfNotValid(rows) else addNextRow(rows)
16:  
17:   private[this] def rollbackIfNotValid(rows: List[Row]) =
18:    if ( rowsAreValid(rows) ) rows else rows.tail 
19:   
20:   private[this] def rowsAreValid(rows: List[Row]): Boolean = {
21:    rows match {
22:     case Nil => true
23:     case _ if ( rows.filterNot(_.cells == Nil) == Nil ) => true
24:     case x if ( rows.map(_.cells.head).contains(CardCell(Item)) ) => rowsAreValid(x.map(row => Row(row.cells.tail)))
25:     case _ => false
26:    }
27:   }
28:  
29:   private[this] def addNextRow(rows: List[Row]): List[Row] = {
30:    for ( i <- 0 until Retries ) {
31:     val resultRows = addRows(rowGenerator.makeRow :: rows)
32:     if ( fullCard(resultRows) ) return resultRows
33:    }
34:    if ( rows == Nil ) Nil else rows.tail
35:   }
36:  }
37:  

One interesting observation: In used an imperative loop construct for implementing retries as this felt more natural than doing this recursively. One of the strengths of Scala is the ability to mix imperative and functional approaches in this way.

Also of note is the map calls on line 24, which I use to pull all the cells in the current column for validation and then again to strip the current column from all rows and pass the remaining columns recursively to the same function. Map is very powerful when you know how to use it.

In my final post on this subject I'll be looking at using the same approach to generating a full page of cards and how this proves to be not so successful.