Day 4 - Let's play bingo

How curious. My first job after graduating university was to program touchscreen bingo systems, so I'll be fascinated to see how accurate this is. My first note is that the bingo cards are 5x5, whereas good british cards are 9x3 or 4x4. So it's american bingo then.

This one is going to be the first opportunity for us to consider some form of data structure I think. Previously we've worked on sets of numbers, and there's been no real need for a more complex data structure at all.

But in this case, we're going to load a stream of random numbers, and then we're going to have to store a number of boards of 5x5 bingo cards. We're then going to have to step through the number list, and for each number called, we're going to go through our boards and mark the number (dab them in Bingo parlance FYI), and then we're also going to have to check for a winning card, one in this case that has a line of 5 in a row. In this case, a board is winning if there's a row or a column of marked numbers.

We also need that board to keep track of which number is marked and which are not in order to calculate the final sum for the board. This feels like it calls for a class.

We can have a board class. It can keep the 25 numbers on the board in one list, and a list of booleans indicating whether or not a number is marked seperately. We could use a multidimensional list, so something like numbers = [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15]], but I suspect it's easier to use a bit of math on a simple list of numbers. If we want to check a column, we can simply look at every 5th number, offset by the column number, so at numebr 0,5,10 for 1st column or number 1,6,11 for the second column. This is easy enough to do.

Oh, finally we need to be able to parse the data into our boards. That's a lot more complex than previous parsing, so we're going to want to consume the input file in two chunks. Firstly the first line is just the list of numbers called. Then we can skip a line, and line 3 onwards can be seen as a set of 5 lines with a board, and skip a line. We can repeat that to get all the boards.

Onwards

That's a Board class, it lets us mark numbers, it keeps track of the marked numbers.

There's two clever bits of code in here that you might not have seen before though.

Firstly, there's a range that uses a step. When you access a number inside an list you use list[n]. But sometimes you want a range rather than just one number. You can use list[n:m] to get you all the list from index n to index m-1 (it doesn't include the last index for ... reasons, just trust me). You can shorten this if you want all the way from the beginning or all the way to the end, so list[n:] and list[:m] can be handy (we'll use this shortly on the input lines).

But there's another thing, the step. By default, when you say list[m:n] it means every digit from m to n. But you can also tell it to step by more than one, so list[m:n:2] will get you every other number from a list. In our case we use self.marked[num::5] to get us every 5th number starting from number (0 to 5). That's basically a column.

Secondly, I've used another list comprehension feature, the filter clause. For a list comprehension [item for item in list] you can also put an if statement on it, for example [item for item in list if item > 5]. We use that in the score to combine the list of numebrs and the list of marked with zip to give us a list of tuples like [(False, 1), (False,2), (True, 3)...]. Instead of just item, I've used m,n to unpack the marked and number values, and then the if clause is returning only numbers that are not marked. We then pass that list to sum, and viola, our scoring mechanism.

Final thing, I want to compare boards for testing, so I've implemented the special method __eq__. This is called when you do a == b, and it does two things, if b is another Board, and if both a and b's list of numbers are the same, then it'll return true. If b is any other class, it will return NotImplemented, and python will just compare object identity instead. Finally I'm implemented repr which is called when the test framework prints objects.

So let's try this weird parsing thing next.

We want to open our file, but now we're going to read it in a unique way. We're going to read the first line and store those as numbers, and then we're going to read a card. We want to store our cards as a single long list, so we'll read five lines, strip them of their linebreaks, and then join them together, with a space between each line. We can then split them up by spaces and get 25 numbers out.

Let's go

Yuck, that parsing was more complex than I thought. We're joining together the lines, in 6's. We're including the blank line because the split will eat all the extra whitespace and it's easier to take them in chunks of 6 than to work out how to handle the first or last board being different.

Ok, let's try dabbing our test boards and see if we can get teh same result as the example. We're going to write a function that takes the call numbers and keeps dabbing until one of the boards tells it it's won, at which point it will return the winning board and we can then calculate it's score.

Blimey, wasn't expecting that to work first time!

Ok, let's try this bad boy on some real data and see what it tells us.

That worked, although I'll admit now to 1 minor bug when I first wrote this. First of all, I was still calling dab_until_win on the test data, which gave me the wrong total. Seocndly, once I fixed that, I discovered I was trying to parse the day3 data, which was resulting in some very odd errors.

Oh well, onto ...

Part 2 Find out who loses

This is really interesting, because we're after a really specific condition. As numbers are called, a board might be winning because it has a single line. But when the next number is called, it might now win on a column, so it has two lines. I was expecting something like this, keep playing until there's 2 lines or even a special pattern (I've seen christmas tree patterns on 5x5 bingo cards, as well as 4 corners plus center, and so on).

But in this case, even if a card has won, we keep playing until every card has won apart from one of them. Even then we need to keep playing until that card finally wins. We probably don't care about the other cards at that point, so I'm super tempted to start removing them from the list, that way we can wait until there's only 1 card left and then when it wins, we can return the card and the number as before. Lets try that, it's just a new version of dab_until_win for us.

Phew.

I ran into a problem I'd forgotten about there, removing items from a list while iterating through a list does really odd things to the iteration. So I had to rework the process to iterate through the boards, adding winning boards to a list of boards to delete.

The second thing that I struggled with at this point was that I had made a mistake in the is_winning code. The original cost checked for rows without multiplying. Since I'd made the point of mentioning it, this was a stupid mistake to make. More importantly, because somehow nothing so far had needed to know about the completion of rows 2-5, I didn't notice.

Finally, I added late a __str__ function,which is used to render the boards as strings. I used stars around numbers to indicate those that had been marked, making it easier to tell how well a board had been filled. This is what tipped me off to my is_winning bug, when I discovered a board being marked as winning despite not having any lines completed!