Uncle Bob’s Bowling Game Kata

August 11, 2009

Someone mentioned Uncle Bob’s Bowling Game Kata to me a few days ago; it is apparently famous as a tutorial on object-oriented programming and test-driven development, though I had never heard of either Uncle Bob or his Bowling Game Kata.

A game of tenpins bowling lasts ten frames, in each of which the bowler makes one or two attempts to knock down ten pins arranged in a triangle. If the bowler knocks down all ten pins on the first attempt (that’s called a “strike”), he scores ten pins plus the number of pins knocked down on his next two rolls. If the bowler knocks down all ten pins after two attempts (that’s called a “spare”), he scores ten pins plus the number of pins knocked down on his next roll. If the bowler fails to knock down all ten pins (that’s called an “open frame”), he scores the number of pins he knocked down. The scores accumulate through all ten frames. At the last frame, if necessary, the pins are reset for one or two additional rolls to count the final bonus. The sample scoresheet below shows how the calculations work:

Drawing by my daughter Kate

For instance, the score in the second frame is 9, the sum of the two balls in the open frame. The score in the third frame is 15, which is 10 for the spare plus 5 on the next ball. The score in the ninth frame is 20, which is 10 for the strike plus 10 for the spare on the first two balls of the tenth frame. The score in the tenth frame is 16, which is 10 for the spare plus 6 for the extra ball, which is a bonus ball not really part of any frame (the two balls of the tenth frame have already been rolled).

Your task is to write a function that calculates the score of a tenpins bowling game. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

