Programming Challenge: BINGO

Recently we went camping to a site with evening entertainment. One activity they offered was Bingo. This included both adult and children games. We discovered that my five year old loves Bingo and that it's also a great way for her to learn her numbers. So, my wife suggested that it would be great to have a way to play Bingo as a family from time to time.

I like a little programming challenge so I though't I'd build a little Bingo Calling app that we can use at home and when on holiday. However, the first thing I decided that we need is a way to generate Bingo cards for us to mark the numbers off against. I wanted something flexible so that I can generate 'proper' cards (both UK and US style) plus simpler cards for younger children - perhaps even Picture Bingo cards as well.

I decided to start by trying to generate non-US (UK) style cards as these are by far the most complex. Actually, it turns out they are really complex to generate. The basic rules are as follows:

1. Each card is a presented on a grid of 3 rows by 9 columns
2. Each row has 5 cells containing numbers and 4 cells that are blank (Thus, on each card there are 15 cells with numbers and 12 with blanks)
3. Each column must have at least one number cell, but can also have two or three number cells
4. The first column can contain only numbers 1-9, second column 10-19, third column 20-29 and so on until the last column which can contain only numbers 80-90

Now, that doesn't actually sound too bad. But, there's one further complication:

• Cards are presented on a page made up of six separate cards. On each page each of the numbers 1 to 90 must appear ONCE and ONLY ONCE

Thus, as well as the separate rules per card there is also a rule per page that ensures that each column on the page contains only a specific number of cells (9 for the first column, 10 for the others and 11 for the last).

So, we're looking at an algorithm that generates random rows, combines these into random cards and then combines six of these cards on a single page all while honouring the rules about number of cells per row and column.

My current language of choice is Scala as I like it's power and flexibility. I'm also trying to improve my ability at functional programming and this looked like a perfect challenge for adopting the functional approach.

So, I started out with something simple to get my head around the problem. I decided my first goal would be to generate a single row containing the required template pattern of 9 columns, with 5 that will contain numbers and 4 that will be blank (putting in numbers will be a later task once I can generate the card templates). Starting with the test case:

1:  class RowGeneratorSpec extends FlatSpec with ShouldMatchers {
2:  
3:   "A Row Generator" should "generate a row with the specified number of columns" in {
4:    val generator = new RowGenerator(9, 5, new java.util.Random)
5:    val row = generator.makeRow
6:  
7:    row.cells.length should be (9)
8:   }
9:  
10:   it should "generate the specified number of slots" in {
11:    val generator = new RowGenerator(9, 5, new java.util.Random)
12:    val row = generator.makeRow
13:  
14:    row.cells.filter(_ == CardCell(Item)).length should be (5)
15:   }
16:  
17:   it should "generate the correct number of blanks" in {
18:    val generator = new RowGenerator(9, 5, new java.util.Random)
19:    val row = generator.makeRow
20:  
21:    row.cells.filter(_ == CardCell(Blank)).length should be (4)
22:   }
23:  
24:   it should "generate the same row with the same random seed" in {
25:    val generator1 = new RowGenerator(9, 5, new java.util.Random(1L))
26:    val generator2 = new RowGenerator(9, 5, new java.util.Random(1L))
27:  
28:    compareCells(generator1.makeRow.cells, generator2.makeRow.cells)
29:   }
30:  
31:   private[this] def compareCells(lhs: List[CardCell], rhs: List[CardCell]): Unit = {
32:    if ( !lhs.isEmpty ) {
33:     lhs.head should be (rhs.head)
34:     compareCells(lhs.tail, rhs.tail)
35:    }
36:   }
37:  }
38:  

Next I added some domain objects:

1:  object CellType extends Enumeration {
2:   type CellType = Value
3:   val Blank, Item = Value
4:  }
5:  
6:  case class CardCell(cellType: CellType)
7:  case class Row(cells: List[CardCell])
8:  

Then, came my initial version of the code to generate the row:

1:  class RowGenerator(columnCount: Int, slotCount: Int, random: java.util.Random) {
2:  
3:   require(slotCount <= columnCount)
4:  
5:   def makeRow(): Row = {
6:    val indexes = selectIndexes
7:  
8:    val cells = Array.ofDim[CardCell](columnCount)
9:    for ( index <- 0 until columnCount ) {
10:     cells(index) = if ( indexes.contains(index) ) CardCell(Item) else CardCell(Blank)
11:    }
12:    Row(cells.toList)
13:   }
14:  
15:   private[this] def selectIndexes = {
16:    val indexes = Set[Int]()
17:    while ( indexes.size < slotCount ) indexes += random.nextInt(columnCount)
18:    indexes
19:   }
20:  }
21:  

This code works fine, but it's pretty imperative in nature. The populating of the set of indexes and then setting values into an array is pretty typical code that would be written in languages such a Java or C++. I therefore had another go trying for a more recursive, functional solution:

1:  class RowGenerator(columnCount: Int, slotCount: Int, random: java.util.Random) {
2:  
3:   require(slotCount <= columnCount)
4:  
5:   def makeRow(): Row = Row(addToRow(Nil))
6:  
7:   private[this] def addToRow(cells: List[CardCell]): List[CardCell] = {
8:    val slotsFilled = cells.count(_ == CardCell(Item))
9:    val cellsRemaining = columnCount - cells.length
10:    val slotsRemaining = slotCount - slotsFilled
11:  
12:    (cellsRemaining, slotsRemaining) match {
13:     case (0, _) => cells
14:     case (_, 0) => addToRow(CardCell(Blank) :: cells)
15:     case (cr, sr) if ( cr == sr ) => addToRow(CardCell(Item) :: cells)
16:     case _ => if ( random.nextBoolean ) addToRow(CardCell(Item) :: cells)
17:          else addToRow(CardCell(Blank) :: cells)
18:    }
19:   }
20:  }
21:  

This new code is much more functional in nature, building the row by concatenating lists. A match is done on the state of the supplied list and the appropriate return or recursion is triggered by this match.

The code is fairly simple but also very flexible, allowing me to generate a range of different row configurations in the future. I'm also using an externally supplied Random instance to that I can seed the random with a known value and generate the same rows consistently (handle future automated call checking code should I decide to add it).

I'm happy with this part of the solution. In the next post we'll look into the first of the more complex cases: generating an individual Bingo card that complies with the row and column rules.