Programming Challenge: BINGO Part 3

In previous posts here and here I started to look at generating Bingo cards using a Functional Programming approach. Firstly I built a generator for individual rows. Then  I created a recursive generator for building single Bingo cards. In this post I look at building multiple cards to create a Bingo book page.

(Unfortunately the code for this post is on my poorly MacBook Pro which I haven't got back yet. I'm therefore posting descriptions/lessons learnt only - sorry!)

UK Bingo pages are made up of 6 separate cards arranged in one column. As you may recall, each card has 3 rows of 9 cells each, with 5 of these cells containing numbers and 4 containing blanks. That makes 90 cells in total.

Each number 1 to 90 appears only once on the page. Numbers 1 to 9 can only be in the first column of any card, 10 to 19 only in the second column and so on.

To generate the pages I adopted the same approach as for cards: generate templates recursively; validate they need the card rules; then insert the numbers. If the page is not valid then generated cards are gradually rolled back and regenerated until a valid page is produced.

This approach worked fine for cards, and only a small number of rollbacks was required until a valid card was created. However, the rules for pages are somewhat more complex. After writing the recursive code I was finding that in some cases over 300 rollbacks were required to generate a valid page. Page generation was averaging at 15ms per page on my very fast MBP.

This made me consider re-evaluating my approach. In the end I decided to stick with it the way it is. Were my goal to generate vast numbers of pages in large batch runs then performance would be insufficient. However I'm looking at just being able to generate a small number of pages for a family game, so even a second or so to do so would not be a problem. A pragmatic approach to performance!

Incidentally I did go back to revisit this and try to write a generator that always produces totally valid pages first time (without any rollbacks). I implemented this in Haskell, but I never managed to come up with a set of rules/patterns that worked in every case. I'll leave that as an exercise to the reader. Jam donut and credit on my blog to them contributor of the first working Functional solution!

Now all that remains is hacking together a simple web front end for displaying the generated cards so that they can be printed out. Time to play with the Lift framework I think.