June Kim posted a J Language version of bowling that is very vector-oriented. As an experiment, I coded up a vector-style version in Ruby, TDD of course. It turned out to be kind of interesting.

An Idea from June Kim, in J Language

June Kim recently posted some examples of the bowling game implemented in J language, which is a derivative of APL, with the added advantage that it can actually be typed in and displayed. The examples are probably clear to someone who knows J or APL, but are pretty cryptic to the likes of me. I’m looking at the J documentation and may bring down a version to play with. Meanwhile, my limited understanding of June’s examples suggest a solution that I’ve decided to try in Ruby.

For your amusement, here is an example, from Henry Rich, that June presented:

NB. Index of each ball that starts a frame.
framex =: 10 {. 0 {~^:a:~  _1 _1  ,~  i.@# >:@:+  10&~:
NB. Score for each ball, assuming that ball starts a frame
scoreifframe =: 3   +^:(9<])`+/@|.\   ,&0
NB. Pick the balls that actually start frames & add em up
gamescore =: [: +/ framex { scoreifframe

NB. means a comment: I know that much J already. The comments give us a hint on a possible implementation. Let me take us through the idea that I’m getting:

NB. Index of each ball that starts a frame This seems pretty straightforward: it must be a ten-element array, with each element being the index of the beginning of a frame. I truly don’t understand the code.

NB. Score for each ball, assuming that ball starts a frame This suggests that each ball is scored as if it started a frame, that is, scoring itself plus the next two if the ball at that position is ten, scoring itself plus the next two if the sum of the balls at that position is ten, and scoring itself plus the next one otherwise.

NB. Pick the balls that actually start frames & add em up Then this, I assume, means to use the first array to index into the second array, and add up the results.

Again, the code doesn’t mean much to me here. I can somewhat decode the last statement:

gamescore =: [: +/ framex { scoreifframe

If I’m understanding, that means, roughly, assign to gamescore, the sum of the framex-th element of the scoreifframe array. The [: is called a “cap” and is apparently some gimmickry to get the precedence to come out right. But if the answer is to be right, and the comments are right, then what has to happen is that we create the (sub-) array of the sums indexed by framex, and add them up.

So, armed with that understanding of the comments, I think that’s a nifty idea for a way to do the bowling game. Calculate the frame-start indexes, calculate all the frame scores as if the ball was an initial roll, and then select and add up the right ones. We’ll have to be careful about running off the end of the array of rolls, it occurs to me, in case there are strike or spare equivalents in the bonus rolls.

Let’s see if we can make this happen.

Building the Ruby Code

Begin with a test. In this case, a hookup test, which I commonly do when I’m rusty on a language or tool. Since I haven’t used Ruby for a month, this is a good time to do that:

require 'project.rb'
  class TC_MyTest < Test::Unit::TestCase

    def test_hookup
      assert_equal(1,0)
    end

  end

Sure enough, that doesn’t work, and we’re on our way.

Since I have an implementation in mind, I can see two ways to go. We could either work bottom up, creating the various vectors, or top down, writing the implementation “by intention”, and then filling in just as many blanks as we have to. My cunning plan is to proceed by intention, but to feel free to test individual vector creation methods if it seems appropriate.

I’ll begin, of course, with gutter balls:

require 'project.rb'
  class TC_MyTest < Test::Unit::TestCase

    def setup
      @game = Game.new
    end

    def test_gutter_balls
      game.rolls = [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0 ]
      assert_equal(0, game.score)
    end

  end

That, if I remember Ruby yet, which is open to question, should be roughly what it takes to put the basics in place. Let’s see. Uninitialized constant Game. That sounds about right since there is no class Game:

  class Game
  end

That should make the message change, and it does. It’s whining that “game” is not recognized. And it shouldn’t be: I need @ on the game references in the test, to make them refer to the member variable, not a non-existent temp. I’ll fix that, and if as I expect, the next message is that rolls and score aren’t implemented, fix that too, and show you the results. If that isn’t what happens, I’ll let you know.

That wasn’t too bad. The result so far:

require 'project.rb'
  class TC_MyTest < Test::Unit::TestCase

    def setup
      @game = Game.new
    end

    def test_gutter_balls
      @game.rolls = [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0 ]
      assert_equal(0, @game.score)
    end

  end 

  class Game
    attr_writer :rolls

    def score
      return 0
    end
  end

Now we could write a new test and define new functionality. Instead, I’ll block in the implementation of score in the way I have in mind. I’m envisioning a method calculate_score, taking two arrays, one of the scores for all balls assuming they’re first roll, the second the list of starting positions for the frames. So I’ll code that by intention, using Fake It Till You Make It to provide the skeleton implementations. Here’s the sketch:

  class Game
    attr_writer :rolls

    def score
      return calc_score(all_roll_scores, frame_starts)
    end

    def frame_starts
      return [0, 2, 4, 6, 87, 10, 12, 14, 16, 18]
    end

    def all_roll_scores
      return [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0 ]
    end

    def calc_store(all_scores, frame_starts)
      return frame_starts inject(0) { |sum, value| value + all_scores[value] }
    end
  end

That last bit is probably too big a bite: I could have just returned zero, but I felt like doing some work. The inject is stolen from Smalltalk, and since Ruby doesn’t have it – silly girl – we have to implement it. I decided to write a test and the implementation:

    def test_inject
      assert_equal(6, [1, 2, 3].inject(0) { | sum, each | sum + each } )
    end

  class Array

    def inject(n)
      each { |value| n = yield(n, value) }
      n
    end

  end

Let’s not go down the path of explaining inject just now, though I may come back and fill it in later. For now, let’s make things work. The inject works, but the calc store method isn’t hooking up. Oh. I spelled it calc_store, which isn’t as good as it might be. Where was my pair? With that fixed, the inject doesn’t work because it lacks a dot in front of it:

Late-breaking news: It’s not necessary to implement inject! (See footnote 1.)

    def calc_score(all_scores, frame_starts)
      return frame_starts.inject(0) { |sum, value| value + all_scores[value] }
    end

And now the complaint is more serious:

  1) Error:
test_gutter_balls(TC_MyTest):
TypeError: nil can't be coerced into Fixnum
    ./bowlingvectortest.rb:36:in `+'
    ./bowlingvectortest.rb:36:in `calc_score'
    ./bowlingvectortest.rb:36:in `inject'
    ./bowlingvectortest.rb:43:in `each'
    ./bowlingvectortest.rb:43:in `inject'
    ./bowlingvectortest.rb:36:in `calc_score'
    ./bowlingvectortest.rb:24:in `score'
    ./bowlingvectortest.rb:10:in `test_gutter_balls'

Obviously we’ve grabbed a nil somewhere, but where? Oh. Something not quite right here:

    def frame_starts
      return [0, 2, 4, 6, 87, 10, 12, 14, 16, 18]
    end

That 87 is a bit off. I think I meant 8. Let’s try that. Hmm. Now the failure is expected 0 but was 18. Clearly we’re returning the input value from inject instead of the sum. Let’s take a look at that.

    def calc_score(all_scores, frame_starts)
      return frame_starts.inject(0) { |sum, value| value + all_scores[value] }
    end

Oh. We’re returning value +, not sum +. What a tiny fool I am. We’ll fix that:

    def calc_score(all_scores, frame_starts)
      return frame_starts.inject(0) { |sum, value| sum + all_scores[value] }
    end

Now my test works. That took a little longer than I’d have liked, but all the problems were pretty straightforward and mostly due to being rusty in Ruby, combined with my usual rank stupidity.

Next Test, Open Frames

Now let’s try another test, this time open frames. I expect that to be pretty easy to get going.

    def test_open_frames
      @game.rolls = [8,1, 7,2, 6,3, 5,4, 4,5, 3,6, 2,7, 1,8, 2,7, 3,6 ]
      assert_equal(90, @game.score)
    end

I chose to make each frame different, because I’ve learned that sometimes I don’t index through the array. I don’t expect that problem here, but it was easy enough to be safe. Run the test to see that it fails. Yep. 90 expected, got zero. Let’s see what has to happen to make it work. The frame_start indexes are just fine. The scores for each roll, assuming it’s the first roll of a frame, aren’t. We’ll fix that:

    def all_roll_scores
      rolls_extended = @rolls + [0,0]
      (0..rolls_extended.size-2).collect do
        | index |
        rolls_extended[index] + rolls_extended[index+1]
      end
    end

OK. That took a little longer than I’d have liked, but I was watching the Colbert Report, and I’m rusty with Ruby. And the code is definitely less attractive than we might like. Let’s see what’s not to like.

First, I created the rolls_extended array, with two extra rolls to allow running off the end of the base array. Then we loop over all but those two, collecting the sum of the current roll, and the next one. (We’re not handling strikes and spares, so that gets the correct score for any open frames.) The collect method creates an array of the same size as the one it iterates over, with a value in each position represented by the expression there with the plus in it, i.e. in this case the sum of those two rolls.

Now, I could have calculated the range to loop over more simply: for all open frames, it’s just 0..20, and a “Fake It” implementation could have just said that. I was on a roll (pardon the expression) so I went ahead and put in the calculation that I expect to work for the future. Since it works correctly for now as well, it’s perhaps not too big a YAGNI to have done it.

I’m inclined to extend the roll array right when we assign it, and I see no reason to use the parameters for the calc_score method. Instead, we can just let it call the inner methods directly. We’re all friends here. So since all our tests are running, let’s refactor. First, extend the rolls array on assignment, and remove the references to rolls_extended:

  class Game

    def rolls=(anArray)
      @rolls = anArray + [0,0]
    end

    def score
      return calc_score(all_roll_scores, frame_starts)
    end

    def frame_starts
      return [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    end

    def all_roll_scores
      (0..@rolls.size-2).collect do
        | index |
        @rolls[index] + @rolls[index+1]
      end
    end

    def calc_score(all_scores, frame_starts)
      return frame_starts.inject(0) { |sum, value| sum + all_scores[value] }
    end
  end

Now let’s remove the parameters and just call the methods directly:

  class Game

    def rolls=(anArray)
      @rolls = anArray + [0,0]
    end

    def score
      return calc_score
    end

    def frame_starts
      return [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    end

    def all_roll_scores
      (0..@rolls.size-2).collect do
        | index |
        @rolls[index] + @rolls[index+1]
      end
    end

    def calc_score
      return frame_starts.inject(0) { |sum, value| sum + all_roll_scores[value] }
    end
  end

This is good enough for now. One more thought, though, before I go to bed. In the J implementation shows above, the calculation is to sum an array which contains just the scores for the starting frames. That’s what

framex { scoreifframe

means: take the array framex and index it into the array scoreifframe, returning those values and dropping the others. In other words, something like 2 4 {. 10 20 30 40 50 will equal 30 50.Our implementation is the reverse: it loops over the indexes and sums by looking into the big array, rather than by crunching the big array down to the right entries and then summing it up. It might be nice to implement the Ruby version to do it the same as the J version. Maybe I’ll try that tomorrow … I’m pretty sure I’m not smart enough tonight.

Morning Comes: Building Vector "Take"

Let’s make the change to select the correct frame scores first, then add them up, to match the J version. A little research tells me that Ruby doesn’t have a method that takes an array and subsets it given an array of subscripts. In J, that operation is called “take”. Let’s call it that. We’ll write a test, and a method on Array:

    def test_take
      assert_equal( [30, 50], [ 10, 20, 30, 40, 50].take([2,4]) )
    end

  class Array

    def take(anArray)
      anArray.collect { | each | self[each] }
    end
  end

That runs. Now we can improve the code that sums the array. Currently, it looks like this:

    def calc_score
      return frame_starts.inject(0) { |sum, value| sum + all_roll_scores[value] }
    end

And we can change it to this:

    def calc_score
      all_roll_scores.take(frame_starts).sum
    end

Nice. Of course there is no sum method in Array, but we’ll fix that right up:

    def sum
      inject(0) { |n, value| n + value }
    end

Tests run. My, extending the base classes is helpful, isn’t it? That stuff would all have to be done with utility methods otherwise.

What else shall I do while the sun is still just coming up? There’s just one ugly method left in the whole program, this one:

    def all_roll_scores
      (0..@rolls.size-2).collect do
        | index |
        @rolls[index] + @rolls[index+1]
      end
    end

Let’s clean that up by extracting the last bit. I think it’ll make things easier for our next step as well, because we’re going to be enhancing that code, which is the frame-scoring code. I’ll extract a frame_score method:

    def all_roll_scores
      (0..@rolls.size-2).collect do
        | index |
        frame_score(index)
      end
    end

    def frame_score(index)
        @rolls[index] + @rolls[index+1]
    end

That works. Let’s go to the one-line version of the collect, which I prefer. (Local coding standard: prefer compact code when the idiom is well known.)

    def all_roll_scores
      (0..@rolls.size-2).collect { | index | frame_score(index) }
    end

Sweet. I notice that calc_score is useless, as it is only one line long and is called only from score. So we’ll remove calc_score and put its body in score:

    def score
      all_roll_scores.take(frame_starts).sum
    end

Returns are optional in Ruby, and I’ve only got one in there. Let’s change:

    def frame_starts
      return [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    end

to:

    def frame_starts
      [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    end

Tests run, of course.

Brother, Can You "Spare" a Test?

This is about as simple as it gets. There are two “fake” things in the program right now, and new tests will drive them out. One is the fact that the frame_score always adds up two rolls, and the other is the fact that the frame_starts always step by two. These two ideas are related.

A frame scores two rolls if it is an open frame, and three if it is a strike or a spare (what’s called a “mark”). The next frame starts two rolls away, unless it is a strike, in which case it’s one. One test for spare, and one for strike, and we should force both those changes. First let’s do the spare, and change the scoring. If we were to do the strike first, we’d have to change both the scoring and the framing, so spare is easier. Begin with a test:

    def test_spare
      @game.rolls = [6,4, 6,2, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, ]
      assert_equal(24, @game.score)
    end

I think that’s right – I’m always in trouble when I have to do arithmetic. Let’s see, 6 plus 4 is 10, that’s a spare, so we get the next 6, that’s 16 for the first frame. 8 in the next frame, that’s 24. Yep, that should be right. Now we have to make it work. The relevant code is this:

    def frame_score(index)
        @rolls[index] + @rolls[index+1]
    end

This code needs to add up two elements if it’s open, three if it’s a spare. We could do that with an if, and two lines adding, one with two and one with three elements. Instead, let’s slice out either two or three elements, and sum them. I’ll change the code in frame_score to slice, then run the tests. I expect everything to work except the spare test.

    def frame_score(index)
        @rolls[index,2].sum
    end

That’s what happens. That was a bit off, refactoring with a broken test, but I got away with it. Don’t try that at home. Better would have been to comment out the spare test, do the refactoring, then put the test back. Anyway, now we have a simple thing to change, that colored 2 up above. It needs to be three in the case of a spare. (Actually it needs to be a three in the case of a bonus frame. Am I allowed to know that at this point? Well, I do know it.) Either way, I’m going to replace that 2 with a method call. frame_scoring_size, I think. And I’ll write the method:

    def frame_score(index)
      @rolls[index,frame_scoring_size(index)].sum
    end

    def frame_scoring_size(index)
      mark?(index)?3:2
    end

    def mark?(index)
      10 == @rolls[index] + @rolls[index]
    end

Darn. I expected that to work, and not only did it not fix the spare test, it broke the open frame test. Open should be 90, is 94, spare should be 24, is still 18.

I’m tempted to debug it. I’ve seen better, though: I once saw Kent Beck write a test, put in the code to make it work, have the test fail and just rip out the code and start over. Often it’s the wise thing to do, because whatever mistake you made you probably won’t make again. Here I’m a little more scared about what’s going on. So I’ll rip the code out and try again.

    def frame_score(index)
      if spare?(index)
        @rolls[index] + @rolls[index+1] + @rolls[index+2]
      else
        @rolls[index] + @rolls[index+1]
      end
    end

    def spare?(index)
      @rolls[index] + @rolls[index+1] == 10
    end

That works! Now I’ll work it back toward the frame_size solution. My suspicion is that == and + don’t have the precedence I expect, but I can verify that later. Let’s refactor slowly, having been bitten on the tail just a moment ago. First this:

    def frame_score(index)
      if spare?(index)
        @rolls[index,3].sum
      else
        @rolls[index,2].sum
      end
    end

That works. Now let’s remove the duplication by adding frame_size:

    def frame_score(index)
      @rolls[index, frame_size(index)].sum
    end

    def frame_size(index)
      if spare?(index)
        3
      else
        2
      end
    end

    def spare?(index)
      @rolls[index] + @rolls[index+1] == 10
    end

Now back to the ternary:

    def frame_score(index)
      @rolls[index, frame_size(index)].sum
    end

    def frame_size(index)
      spare?(index) ? 3 : 2
    end

Now, I know that many of you Java and C# folks might eschew the use of the ternary operator as being too terse. The XProgramming.com coding standards, however, prefer it, because our coding heritage comes from idiomatic C and C++, where such things are clear and obvious. Your mileage, etc.

The Larch

No, not the Larch, the Strike. It’s time for something completely different, the strike. I was thinking that doing the spare first was going to keep us from having to make changes in two places, but in fact to make strikes work we will still have to change the frame_size and the frame_starts method at the same time. To make that a little easier, I’ll do frame_starts separately, with a test directly against that method:

    def test_frame_start_strike
      @game.rolls = [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ]
      assert_equal([0,1,2,3,4,5,6,7,8,9], @game.frame_starts)
    end

I figured I’d throw a perfect game at it and let ‘er rip. As expected the test fails, since we always return [0,2,4,…]. Now implementing this is going to be a bit interesting. We want an array of ten integers, each differing from the previous by the frame size, which is one in the case of a strike, otherwise two. This is a natural for a language like J or APL, which will just do something like calculate the vector of differences, then do some cute cumulative sum across the vector. For me, in Ruby, it’ll take some thinking. Fortunately, it’s time to head out to meet Chet, so I’ll join you here after lunch. Don’t forget to exercise.

Building the Frame Starts Vector

Lunch was disappointing. Lu and Carl’s has gone to a different barbecue sauce, which tastes like ketchup, or catsup, I can’t decide which. I did, however, do some thinking about the frame start problem.

The array of frame starts always begins with zero. Each number after the first is equal to the previous number, plus the length of the frame that starts at that number. That’s nice, and should go into a nice closed form. I decided to do some refactoring before making the test_frame_start_strike test work. I’ll test the existing version, and then implement it other than by returning a literal. Here are the tests, with the strike one commented out:

    def test_open_frames_starts
      @game.rolls = [8,1, 7,2, 6,3, 5,4, 4,5, 3,6, 2,7, 1,8, 2,7, 3,6 ]
      assert_equal([0, 2, 4, 6, 8, 10, 12, 14, 16, 18], @game.frame_starts)
    end

#    def test_frame_start_strike
#      @game.rolls = [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ]
#      assert_equal([0,1,2,3,4,5,6,7,8,9], @game.frame_starts)
#    end

The implementation is written to take advantage of the fact that, right now, the step size is always two. So I’ll start with an array containing 0, the frame start for the first frame, and add elements that are two greater, nine more times. That looks like this:

    def frame_starts
      (1..9).inject([0]) { | starts, ignored | starts << starts[-1] +2 }
    end

That works just fine. We use our inject method, send in the starting array, then add 2 to the last item in the array, and push that value onto the array. Repeat nine times, return the final array.

Now with the implementation beefed up, let’s refactor it to be more like what we really need. Adding in the two is just what works for frames that aren’t strikes. What we’re really adding in is frame size, which is based on the frame whose position is last in the array. So we refactor this way:

    def frame_starts
      (1..9).inject([0]) { | starts, ignored | starts << starts[-1] + frame_size(starts[-1]) }
    end

    def frame_size(frame_start)
      2
    end

    def all_roll_scores
      (0..@rolls.size-2).collect { | index | frame_score(index) }
    end

    def frame_score(index)
      @rolls[index, frame_considers(index)].sum
    end

    def frame_considers(index)
      spare?(index) ? 3 : 2
    end

I wanted to use frame_size for this idea, so I renamed the old method frame_considers, representing the fact that it’s the number of balls the frame looks at for scoring purposes. Might not be the best name … keep that in mind. The tests are green.

Now we have this program where we want it. I’m expecting to be able to make the strike test for frame starts run by just modifying the frame_size method to accommodate strikes. Let’s uncomment the test …

    def test_frame_start_strike
      @game.rolls = [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ]
      assert_equal([0,1,2,3,4,5,6,7,8,9], @game.frame_starts)
    end

… and make it run:

    def frame_size(frame_start)
      @rolls[frame_start]==10 ? 1 : 2
    end

That’s all it takes. Frame size is one if the first roll is a ten, otherwise it’s two. I’m thinking I’m done, so I’ll add my two favorite tests, the perfect game, and the alternating strike-spare game. First perfect:

    def test_perfect_game
      @game.rolls = [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ]
      assert_equal(300, @game.score)
    end

That doesn’t work. You’re not surprised. I had forgotten that as yet the frame_score method only considers spares, not strikes, for bonus rolls. Here’s the code:

    def frame_score(index)
      @rolls[index, frame_considers(index)].sum
    end

    def frame_considers(index)
      spare?(index) ? 3 : 2
    end

    def spare?(index)
      @rolls[index] + @rolls[index+1] == 10
    end

We need to make that handle both strikes and spares. The result is the same in either case, we consider three rolls, otherwise two. So let’s change the spare? to mark?, which refers to either a strike or spare, rename spare? to mark?, and implement it correctly:

    def frame_considers(index)
      mark?(index) ? 3 : 2
    end

    def mark?(index)
      @rolls[index] == 10 || @rolls[index] + @rolls[index+1] == 10
    end

Tests all run. I think we’re done! Now alternating:

    def test_alternating
      @game.rolls = [ 10, 5,5, 10, 6,4, 10, 7,3, 10, 4,6, 10, 3,7, 10, 9,1 ]
      assert_equal(200, @game.score)
    end

Test runs! I confess to a bit of trepidation there: things have been going very well, and even with all the tests in place, when things go well, I keep expecting Murphy to strike. (As it were.) Let’s do the opposite alternating just for fun:

    def test_alternating_spare_first
      @game.rolls = [ 9,1, 10, 5,5, 10, 6,4, 10, 7,3, 10, 4,6, 10, 3,7, 10]
      assert_equal(200, @game.score)
    end

This one runs also. This problem is solved.

Cleaning the Code

The program works. Let’s review the code and see what needs improvement:

  class Game

    def rolls=(anArray)
      @rolls = anArray + [0,0]
    end

    def score
      all_roll_scores.take(frame_starts).sum
    end

    def frame_starts
      (1..9).inject([0]) { | starts, ignored | starts << starts[-1] + frame_size(starts[-1]) }
    end

    def frame_size(frame_start)
      @rolls[frame_start]==10 ? 1 : 2
    end

    def all_roll_scores
      (0..@rolls.size-2).collect { | index | frame_score(index) }
    end

    def frame_score(index)
      @rolls[index, frame_considers(index)].sum
    end

    def frame_considers(index)
      mark?(index) ? 3 : 2
    end

    def mark?(index)
      @rolls[index] == 10 || @rolls[index] + @rolls[index+1] == 10
    end

  end

  class Array

    def inject(n)
      each { |value| n = yield(n, value) }
      n
    end

    def sum
      inject(0) { |n, value| n + value }
    end    

    def take(anArray)
      anArray.collect { | each | self[each] }
    end

  end

I’ll just do a bit of cleanup here, because it’s getting late and my post T’ai Chi diet pepsi is wearing off. There’s duplication here:

    def frame_starts
      (1..9).inject([0]) { | starts, ignored | starts << starts[-1] + frame_size(starts[-1]) }
    end

Notice that starts[-1] appears twice. We can remove that by noticing that what we’re pushing onto the array is the new frame start, and building that this way:

    def frame_starts
      (1..9).inject([0]) { | starts, ignored | starts << new_frame_start(starts[-1]) }
    end

    def new_frame_start(frame_start)
      frame_start + frame_size(frame_start)
    end

    def frame_size(frame_start)
      @rolls[frame_start]==10 ? 1 : 2
    end

We could fold together the new_frame_start and frame_size methods, which would remove one reference to the frame_start variable, but I’d rather keep the concepts clear. YMMV.

Another thing that irritates me is that hack where we add two zeros to the end of the rolls array, and then skip over them with that - 2:

    def rolls=(anArray)
      @rolls = anArray + [0,0]
    end

    def all_roll_scores
      (0..@rolls.size-2).collect { | index | frame_score(index) }
    end

The issue is that if we don’t do something like that – if we run right up to the end of the rolls array, the all_roll_scores method will try to score the bonus balls as if there were more bonuses waiting, if those last rolls are strikes or spares. But we can’t just hold back scoring the last balls all the time, because sometimes they’re an actual frame and need to be added in.

So the hack is to add zero rolls, then score right up to the original end of the array, size-2. If those last ones think they require bonus balls, they’re zero and have no effect. I’d like to get rid of that hack. Here’s my cunning plan:

Indexing off the end of an array returns nil, rather than throwing an exception. That’s a good start. However, we can’t add nil to an integer. Let’s remove the padding and the -2, then fix the resulting test failures.

We get a few of them. The mark? method fails in two different ways: trying to compare nil to 10, or trying to add nils to get a two-roll score. Here it is:

    def mark?(index)
      @rolls[index] == 10 || @rolls[index] + @rolls[index+1] == 10
    end

I’m going to create a new method, roll(index) that returns the roll if it’s there, and otherwise zero. That’s legit, I claim, because the only time there’s a nil there is if we’re running off the end where we added zeros up until a moment ago.

    def mark?(index)
      roll(index) == 10 || roll(index) + roll(index+1) == 10
    end

    def roll(index)
      @rolls[index]==nil ? 0 : @rolls[index]
    end

Having created this method, we need to use it everywhere we referred to @rolls before, for consistency. (Another possibility would be to let the tests tell us where to do this. I’m going to proceed that way, but I fully intend to change it everywhere anyway.) Let’s run the tests.

Uh, wow! They all run! I’m a bit surprised. I expected that we’d have to change at least this method:

    def frame_score(index)
      @rolls[index, frame_considers(index)].sum
    end

I figured that the slice there could run off the end, and that it would contain nils. Better check the manual. It turns out that the manual says “Returns nil if any indexes are out of range,” but it shows an example indicating that if the tail end of a slice is out of range, you just get the elements that are in range. That’s consistent with what we’re seeing. So we’re good to go: all the reference to @rolls that could nil out are in the mark? method. I’m a bit irritated by the duplication in the roll method, though. We’re fetching @rolls[index] twice. We can fix that this way:

    def roll(index)
      (t = @rolls[index]) == nil ? 0 : t
    end

There is another way to do this, which I remember from Smalltalk days. Just for fun, let’s code this:

    def roll(index)
      @rolls[index].if_nil { 0 }
    end

Our intention here is pretty clear, I hope. There’s going to be a method if_nil, which takes a block which will be evaluated if and only if the receiver of the message is nil. Unfortunately, there is no such method … yet.

  class Object
    def if_nil
      self
    end
  end

  class NilClass
    def if_nil
      yield
    end
  end

Now there is. Way cool. (I realize that some of you may wish to discuss that with me.) Enough for tonight. I’ll leave you with one more look at the code, and we’ll discuss tomorrow what this implementation tells us.

Late-breaking news: if_nil isn’t needed either! (See footnote 2.)

  class TC_MyTest < Test::Unit::TestCase

    def setup
      @game = Game.new
    end

    def test_gutter_balls
      @game.rolls = [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0 ]
      assert_equal(0, @game.score)
    end

    def test_open_frames
      @game.rolls = [8,1, 7,2, 6,3, 5,4, 4,5, 3,6, 2,7, 1,8, 2,7, 3,6 ]
      assert_equal(90, @game.score)
    end

    def test_spare
      @game.rolls = [6,4, 6,2, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, ]
      assert_equal(24, @game.score)
    end

    def test_inject
      assert_equal(6, [1, 2, 3].inject(0) { | sum, each | sum + each } )
    end

    def test_take
      assert_equal( [30, 50], [ 10, 20, 30, 40, 50].take([2,4]) )
    end

    def test_open_frames_starts
      @game.rolls = [8,1, 7,2, 6,3, 5,4, 4,5, 3,6, 2,7, 1,8, 2,7, 3,6 ]
      assert_equal([0, 2, 4, 6, 8, 10, 12, 14, 16, 18], @game.frame_starts)
    end

    def test_frame_start_strike
      @game.rolls = [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ]
      assert_equal([0,1,2,3,4,5,6,7,8,9], @game.frame_starts)
    end

    def test_perfect_game
      @game.rolls = [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ]
      assert_equal(300, @game.score)
    end 

    def test_alternating
      @game.rolls = [ 10, 5,5, 10, 6,4, 10, 7,3, 10, 4,6, 10, 3,7, 10, 9,1 ]
      assert_equal(200, @game.score)
    end 

    def test_alternating_spare_first
      @game.rolls = [ 9,1, 10, 5,5, 10, 6,4, 10, 7,3, 10, 4,6, 10, 3,7, 10]
      assert_equal(200, @game.score)
    end

  end 

  class Game

    def rolls=(anArray)
      @rolls = anArray
    end

    def score
      all_roll_scores.take(frame_starts).sum
    end

    def frame_starts
      (1..9).inject([0]) { | starts, ignored | starts << new_frame_start(starts[-1]) }
    end

    def new_frame_start(frame_start)
      frame_start + frame_size(frame_start)
    end

    def frame_size(frame_start)
      @rolls[frame_start]==10 ? 1 : 2
    end

    def all_roll_scores
      (0..@rolls.size).collect { | index | frame_score(index) }
    end

    def frame_score(index)
      @rolls[index, frame_considers(index)].sum
    end

    def frame_considers(index)
      mark?(index) ? 3 : 2
    end

    def mark?(index)
      roll(index) == 10 || roll(index) + roll(index+1) == 10
    end

    def roll(index)
      @rolls[index].if_nil { 0 }
    end

  end

  class Array

    def inject(n)
      each { |value| n = yield(n, value) }
      n
    end

    def sum
      inject(0) { |n, value| n + value }
    end    

    def take(anArray)
      anArray.collect { | each | self[each] }
    end

  end

  class Object
    def if_nil
      self
    end
  end

  class NilClass
    def if_nil
      yield
    end
  end

Assessment in the Clear Light of Day

Let’s take a look at this vector-oriented implementation of the bowling game, and see what we can learn.

Thinking in Vectors

Frankly, I think the core vector implementation, shown here, is marvelous:

    def score
      all_roll_scores.take(frame_starts).sum
    end

We take the frame scores for each roll as if it was a first roll, take out the ones that actually do start frames, and add them up. Now that’s clean.

However, it’s also strange, if you’re not used to thinking in terms of set or vector operations. When I began to learn to think in those terms, my thoughts changed from sounding like “loop over this, if that, do this”, into more chunk oriented ideas: “score all rolls as first roll; grab all frame starts; add them together”. That may seem unnatural to you: it certainly did to me when I was learning it. Here’s something that may give you a taste for the difference, if you don’t already have it:

Consider an SQL statement like

    SELECT FirstName, LastName FROM People
    WHERE ZipCode EQ 48169

I don’t think of that as looping over all the People, finding the ones that are in 48169, and then copying the first and last name fields over. I just think poof! there’s the new set. And in fact, it might not be implemented with the loop, test and copy in the database system either. The set might be indexed on ZipCode, and it might be partitioned on FirstName+LastName. If so, the operation comes down to an indexed selection (much like our “take” operation).

It’s probable that there are operations you’re used to where you think of them as a blob. J and APL, and for that matter Extended Set Theory and Relational Database, give you more opportunities to think that way.

The result is that I like the vector focus here – and some other folks may not. Write me if you don’t, or start a discussion on the XP group. Or, for that matter, if you do like it.

Tiny Methods

Moving on, the implementation itself is interesting. To begin with, did you notice that every method is only one line long? That’s a characteristic of good Smalltalk code, and good Ruby code, in my opinion. You can’t get there in Java or C# – much less C++ – and programmers who work in those languages are often troubled by there being so many tiny methods. Smalltalkers and Rubyists love it.

Now of course some of those one-line methods might have been written out over more lines. We could have said these things:

    def frame_starts
      (1..9).inject([0]) {
        | starts, ignored |
        starts << new_frame_start(starts[-1])
      }
    end

    def frame_considers(index)
      if mark?(index)
        3
      else
        2
      end
    end

That would make the methods longer, though no different, and some people prefer things spelled out that way. The XProgramming.com coding standard prefers those more idiomatic constructs, so I am required to code that way. I’ve come to like it myself.

Inject

We used inject twice, covered it once with sum, and still have the explicit usage in frame_starts. People who haven’t used blocks and inject much find it obscure: people who are used to it love it. Let’s talk about what it does.

  • The inject operation loops over a collection: the message is sent to a collection, in our case an interval 1 through 9.
  • The operation is started off with something to accumulate into, usually a number, but often something else. In our case it's an array containing a zero.
  • Inject processes each collection element, passing the accumulator, and the element, to the block it controls. We are ignoring the element, which is done in cases like this where the information to accumulate isn't dependent on the elements. Another common case would be accumulating selected elements from a stream.
  • When the collection is fully processed, the inject expression returns the accumulator. In our case, that's the array that now contains the starting positions of each frame in the game.

Inject is well-known to Smalltalkers, and hardly known at all to folks who use languages that don’t contain blocks. Delegates and the like are a poor substitute. Requiring more syntax, they become less likely to be valuable.

Assessing its use in this program, it’s the sort of thing that would be approved in a Smalltalk or probably a Ruby shop, and would be felt to be obscure in a Java / C# shop. In the context, I’m OK with it being here.

The if_nil Method

The if_nil method is another Smalltalk / Ruby technique. It relies on blocks, on the fact that everything in the language has a class, and that nil is an element of its own class. Again, I’m OK with it in this context.

Extending Base Classes

To get inject, sum, and if_nil, I extended the base classes Array, Object, and NilClass. Wow! I actually added methods to those classes? Isn’t that dangerous, playing with fire, asking for trouble?

Certainly there are issues. When we upgrade to the next version of Ruby, which we do every year or two, we’ll need to make sure whether these new methods still work, and whether they are overriding methods that have been newly added, and so on.

Meanwhile, they make our code simpler to write, shorter, and more clear, at least to those familiar with the language and our code base. Since I represent a very small team, and work on very small programs, the cost to me of using this approach is very small. Even fairly large Ruby and Smalltalk projects do this sort of thing all the time with good results.

It’s enough to make me wonder what the deal is with all those sealed classes we get from our vendors. And it’s very much what makes me prefer programming in Ruby or Smalltalk to programming in Java or C# or C++.

Another Order of Execution?

In this implementation we build the vector of all scores, and then select the ones we want. We could probably build a version that works in another order, still vector-oriented. It would build the frame_starts first, then sum over that collection, computing the frame scores on the fly. Maybe I’ll do that in the next article: this one’s more than long enough already.

Another Language?

I’m not sure what would happen if we tried to build a vector-oriented solution in Java or C#. I’m sure it would be larger, and that we’d have to put a bunch of code in “our” classes instead of in Array and Object. On the other hand, I’m confident that we could have our score method look very much like the one we have here, processing the vectors “all at once” in a very similar way.

Might be worth doing. Any takers?

The Bottom Line

I’m very grateful to June Kim for posting the J Language bowling game. It took me into a kind of thinking that I don’t get to do very often, and has certainly produced an implementation quite unlike the others I’ve done.

I think it turned out to be rather neat. I hope you enjoyed coming along. Especially if you read all the way down to here!

Late-Breaking News

  1. My colleagues Jonas Bengtsson and Anthony Moralez leap in within minutes to tell me that inject is in there already. I removed it from my code, and it's true. I probably jumped to the conclusion that it didn't exist because it didn't compile due to the missing dot, and because whichever Hunt/Thomas book I had open said it didn't.
  2. Jonas also tells me about using "or" to get a similar effect to my if_nil. That lets me change the roll method to the following, and I can remove all the base extensions except sum and take, replacing the if_nil thusly: 
        def roll(index)
      @rolls[index] or 0
    end

Thanks for the help, guys!

Even Later-Breaking News

Christian Neukirchen informs me about the Array method values_at, which can be used with splatting to replace take. (Splatting: if you put a * in front of an array argument, it acts like that many individual arguments).

I plead ignorance of the method, because I was using the old Ruby help file and values_at came along after that version. I don’t think I have the PDF of the 1.8 pickaxe book, but I’ll look to see. Anyway, the affected method is:

    def score
      all_roll_scores.values_at(*frame_starts).sum
    end

Changed from:

    def score
      all_roll_scores.take(frame_starts).sum
    end

Thanks, Christian!