28 May 2012

Variations on a Bowling Scorer

Instead of writing a lot about programming as I usually do, this post is made up mainly of code. The background story is that I was terribly offended by a piece of code I found on the web. So I rewrote it, documenting my process and design decisions on the side. I was very happy with the resulting code I got, but never had the time to rewrite the process and design description for publishing. My code, however, is always written to be readable for anybody, so I am publishing it here without any comments.

You'll probably notice that the code which offended me is very clean on the surface (after all, it's written by Mr. Clean Code himself!), but what bugged me was the design of the program and the tight coupling of methods by shared variables. In fact, the coding style reminded me a lot of programs written in C. (A higher-level machine language from the 70s, for those who don't know it.)

Here's Uncle Bob's solution; copied from his long post where he and a coworker derive it TDD style. (Code-highlighting on Blogger seems really hard to do, so for the moment, I need to feed you black and white code. Sorry for that!) Don't worry about the actual purpose of the code. If you want to learn the rules of bowling scoring, you can read them from the declarative program given below!

//Game.java----------------------------------
public class Game
{
  public int score()
  {
    return scoreForFrame(itsCurrentFrame);
  }

  public void add(int pins)
  {
    itsScorer.addThrow(pins);
    adjustCurrentFrame(pins);
  }

  private void adjustCurrentFrame(int pins)
  {
    if (firstThrowInFrame == true)
    {
      if (adjustFrameForStrike(pins) == false)
        firstThrowInFrame = false;
    }
    else
    {
      firstThrowInFrame=true;
      advanceFrame();
    }
  }

  private boolean adjustFrameForStrike(int pins)
  {
    if (pins == 10)
    {
      advanceFrame();
      return true;
    }
    return false;
  }  

  private void advanceFrame()
  {
    itsCurrentFrame = Math.min(10, itsCurrentFrame + 1);
  }

  public int scoreForFrame(int theFrame)
  {
    return itsScorer.scoreForFrame(theFrame);
  }

  private int itsCurrentFrame = 0;
  private boolean firstThrowInFrame = true;
  private Scorer itsScorer = new Scorer();
}

//Scorer.java-----------------------------------
public class Scorer
{
  public void addThrow(int pins)
  {
    itsThrows[itsCurrentThrow++] = pins;
  }

  public int scoreForFrame(int theFrame)
  {
    ball = 0;
    int score=0;
    for (int currentFrame = 0; 
         currentFrame < theFrame; 
         currentFrame++)
    {
      if (strike())
        score += 10 + nextTwoBalls();
      else if (spare())
        score += 10 + nextBall();
      else
        score += twoBallsInFrame();
    }

    return score;
  }

  private boolean strike()
  {
    if (itsThrows[ball] == 10)
    {
      ball++;
      return true;
    }
    return false;
  }

  private boolean spare()
  {
    if ((itsThrows[ball] + itsThrows[ball+1]) == 10)
    {
      ball += 2;
      return true;
    }
    return false;
  }

  private int nextTwoBalls()
  {
    return itsThrows[ball] + itsThrows[ball+1];
  }

  private int nextBall()
  {
    return itsThrows[ball];
  }

  private int twoBallsInFrame()
  {
    return itsThrows[ball++] + itsThrows[ball++];
  }

  private int ball;
  private int[] itsThrows = new int[21];
  private int itsCurrentThrow = 0;
}
Since I felt that mutable variables shouldn't be necessary in the solution at all, I first produced a solution in a purely functional programming language. Here's my solution in Haskell:
example_throws_incomplete = [1,2,3,4,10,10,1,2,3]

to_frames :: [Int] -> [([Int], [Int])]
to_frames (10:xs)  = ([10], xs) : to_frames xs
to_frames (x:y:xs) = ([x,y], xs) : to_frames xs
to_frames _        = []   -- covers empty lists and trailing bonus throws

test_to_frames = assert_equals (map fst $ to_frames example_throws_incomplete)
          [[1,2],[3,4],[10],[10],[1,2]]

-- how many bonus throws are counted into a frame?
num_bonus [10]               = 2
num_bonus [a, b] | a+b == 10 = 1
num_bonus _                  = 0

-- scoring a frame is really simple:
score_frame (frame_throws, next_throws) = sum frame_throws + sum bonus_throws
     where 
     bonus_throws = take (num_bonus frame) next_throws

-- the straight-forward solution assumes that all the bonus throws are present
score_complete_game throws = scanl1 (+) $ map score_frame $ take 10 $ to_frames throws

assert_equals a b | a == b    = "ok"
                  | otherwise = "expected: " ++ show a ++ "\n"
                             ++ "but got: " ++ show b

Given how easy that was, we now have a clear picture of the solution algorithm and design which we only need to port to Java. It's not exactly I one-to-one port, but you'll recognize the spirit of the algorithm.
Here's the code:
import java.util.List;

public class BowlingScorer {
  static class Frame {
    static final public Frame firstFrame(List throwns) {
      return new Frame(throwns, 1, 0, 0);
    }
    public Frame nextFrame() {
      return new Frame(throwns, number+1, nextPosition(), score());
    }
    public int number() {
      return number;
    }
    public int score() {
      return score;
    }
    public boolean isStrike() {
      return throwns.get(position) == 10;
    }
    public boolean isSpare() {
      return ! isStrike() && throwsScore() == 10;
    }
    public int numThrows() {
      return isStrike() ? 1 : 2;
    }
    public int numBonus() {
      return isStrike() ? 2 : isSpare() ? 1 : 0;
    }
    private int nextPosition() {
      return position + numThrows();
    }
    private int throwsScore() {
      return sumThrowns(position, numThrows());
    }
    private int bonusScore() {
      return sumThrowns(nextPosition(), numBonus());
    }
    private int sumThrowns(int start, int count){
      int result = 0;
      for (int i = start; i < start+count; i++) {
        result += throwns.get(i);
      }
      return result;
    }
    private final List throwns;
    private final int number; // number of frame in game, counting from 1
    private final int position; // this frame's first throw in throwns
    private final int score;
    private Frame(List throwns, int number, int position, int previousScore) {
      this.throwns = throwns;
      this.number = number;      
      this.position = position;
      this.score = previousScore + throwsScore() + bonusScore();
    }
  }
  public int finalScore(List throwns) {
    return getFrame(throwns, 10).score();
  }
  private Frame getFrame(List throwns, int number) {
    // requiresThat(number, atLeast(1));
    // requiresThat(number, atMost(10));
    Frame f = Frame.firstFrame(throwns);
    while (f.number() < number) {
      f = f.nextFrame();
    }
    return f;
  }
  /*
  private static void requiresThat(T thing, Matcher matcher) {
    if (! matcher.matches(thing)) {
      throw new IllegalArgumentException(matcher.reason());
    }
  }  
  */
}
Before start giving a lecture on why my program is better, I'll just let you read and find your own opinion. If you want some more food for thought, try to find the one concern that Uncle Bob's solution treats in two different places in two different ways without explicitly mentioning it as a concern. (Had they found the pattern and named it, they'd probably tried to solve it in one place only.)

If you don't have the time to study the code in detail, at least have a look at that one line in Frame(..) which says:  this.score = previousScore + throwsScore() + bonusScore(); I think that this is as close as we get to formulating a really direct and concise specification of the score of a frame. 


Finally, sorry for improvising some of the Matcher / Assertion stuff as I don't have all the proper tools installed right now.

0 comments:

Post a Comment