15 Responses to “Uncle Bob’s Bowling Game Kata”

  1. Here’s my attempt for the bowling game kata written in Haskell:

    pins [x,y] = x+y                      -- last frame
    pins [x,y,z] = x+y+z                  -- last frame
    pins (x:y:z:xs)
       | x == 10 = 10+y+z + pins (y:z:xs) -- Strike
       | x+y == 10 = 10+z + pins (z:xs)   -- Spare
       | otherwise = x+y  + pins (z:xs)   -- open frame
    
  2. You’ve created a small but unreadable solution to the bowling kata, but that’s not the point of the exercise.

    Robert Martin wrote a good explanation of this kata here: http://www.butunclebob.com/ArticleS.UncleBob.TheBowlingGameKata

  3. programmingpraxis said

    You’ve got to be kidding. Here is Uncle Bob’s code, reading from “The Fifth Test” on slide 52:

    public class Game {
      private int rolls[] = new int[21];
      private int currentRoll = 0;

      public void roll(int pins) {
        rolls[currentRoll++] = pins;
      }

      public int score() {
        int score = 0;
        int frameIndex = 0;
        for (int frame = 0; frame < 10; frame++) {
          if (isStrike(frameIndex)) {
            score += 10 + strikeBonus(frameIndex);
            frameIndex++;
          } else if (isSpare(frameIndex)) {
            score += 10 + spareBonus(frameIndex);
            frameIndex += 2;
          } else {
            score += sumOfBallsInFrame(frameIndex);
            frameIndex += 2;
          }
        }
        return score;
      }

      private boolean isStrike(int frameIndex) {
        return rolls[frameIndex] == 10;
      }

      private int sumOfBallsInFrame(int frameIndex) {
        return rolls[frameIndex] + rolls[frameIndex+1];
      }

      private int spareBonus(int frameIndex) {
        return rolls[frameIndex+2];
      }

      private int strikeBonus(int frameIndex) {
        return rolls[frameIndex+1] + rolls[frameIndex+2];
      }

      private boolean isSpare(int frameIndex) {
        return rolls[frameIndex] + rolls[frameIndex+1] == 10;
      }
    }

    This is far less readable than my solution. Look at all the variables: rolls, currentRoll, score, frame, and frameIndex. A reader’s first task is to figure out what all those variables mean. Quickly: What is the relationship between frame and frameIndex? Between currentRoll and frameIndex? Why do you need two functions, roll and score, when the only requirement is to compute one result, the score? Why is the score identifier used in two different ways, once as a function and once as a variable within the function? It’s not too complicated to work all that out, but how is it better to force your reader to do all that work than to just write the function as I did? You can’t possibly claim with any degree of conviction that Uncle Bob’s version is more readable than mine.

    I am also unimpressed with the testing done by Uncle Bob. In the parlance of my pins function, Uncle Bob did the following tests:

    (assert (pins 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) 0)
    (assert (pins 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) 20)
    (assert (pins 5 5 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) 16)
    (assert (pins 10 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) 24)
    (assert (pins 10 10 10 10 10 10 10 10 10 10 10 10) 300)

    That’s rather uninspiring. There are three boundary tests, one strike test, and one spare test. None of the test cases offer a realistic bowling game; even the sample given in the specification of the problem is not used in testing. And I never did find the definition of rollMany, though its meaning is clear enough; I suppose if I read far enough back the definition is given somewhere. It’s also not clear to me how the currentRoll variable is re-initialized between tests, though that may just be because I’m unfamiliar with the language.

    To my mind, my code is far more readable. It’s not cluttered with all those extraneous functions isSpare, isStrike, spareBonus, strikeBonus, and sumOfBallsInFrame; such simple one-liners could easily be moved into the place where they are called. The pattern-matching clearly and simply identifies strikes, spares and open frames, and the local bindings make it easy to calculate the correct score for each case. There is no need for a frame counter, which is used only to run from 1 to 10, and no need to figure out how to increment frameIndex at the end of each frame. The score variable disappears in the recursion. And because the code is so simple, there is no need to make a separate class, and thus no need for the roll function to allow the caller to update the private data of the class.

    Let’s step back for a minute. Uncle Bob’s version has 39 non-blank lines (29 if you don’t count lines containing only a closing brace), mine has 5. That’s six or eight times as much code, to perform the same task. Who wants to read that much code to perform such a simple task? Who wants to write that much code to perform such a simple task? Who wants to type that much code to perform a simple task?

    Imagine if a modest-sized program, say 1000 lines, suddenly became an 8000-line program. The poor programmer who inherits the maintenance of that program won’t know where to start reading. The additional complexity of all that code means that the programmer needs tools to manage it, so large programming environments are created, with all of their own complexity. Then you need design patterns to help you figure out what you are reading: is that visitor or singleton?

    And let’s consider ease of development. It took Uncle Bob five tries to develop his code and fifty slides to present his code; twice during development he comments that the design is wrong, so he has to throw out already-written code and try again. By contrast, it took me a single page to show the code, give a thorough explanation, and demonstrate its correctness; I wrote my function as quickly as I could type, and it worked correctly the first time I ran it.

    I am primarily a functional programmer, though I am not as dogmatic about it as some of my functional-programming friends. I suppose there is a case to be made for object-oriented programming, though it is highly unclear to me that the bowling game kata does that. But while I am waiting for someone to make that case, I’m perfectly content with my five-line solution.

  4. The code presented within the kata is intended to be quickly read and understood by a human. I assert with all possible conviction that a language such as English is more “readable” than an equivalent mathematical expression.

    All of the identifiers in his example basically express their use and/or meaning. Context is presented as you /read/ the code. An integer named “score” is very meaningful whereas that same variable named “x” is not. In a trivial example such as this that’s no problem, but in an enterprise-level application maintenance of such code is absolutely more difficult. I want to focus my attention on what your code is doing rather than how it does it.

    The tests that were performed in the kata aren’t unit tests. Your observation that they don’t fully or effectively test the system is absolutely correct. They’re called tests, they test the code, but they’re not tests in the sense that they were written to validate application behavior. Robert wrote those tests _before_ he wrote the code they tested. He was expressing in code the behavior that he wanted to implement next. This is a very good form of software documentation, it does accomplish a very basic level of testing, and the approach of implementing only the code that is necessary to satisfy our tests keeps code very simple without requiring a lot of consideration. Again, the focus is placed firmly on the problem at hand and its solution rather than the mechanics of implementing that solution.

    Code length is no measure of complexity. One line from the computer science text of your choice is certainly more “complex” than all of the language in an entire children’s book. All of the trivial one line methods that you dismiss in Robert’s code take a single concept and wrap it within a reusable identifier that expresses its meaning in English.

    I agree that the bowling kata is so simple that one can simply sit down and solve it in a few lines of code with little thought. That is not the point. This trivial exercise is presented alongside a process for solving it so that you can understand the process without getting buried in complex implementation details. TDD or even OOP in the context of a simple problem such as this is good for learning how to apply these methodologies but will never show you /why/ you might want to do so. For that, you’d need a much more complex application that you’re unlikely to be able to sit down and write in one session.

    Rather than dismissing Robert’s ideas by circumventing the exercise as it was presented, please consider really stepping back for a moment and trying to understand how this man thinks and works. Then, try to apply these principles to a real world problem. I’m not saying that you’ll absolutely come to accept test-driven development but at least then you’ll have an understanding of the subject matter on which to base your opinion.

  5. programmingpraxis said

    Steve Yegge seems to disagree with you: http://steve-yegge.blogspot.com/2007/12/codes-worst-enemy.html.

  6. Michael said

    I think your solution is a bit too simplistic. I bet it would fail a few test cases.

    In fact, here are two provided by Jon Bettinger that provide ambiguity in your first pattern match:

    0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,1,0 (A strike in the 10th frame should = 11)
    0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 1,0 (A strike in the 9th frame should = 12)

    Your solution will _not_ double count the last bowl in the 10th frame of the second test case.

    To fix this, you need to keep track of the frame number.

    Cheers,
    Michael

  7. Michael said

    Here’s a version that passes the tests (so far):

    class BowlByMapping {
    	def score(bowls:List[Int]) =
    		scoreFrames(bowls) sumFirst 10
    	
    	def scoreFrames(bowls:List[Int]):List[Int] = bowls match {
    		case Nil => List(0)
    		case isStrike() =>
    			bowls.sumFirst(3) :: scoreFrames(bowls drop 1)
    		case isSpare() =>
    			bowls.sumFirst(3) :: scoreFrames(bowls drop 2)
    		case _ =>
    			bowls.sumFirst(2) :: scoreFrames(bowls drop 2)
    	}
    	
    	object isStrike {
    		def unapply(bowls:List[Int]) = bowls match {
    			case 10::_ => true
    			case _ => false
    		}
    	}
    	
    	object isSpare {
    	    def unapply(bowls:List[Int]) = bowls match {
    		    case a::b::_ if a+b == 10 => true
    		    case _ => false
    		}
        }
    	
        class SumFirstN(val list:List[Int]) {
    	    def sumFirst(n:Int) = list.slice(0, n).sum
        }
        implicit def list2SumFirstN(list:List[Int]):SumFirstN = new SumFirstN(list)
    }
  8. Pascal said

    Andre, I really like your elegant solution to compute bowling score. But you do not offer us what Bob Martin does : how do you think when you are building this solution ? What are the detailed steps that you went through to construct this solution ? What case did you write first, and so on ?

  9. I don’t think what Yegge wrote in that article disagrees with Kyle W. Cartmell.

    For the most part what Yegge is describing is how unexpressive Java is. I code primarily in AS3 which is similarly weighed down. I suspect if you saw some of Bob Martin’s ruby code for the same Kata it would be significantly shorter and more expressive, and still considerably more readable than your functional example (especially when things scale, as Kyle suggests).

    When I code in other languages that are more expressive, such as ruby or scala, I can use the same approach but end up with much lighter code. However, because of other stakeholder requirements, Flex is a great win for us, so I do what I can with AS3 and utilise the efforts of Bob Martin and Martin Fowler to keep the mess to a minimum.

    You still need to utilise much of the same research in complex systems no matter what the language, or you end up with seriously unreadable code.

    Yegge also glosses past the fact that when crafted well, a huge codebase won’t hurt. It should be largely human readable and compartmentalized.

    Much as you might use IO or UI libraries without ever peaking inside them, a well written module can be as trustworthy and thus considered “Not a member of the set of classes upon which I am working”, even if it is in your codebase.

  10. Philip Schwarz said

    @Programming Praxis

    You wrote: To my mind, my code is far more readable. It’s not cluttered with all those extraneous functions isSpare, isStrike, spareBonus, strikeBonus, and sumOfBallsInFrame; such simple one-liners could easily be moved into the place where they are called.

    Experienced people usually take the opposite view: http://programmingtour.blogspot.com/2010/12/taking-it-too-far-v-taking-too-much.html

  11. Markus said

    let rec bowling = function
    | 10 :: y :: z :: xs -> 10 + y + z + bowling (y :: z :: xs)
    | x :: y :: z :: xs when x + y = 10 -> 10 + z + bowling (z :: xs)
    | x :: y :: xs -> x + y + bowling xs
    | _ -> 0

  12. Francis Monkman said

    The original is nonsense – did anyone ever try testing it? You can see the basic problem from the last page, the ‘Fifth test’. Look at the calls to rollMany(rolls, pins) – the first two are making 20 calls, the next is making 22 (!! – writing zeros past the end of the array of 21), the next 24, then suddenly the new blue one is making *12*, in other words, without warning, we are to assume that strikes are (correctly) registered as two rolls -and that’s the point. You need (sorry we’re in C++ now):

    void Game::roll(int pins) {
    rolls[currentRoll++] = pins;
    if (pins == 10) currentRoll++; // must increment by two for a strike! Ugly or not!!!
    }

    then, you need to work out your indexing, get it right (!?!?!), and simplify:

    int Game::score() {

    int s = 0, f2 = 0;

    for (int frame = 0; frame < 10; frame++) {

    if (isStrike(f2)) { s += 10 + strikeBonus(f2); }
    else if (isSpare(f2)) { s += 10 + spareBonus(f2); }
    else s += sumOfBallsInFrame(f2);

    f2 += 2;
    }

    return s;
    }

    …and then, you need to check your lookaheads in case the first one is itself a strike, eg.

    int strikeBonus(int f2) { return rolls[f2 + 2] + rolls[f2 + !isStrike(f2 + 2)? 3 : 4]; }

    and that (finally, I admit) worked for me – all the tests (in 'main' :) ) correct, and for my final test
    I input the values from Uncle Bob's own diagram, and it indeed works out at 133.

    You know, I can see the point in this kind of coding, which is why I've been banging my head
    against this thing — but what's the point of doing it if the code doesn't even work, like not at all?
    Rant over…

  13. Francis Monkman said

    Please forgive the above rant. Sincerest apologies, I think it was the
    “return -1 oops” that got to me…
    Apart from that, I was the one writing past the array end *duh*…

    As penance (using the original algorithm) I made the roll() function
    return a bool, true when game over. Assuming a game object g,

    while(!g->roll(input)); // loop until game done, input from keyboard or file
    score = g->score();

    (thinking my previous ‘bee in bonnet’ idea might be used for database purposes,
    when immediate access to individual frame scores could be useful for stats etc,
    I recoded it as well, noting the final frame’s entries need to be consecutive.)

    Then, I had a thought — a roll() that returns game over needs to be able to
    distinguish between first and second rolls of a frame, so that a ‘rolls left’
    counter only decrements by two when there’s a real strike (because a player
    can score a 10 on the second roll, having scored zero on the first roll).

    This was even messier so I returned to my ‘frame-aligned’ version.

    class Game {

    public:
    bool roll(int);
    int score();
    // void newGame(); // reset if needed

    private:
    int rolls[21];
    int thisRoll;

    bool isStrike(int r) { return rolls[r] == 10; }
    bool isSpare(int r) { return rolls[r]+rolls[r+1] == 10; }

    int strikeBonus(int r) {
    if (r == 18) return rolls[19] + rolls[20]; // kluge for last frame
    else return rolls[r+2] + rolls[r + (isStrike(r+2)? 4 : 3)];
    }
    int spareBonus(int r) { return rolls[r+2]; }

    int sumOfBallsInFrame(int r) { return rolls[r] + rolls[r+1]; }
    };

    //void Game::newGame() { for(int x=0;x<21;x++) rolls[x]=0; thisRoll = 0; }

    bool Game::roll(int pins) {

    rolls[thisRoll++] = pins;

    if (pins == 10 && (thisRoll & 1) // true strike only on new frame
    && thisRoll < 18) thisRoll++; // but squash tenth frame anyway

    if (thisRoll == 20) // second ball of last frame? add frame contents,
    return (rolls[18]+rolls[19] < 10)? true: false; // done if 20) return true; // we did the extra one

    else return false;
    }

    int Game::score() {

    int s = 0, r = 0; // score, roll index

    for (int frame = 0; frame < 10; frame++) {

    if (isStrike(r)) { s += (10+strikeBonus(r)); }
    else if (isSpare(r)) { s += (10+spareBonus(r)); }
    else s += sumOfBallsInFrame(r);

    r += (frame == 9)? 1 : 2; // last frame consecutive regardless
    }
    return s;
    }

    …which works with the tests given, and the diagram with as many variations as
    I could think of. The game over flag seems to work okay. Hope this is of some use!

    Again, please accept my sincere apologies (and to Uncle Bob, except for the -1)!

  14. Graeme Moss said

    I wanted to try to combine the brevity of the Haskell solution with the readability of the Java solution (that is, readable by others). Here’s my best attempt so far. I’m interested in others’ opinions.

    score rolls = score' 1 rolls
    score' frame rolls = scoreThisFrame + scoreRemainingFrames
      where scoreThisFrame
              | isStrike  = 10 + sum (take 2 remainingRolls)
              | isSpare   = 10 + head remainingRolls
              | otherwise = sum (take 2 rolls)
            scoreRemainingFrames
              | isLastFrame = 0
              | otherwise   = score' (frame + 1) remainingRolls
            remainingRolls
              | isStrike  = tail rolls
              | otherwise = drop 2 rolls
            isLastFrame = frame == 10
            isStrike = head rolls == 10
            isSpare = sum (take 2 rolls) == 10
    

    This code is much longer than Andre’s (which might need a line or so to count the frames to fix the bug raised by Michael) but in my opinion easier to understand by someone who did not write the code, especially if you decide to avoid using comments in the code (on the assumption they easily get out of date).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: