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:

- 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
- Use the row generating mechanism but supply hints on which cells are safe to generate Numbers/Blanks and which cells are not

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.

## No comments:

## Post a Comment