Gutter Balls Isn't Enough
Lunch was fine, thanks. Zukey Lake Tavern buys their meat from the best meat market around, and they make a lovely burger. Some crispy wedge fries, a bit of slaw, and I’m all set. Bitter cold out, though: 7 degrees at 1 PM. Brrr.
I put my customer hat on while having lunch – no one noticed – and decided that while the gutter ball bowling scoring program is pretty impressive, we really need more features before we ship it. For example, someone might accidentally knock down some pins. And, who knows, a decent bowler might show up and start throwing strikes and spares. So we’ll write some additional tests and make them run. As is my practice, I’ll be using the simplest code I can imagine to make each test run. In real life, especially with a program I know as well as bowling, I’d do something a bit more general at the beginning. But you’ll notice, as often happens in this Test-Driven stuff, that starting simply doesn’t cause much backtracking. Especially in Smalltalk.
In bowling, an “open frame” is a frame (turn) where you don’t knock all the pins down, even in the two tries you are given. The score for such a frame is the total number of pins you knock down. So I’ll write a test for a game of nothing but open frames:
testAllOpen | game | game := BowlingGame new. 10 timesRepeat: [ game roll: 5. game roll: 4]. self should: [ game score = 90]
This test is supposed to bowl ten frames, mysteriously knocking down 9 pins in every frame. An unlikely game, but an easy one to program, and it’s not likely to make anything go really wrong in the game code. But as soon as we write this, we notice the duplication between this and the testAllGutters method: the temp #game, and the initialization. This calls for an instance variable, and for an SUnit setUp method:
setUp game := BowlingGame new testAllGutters 20 timesRepeat: [ game roll: 0]. self should: [ game score = 0] testAllOpen 10 timesRepeat: [ game roll: 5. game roll: 4]. self should: [ game score = 90]
In the code above, I’ve moved the temp #game to an instance variable, and initialized it in setUp, which, as in the other xUnit packages, is executed before each test. Telling the TestRunner to Run, I find, no surprise, that the new method doesn’t work: it gets a zero where it expects a 90.
There may be some really cool way to do this in the debugger, but since we know what is going wrong, we’ll fix it in the browser. We need to accumulate the score in #roll:, and return it in #score. Usually I just total it up in the roll method, but this time I think I’ll make a list of rolls instead:
roll: anInteger self rolls add: anInteger score ^self rolls inject: 0 into: [ :sum :each | sum + each ] rolls rolls isNil ifTrue: [ rolls := OrderedCollection new]. ^rolls
What’s up here? Well, the #roll: method is imagining that there’s a new variable, rolls, and that the #rolls method returns it. Then #roll: adds the incoming integer (the number of pins knocked down) to the collection.
The method #score sums the integers in the collection. The #inject:into: method is a Smalltalk idiom for summing. The block has two parameters, sum, and each. sum is initialized to zero (because it says inject: 0). The block is passed each element of the collection rolls, and the current running sum. The sum + each expression defines the next value of sum, and the method answers the final sum. Let’s don’t try to understand that for now, just take it as given: #inject:into: sums a collection. Where did the collection come from? Well, I defined it as an instance variable, and the rolls method initializes it.
All variables start empty (nil). So first time through self rolls, we send isNil to rolls, the variable, and sure enough it’s nil. So we set rolls to a new OrderedCollection (like a C# ArrayList or a Java vector). Then we return the collection. The method #roll: duly puts its integer in there, and when the day is done, score adds them up. I expect this to work. Let’s see:
Sure enough, it does. Now we’ve got to get serious. We’ll try to make spares work next, with this test:
testSpare game roll: 4. game roll: 6. game roll: 5. game roll: 4. 8 timesRepeat: [ game roll: 0. game roll: 0]. self should: [ game score = 24]
We roll one spare, which should score ten plus five, then an open frame worth 9, for a total of 24. Easy enough. Of course the code as its written now will get 19, because the five point bonus won’t be awarded. Running the test, I find that to be the case.
I’m showing you the debugger so that you can see that highlighted 19, the incorrect game score. I got that by selecting the method in the debug pulldown of TestRunner, clicking on the testSpare method in the stack, selecting “game score” with the mouse, and typing “control+P”, or “Print It”. Voila, the value of the expression prints right there. So the failure is what I expected. Now for the hard part: we have to fix it. I think I’ll do that by introducing the notion of a frame right now. I’ll rewrite #score this way:
score | score | score := 0. 1 to: 10 do: [ :frame | score := score + (rolls at: 2*frame-1) + (rolls at: 2*frame)]. ^score
OK, one thing at a time here. #to:do: is a method sent to the integer 1, causing a loop. The :frame parameter of the block will repeatedly be set to 1, 2, up to 10.
(rolls at: x) would mean the same as Java’s rolls[x]. So we’re looking in the block at two rolls in each iteration.
So each time through the block we add two rolls into score. The subscripting values, 2frame-1 and 2frame just step through the rolls collection. It’s worth noting that Smalltalk collections have their origin at 1, not zero, which makes the expressions familiar but not quite what you might expect.
The result of this change is that the original two tests still run, and the spare test still doesn’t. (If I were a fanatic, I’d have removed the spare test, shown the other two running, refactored, shown them still running, then added the spare test back in. Pardon my impatience: I got away with it this time. Now to handle the spare in the score method. I think I’ll make a new temp, for the score of each frame, and then test it for equalling ten:
score | score frameScore | score := 0. 1 to: 10 do: [ :frame | frameScore := (rolls at: 2*frame-1) + (rolls at: 2*frame). score := score + frameScore. frameScore = 10 ifTrue: [ score := score + (rolls at: 2*frame+1)]]. ^score
No biggie. We do the same sum, but if the frameScore is 10, we also add in the bonus ball, which is one past the second ball of the frame. The test runs. (You don’t believe me, do you? Watch this:)
Strike is More Difficult
Now here is where we are going to get in trouble. We will write a test that throws a strike (all ten down), then a couple or three frames that knock down some pins (but no more strikes and spares), and see if it adds up. It won’t – we know that already.
A little bit of thinking shows us that our current scheme won’t really work: we can’t just go through the rolls by twos any more. We’ll have to step, sometimes by one, sometimes by two. One way to do that is pretty simple but pretty ugly. Maybe I’ll start with that one. Here’s the test:
testStrike game roll: 10. game roll: 5. game roll: 4. game roll: 3. game roll: 0. 7 timesRepeat: [ game roll: 0. game roll: 0]. self should: [ game score = 31]
This test fails by running off the end of the ordered collection. It’s going by twos, and there are only 19 values in there, not 20.
I really hate the idea of indexing through the array, sometimes by one and sometimes by two. It’s bad enough in C# but it’s just not the way to program in Smalltalk. I might not have all my moves back, but I know enough to hate that idea. Instead, I’ll do something different. I’ll convert the rolls collection to a collection of frames: ten little arrays, each with two integers in it. Then I’ll see what I can do with that collection. I expect that I can make the simple cases work, that I’ll even break the spare, and then finally I’ll get them all working. Let’s see.
score ^self frames inject: 0 into: [ :sum :eachFrameArray | sum + (self frameScore: eachFrameArray)].
Now that’s what I’m talkin’ about! The #score method sums the frames collection, which I’m imagining to be a collection of frameArrays, each one with the rolls for one frame. We use the sum idiom, but notice t his time that we’re not just summing input integers, but instead we call self frameScore: with each array. We need to compute the sum of the elements of that array, like this:
frameScore: anArray ^anArray inject: 0 into: [ :sum :each | sum + each ]
We’ll just sum the input array, using the sum idiom again. Now where do we get the frame arrays?
frames ^(1 to: 10) collect: [ :frameIndex | Array with: (rolls at: 2*frameIndex-1) with: (rolls at: 2*frameIndex)]
This is probably a bit fancy for a beginner, but it’s simple Smalltalk idiom. The expression (1 to: 10) is a collection of the integers from 1 to 10. We send it the message #collect:, which takes a block that calculates the desired element of a new collection matching the original in size, i.e. ten elements. The values we return are two-element Arrays, with the two basic rolls of the frame. This makes our two simple cases, but now neither strike nor spare are working.
But now perhaps you see the method to my madness, no pun intended. My plan is to extend the frames method to include just the two rolls for an open frame, the original rolls plus the bonus for a spare, the original ten roll plus two bonuses for a strike frame. Then the summing logic will add up the right number of elements. The only change we need is in #frames. #frameScore: will stay the same.
Furthermore, rather than indexing through the rolls list, my plan is to do remove used rolls from the list, while just looping ten times. Let’s see what happens, as we program this by intention:
frames ^(1 to: 10) collect: [ :frameIndex | self frameArray ]
Now the idea, of course, is that frameArray will return the appropriate little array, just like before. But it no longer has the index of the current element in the rolls list. Instead, it’s going to consume them! Here’s the first cut, for ordinary frames:
frameArray ^Array with: rolls removeFirst with: rolls removeFirst
So each array is just the first two element of the rolls list, and we remove those rolls as we go. This code still has the two open frame tests working, but not the spare or strike. Let’s extend:
frameArray self strike ifTrue: [ ^self strikeFrameArray ]. self spare ifTrue: [ ^self spareFrameArray ]. ^self openFrameArray
This needs a little work, but not much:
strike ^(rolls at: 1) = 10 spare ^(rolls at: 1) + (rolls at: 2) = 10 strikeFrameArray ^Array with: rolls removeFirst with: (rolls at: 1) with: (rolls at: 2) spareFrameArray ^Array with: rolls removeFirst with: rolls removeFirst with: (rolls at: 1) openFrameArray ^Array with: rolls removeFirst with: rolls removeFirst
And yes! It works:
OK, Now What?
Are we there yet? Quite possibly we are. Let’s consider some of the well-known possibilities. First, the “perfect” game, 12 straight strikes. (That’s ten for the ten frames, plus two for your bonus throws. The test is this:
testPerfect 12 timesRepeat: [ game roll: 10 ]. self should: [ game score = 300 ]
This runs just fine! Now a special rule that I learned from a woman in Omaha. I was teaching a TDD course and she happened to be a local bowling champion. She told me that in any game of alternating strikes and spares, the score is 200. Let’s try one:
testAlternating 5 timesRepeat: [ game roll: 10. game roll: 6. game roll: 4]. game roll: 10. self should: [ game score = 200 ]
Sure enough, that runs too. Are we there yet? Yes, we are! Let’s take a break and a brief retrospective now, then a full summary in the next article. Here’s the good news:
Retrospective So Far
Mind you, I’ve gotten pretty good at doing the bowling game as a TDD demonstration. But I haven’t done it in Smalltalk for years. Our BowlingGame class has 11 methods. The longest one is three lines (not counting the method name). The rest are at most three lines, and the three-line methods are just one statement, spread over three lines for formatting clarity. We’ve got 29 lines of code, counting the method names! We’ve gone through three or four significantly different algorithms along the way, and never really broke the tests other than intentionally.
All this from a fat old man who is out of practice with Smalltalk. Ladies and gentlemen, Smalltalk rocks!
Coming Up Soon ...
In the next article, we’ll review the resulting code, and provide some references if you’d like to learn more about Smalltalk. Until then, thanks for tuning in!