Bowling Again

It’s been a while since I’ve done the bowling game scoring exercise. For those of you who don’t know it, the bowling game (ten-pin) is almost the Hello, world! of TDD. I want to learn Groovy, but I’m going to re-do it in Java first, so that I have recent code and feelings to compare when I sink my teeth in Groovy.

Here’s the goal for this exercise: write a program that can score a bowling game. Inputs are the rolls, output the score.

The first thing to note is that the inputs are rolls (number of pins knocked down), while the score depends on frames. A frame consists of up to two rolls: if the first roll knocks all 10 pins down, then we’re talking about a strike and the frame consist of just the one roll. Otherwise, the frame consists of two rolls. If the second roll knocks down all pins, the frame is called a spare, else it’s a regular frame. The only exception is the last frame. If that is a strike or a spare, it will consist of three rolls. We call those bonus frames.

Frames

So our first task is to distinguish the several types of frames. Let’s start simple, with a regular frame:

public class RegularFrameTest {

  @Test
  public void frame() {
    final Frame frame = new RegularFrame(2, 5);
    Assert.assertEquals("# rolls", 2, frame.numRolls());
    Assert.assertEquals("First", 2, frame.pins(0));
    Assert.assertEquals("Second", 5, frame.pins(1));
  }

}

This forces me to write the Frame interface:

public interface Frame {

  int numRolls();
  int pins(int index);

}

The implementation is straightforward:

public class RegularFrame implements Frame {

  private final int first;
  private final int second;

  public RegularFrame(final int first, final int second) {
    this.first = first;
    this.second = second;
  }

  @Override
  public int numRolls() {
    return 2;
  }

  @Override
  public int pins(final int index) {
    return index == 0 ? first : second;
  }

}

Now, let’s do a spare:

public class SpareTest {

  @Test
  public void frame() {
    final Frame frame = new Spare(3);
    Assert.assertEquals("# rolls", 2, frame.numRolls());
    Assert.assertEquals("First", 3, frame.pins(0));
    Assert.assertEquals("Second", 7, frame.pins(1));
  }

}

Again, pretty easy:

public class Spare implements Frame {

  private final int first;

  public Spare(final int first) {
    this.first = first;
  }

  @Override
  public int numRolls() {
    return 2;
  }

  @Override
  public int pins(final int index) {
    return index == 0 ? first : 10 - first;
  }

}

OK, so by now, strike should be familiar territory:

public class StrikeTest {

  @Test
  public void frame() {
    final Frame frame = new Strike();
    Assert.assertEquals("# rolls", 1, frame.numRolls());
    Assert.assertEquals("first", 10, frame.pins(0));
  }

}

public class Strike implements Frame {

  @Override
  public int numRolls() {
    return 1;
  }

  @Override
  public int pins(final int index) {
    return 10;
  }

}

And finally, the bonus frame:

public class BonusFrameTest {

  @Test
  public void frame() {
    final Frame frame = new BonusFrame(10, 3, 5);
    Assert.assertEquals("# rolls", 3, frame.numRolls());
    Assert.assertEquals("first", 10, frame.pins(0));
    Assert.assertEquals("second", 3, frame.pins(1));
    Assert.assertEquals("third", 5, frame.pins(2));
  }

}

public class BonusFrame implements Frame {

  private final int first;
  private final int second;
  private final int third;

  public BonusFrame(final int first, final int second, final int third) {
    this.first = first;
    this.second = second;
    this.third = third;
  }

  @Override
  public int numRolls() {
    return 3;
  }

  @Override
  public int pins(final int index) {
    switch (index) {
      case 0: return first;
      case 1: return second;
      default: return third;
    }
  }

}

Note that I never bothered to specify what pins should return for an invalid index.

Now, there is a lot of duplication in these classes, so let’s extract a common base class. First, I’m going to focus on BonusFrame, since that one has the most code.

I’m going to take baby steps, keeping the code green as much as possible. First, I introduce a list to hold the three separate values:

public class BonusFrame implements Frame {

  private final List<Integer> pins = new ArrayList<Integer>();

  public BonusFrame(final int first, final int second, final int third) {
    this.first = first;
    this.second = second;
    this.third = third;
    pins.add(first);
    pins.add(second);
    pins.add(third);
  }

  // ...
}

Next, I implement numRolls using the new list:

public class BonusFrame implements Frame {

  @Override
  public int numRolls() {
    return pins.size();
  }

  // ...
}

Then the pins method:

public class BonusFrame implements Frame {

  @Override
  public int pins(final int index) {
    return pins.get(index);
  }

  // ...
}

Now the original fields are unused, and I can delete them safely. Never in this refactoring did I break the tests, not even for a second.

The second stage of this refactoring is to extract a base class that will hold the list of pins. Since the constructor is using the fields, I need to change it slightly, so that I can safely move the list. First I’ll introduce a new constructor that accepts a list of pins:

public class BonusFrame implements Frame {

  protected BonusFrame(final List<Integer> pins) {
    this.pins.addAll(pins);
  }

  // ..
}

Then I change the original constructor to call the new one:

public class BonusFrame implements Frame {

  public BonusFrame(final int first, final int second, final int third) {
    this(Arrays.asList(first, second, third));
  }

  // ...
}

Now I can do an automated Extract Superclass refactoring to get my coveted base class:

public class BonusFrame extends BaseFrame implements Frame {

  public BonusFrame(final int first, final int second, final int third) {
    this(Arrays.asList(first, second, third));
  }

  protected BonusFrame(final List<Integer> pins) {
    this.pins.addAll(pins);
  }

}

Unfortunately, there is no way to have Eclipse also move the constructor that I had prepared 😦 Also, the BaseFrame class doesn’t implement Frame yet:

public class BaseFrame {

  protected final List<Integer> pins = new ArrayList<Integer>();

  public BaseFrame() {
    super();
  }

  @Override
  public int numRolls() {
    return pins.size();
  }

  @Override
  public int pins(final int index) {
    return pins.get(index);
  }

}

This is bad, since now the code doesn’t even compile anymore, thanks to the @Override! Let’s add the missing implements, so we’re back to green. The public no-arg constructor can also go, it will be generated for us.

Now to clean up the mess. Eclipse doesn’t offer to Pull Up constructors, which is a shame. So let’s move it by hand:

public class BonusFrame extends BaseFrame implements Frame {

  public BonusFrame(final int first, final int second, final int third) {
    super(Arrays.asList(first, second, third));
  }

}

public class BaseFrame implements Frame {

  protected BaseFrame(final List<Integer> pins) {
    this.pins.addAll(pins);
  }

  // ...
}

The list should be private, and the implements Frame on BonusFrame can go.

We can now use BaseFrame as a base class for the other classes as wel:

public class Strike extends BaseFrame {

  public Strike() {
    super(Arrays.asList(10));
  }

}

public class Spare extends BaseFrame {

  public Spare(final int first) {
    super(Arrays.asList(first, 10 - first));
  }

}

public class RegularFrame extends BaseFrame {

  public RegularFrame(final int first, final int second) {
    super(Arrays.asList(first, second));
  }

}

I’m happy with the result, so let’s move on.

From Rolls To Frames

Now that we have the different kinds of frames in place, we need a way to create them from the rolls that are our input. We basically need to convert a series of rolls into a series of frames. This series idea we can capture in an Iterator:

public class FrameIteratorTest {

  @Test
  public void regular() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(1, 2));
    Assert.assertTrue("Missing frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Frame", new RegularFrame(1, 2), frame);
    Assert.assertFalse("Extra frame", frames.hasNext());
  }

}

But for this to work, we need to implement equals on BaseFrame:

public class BaseFrameTest {

  @Test
  public void equality() {
    final Frame frame1 = new BaseFrame(Arrays.asList(4, 2));
    Assert.assertTrue("Same", frame1.equals(new BaseFrame(Arrays.asList(4, 2))));
    Assert.assertFalse("Different", frame1.equals(new BaseFrame(Arrays.asList(2, 4))));
  }

}

This is easy to implement, since Eclipse can generate the equals and hashCode for us:

public class BaseFrame implements Frame {

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((pins == null) ? 0 : pins.hashCode());
    return result;
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final BaseFrame other = (BaseFrame) obj;
    if (pins == null) {
      if (other.pins != null) {
        return false;
      }
    } else if (!pins.equals(other.pins)) {
      return false;
    }
    return true;
  }

  // ...
}

Now we can return to our FrameIterator:

public class FrameIterator implements Iterator<Frame> {

  private final Iterator<Integer> rolls;

  public FrameIterator(final List<Integer> rolls) {
    this.rolls = rolls.iterator();
  }

  @Override
  public boolean hasNext() {
    return rolls.hasNext();
  }

  @Override
  public Frame next() {
    final int first = rolls.next();
    final int second = rolls.next();
    return new RegularFrame(first, second);
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }

}

OK, so how about a spare?

public class FrameIteratorTest {

  @Test
  public void spare() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(8, 2));
    Assert.assertTrue("Missing frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Frame", new Spare(8), frame);
  }

  // ...
}

public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    final int first = rolls.next();
    final int second = rolls.next();
    final Frame result;
    if (first + second == 10) {
      result = new Spare(first);
    } else {
      result = new RegularFrame(first, second);
    }
    return result;
  }

  // ...
}

OK, then a strike shouldn’t be too hard:

public class FrameIteratorTest {

  @Test
  public void strike() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(10));
    Assert.assertTrue("Missing frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Frame", new Strike(), frame);
  }

  // ...
}

This test doesn’t just fail, but it throws a NoSuchElementException, since we only provide one roll. Not too hard to fix, though:

public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    final Frame result;
    final int first = rolls.next();
    if (first == 10) {
      result = new Strike();
    } else {
      final int second = rolls.next();
      if (first + second == 10) {
        result = new Spare(first);
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  // ...
}

OK, that works, but the code is a bit messy. Not only do we have a magic constant, we now have it in two places! So let’s get rid of that:

public class FrameIterator implements Iterator<Frame> {

  private static final int PINS_PER_LANE = 10;

  @Override
  public Frame next() {
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      result = new Strike();
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        result = new Spare(first);
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  private boolean isAllDown(final int pins) {
    return pins == PINS_PER_LANE;
  }

  // ...
}

I’m still not all that happy with this code, although I guess it does state the rules quite clearly now. Maybe the messyness of the code follows the messyness of the rules? I dont know, so let’s let our background processor think that over some more while I continue.

We now have all the normal frames in place, but we still lack the bonus frames. First a spare:

public class FrameIteratorTest {

  @Test
  public void bonusSpare() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(10, 10, 10, 10, 10, 10, 10, 10, 10, 2, 8, 3));
    for (int i = 0; i < 9; i++) {
      Assert.assertTrue("Missing frame " + i, frames.hasNext());

      final Frame frame = frames.next();
      Assert.assertEquals("Frame " + i, new Strike(), frame);
    }

    Assert.assertTrue("Missing bonus frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Bonus frame", new BonusFrame(2, 8, 3), frame);
  }

  // ...
}

public class FrameIterator implements Iterator<Frame> {

  private static final int NUM_FRAMES_PER_GAME = 10;

  private int numFrames;

  @Override
  public Frame next() {
    numFrames++;
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      result = new Strike();
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        if (isFinalFrame()) {
          result = new BonusFrame(first, second, rolls.next());
        } else {
          result = new Spare(first);
        }
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  private boolean isFinalFrame() {
    return numFrames == NUM_FRAMES_PER_GAME;
  }

  // ...
}

And then the strike:

public class FrameIteratorTest {

  @Test
  public void bonusStrike() {
    final Iterator<Frame> frames = new FrameIterator(Arrays.asList(10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 7, 2));
    for (int i = 0; i < 9; i++) {
      Assert.assertTrue("Missing frame " + i, frames.hasNext());

      final Frame frame = frames.next();
      Assert.assertEquals("Frame " + i, new Strike(), frame);
    }

    Assert.assertTrue("Missing bonus frame", frames.hasNext());

    final Frame frame = frames.next();
    Assert.assertEquals("Bonus frame", new BonusFrame(10, 7, 2), frame);
  }

  // ...
}

public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    numFrames++;
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      if (isFinalFrame()) {
        final int second = rolls.next();
        result = new BonusFrame(first, second, rolls.next());
      } else {
        result = new Strike();
      }
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        if (isFinalFrame()) {
          result = new BonusFrame(first, second, rolls.next());
        } else {
          result = new Spare(first);
        }
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  // ...
}

OK, now we really have to simplify the code! Let’s extract all the strike and spare stuff:

public class FrameIterator implements Iterator<Frame> {

  @Override
  public Frame next() {
    numFrames++;
    final Frame result;
    final int first = rolls.next();
    if (isAllDown(first)) {
      result = newStrike(first);
    } else {
      final int second = rolls.next();
      if (isAllDown(first + second)) {
        result = newSpare(first, second);
      } else {
        result = new RegularFrame(first, second);
      }
    }
    return result;
  }

  private Frame newStrike(final int first) {
    final Frame result;
    if (isFinalFrame()) {
      final int second = rolls.next();
      result = new BonusFrame(first, second, rolls.next());
    } else {
      result = new Strike();
    }
    return result;
  }

  private Frame newSpare(final int first, final int second) {
    final Frame result;
    if (isFinalFrame()) {
      result = new BonusFrame(first, second, rolls.next());
    } else {
      result = new Spare(first);
    }
    return result;
  }

  // ...
}

I think I could further simplify the code by refactoring to a Strategy pattern and then do a Replace Conditional With Polymorphism to get rid of all those pesky if statements. But although that would make the individual methods easier to read, we would lose the overview, and it may just make the rules harder to retrieve from the code. So, I’m inclined to leave it as it is.

On to scoring then!

Scoring

This is where the fun begins.

The basic score for a frame is just the number of pins that were knocked down:

public class BaseFrameTest {

  @Test
  public void baseScore() {
    final Frame frame = new BaseFrame(Arrays.asList(3, 6));
    Assert.assertEquals("Base score", 9, frame.getBaseScore());
  }

  // ...
}

public interface Frame {

  int getBaseScore();

  // ...
}

public class BaseFrame implements Frame {

  @Override
  public int getBaseScore() {
    int result = 0;
    for (final int pins : this.pins) {
      result += pins;
    }
    return result;
  }

  // ...
}

Writing that only now makes me realize that I named the list of rolls pins. But it’s not the pins knocked down, but the list of pins per roll that were knocked down:

public class BaseFrame implements Frame {

  private final List<Integer> rolls = new ArrayList<Integer>();

  protected BaseFrame(final List<Integer> rolls) {
    this.rolls.addAll(rolls);
  }

  @Override
  public int numRolls() {
    return rolls.size();
  }

  @Override
  public int pins(final int index) {
    return rolls.get(index);
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((rolls == null) ? 0 : rolls.hashCode());
    return result;
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final BaseFrame other = (BaseFrame) obj;
    if (rolls == null) {
      if (other.rolls != null) {
        return false;
      }
    } else if (!rolls.equals(other.rolls)) {
      return false;
    }
    return true;
  }

  @Override
  public int getBaseScore() {
    int result = 0;
    for (final int pins : rolls) {
      result += pins;
    }
    return result;
  }

}

Now, that was the easy part of scoring. Apart from the base score, strikes and spares also have extra scores. We don’t want to deal with exceptions, though. That will just lead to code littered with if statements. Instead, we can use polymorphism and the Null Object pattern:

public class BaseFrameTest {

  @Test
  public void extraScore() {
    final Frame frame = new BaseFrame(Arrays.asList(3, 4));
    Assert.assertTrue("Extra score", frame.getExtraScore() instanceof NoExtraScore);
  }

  // ...
}

public interface Frame {

  ExtraScore getExtraScore();

  // ...
}

public interface ExtraScore {

}

public class NoExtraScore implements ExtraScore {

}

Note that the ExtraScore interface is empty for now. We will get to that in a minute. First let’s make the test pass:

public class BaseFrame implements Frame {

  @Override
  public ExtraScore getExtraScore() {
    return new NoExtraScore();
  }

  // ...
}

For spares, the extra score is one roll:

public class SpareTest {

  @Test
  public void extraScore() {
    final Frame frame = new Spare(4);
    Assert.assertTrue("Extra score", frame.getExtraScore() instanceof OneRollExtraScore);
  }

  // ...
}

public class OneRollExtraScore implements ExtraScore {

}

public class Spare extends BaseFrame {

  @Override
  public ExtraScore getExtraScore() {
    return new OneRollExtraScore();
  }

  // ...
}

For strikes, the extra score is two rolls:

public class StrikeTest {

  @Test
  public void extraScore() {
    final Frame frame = new Strike();
    Assert.assertTrue("Extra score", frame.getExtraScore() instanceof TwoRollsExtraScore);
  }

  // ...
}

public class TwoRollsExtraScore implements ExtraScore {

}

public class Strike extends BaseFrame {

  @Override
  public ExtraScore getExtraScore() {
    return new TwoRollsExtraScore();
  }

  // ...
}

Allright, what about that ExtraScore interface? We don’t want to go back to dealing with rolls, since we have our lovely FrameIterator that gives us frames. So the extra score must deal with frames. First, it must tells us whether it needs any at all:

public class NoExtraScoreTest {

  @Test
  public void needFrame() {
    final ExtraScore extraScore = new NoExtraScore();
    Assert.assertFalse("Need more", extraScore.needFrame());
  }

}

public interface ExtraScore {

  boolean needFrame();

}

public class NoExtraScore implements ExtraScore {

  @Override
  public boolean needFrame() {
    return false;
  }

}

We have a little bit more work for the one roll extra score:

public class OneRollExtraScoreTest {

  @Test
  public void extraScore() {
    final ExtraScore extraScore = new OneRollExtraScore();
    Assert.assertTrue("Need more", extraScore.needFrame());

    final Frame frame = new RegularFrame(3, 4);
    final int score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score", 3, score);
    Assert.assertFalse("Need still more", extraScore.needFrame());
  }

}

public interface ExtraScore {

  int getScore(Frame frame);

  // ...
}

public class OneRollExtraScore implements ExtraScore {

  private boolean needMore = true;

  @Override
  public boolean needFrame() {
    return needMore;
  }

  @Override
  public int getScore(final Frame frame) {
    needMore = false;
    return frame.pins(0);
  }

}

And the extra score for a strike is the most complex:

public class TwoRollsExtraScoreTest {

  @Test
  public void regular() {
    final ExtraScore extraScore = new TwoRollsExtraScore();
    Assert.assertTrue("Need more", extraScore.needFrame());

    final Frame frame = new RegularFrame(6, 3);
    final int score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score", 9, score);
    Assert.assertFalse("Still need more", extraScore.needFrame());
  }

  @Test
  public void strike() {
    final ExtraScore extraScore = new TwoRollsExtraScore();
    Assert.assertTrue("Need more", extraScore.needFrame());

    Frame frame = new Strike();
    int score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score", 10, score);
    Assert.assertTrue("Still need more", extraScore.needFrame());

    frame = new RegularFrame(6, 3);
    score = extraScore.getScore(frame);
    Assert.assertEquals("Extra score 2", 6, score);
    Assert.assertFalse("Still need more 2", extraScore.needFrame());
  }

}

public class TwoRollsExtraScore implements ExtraScore {

  private int numNeeded = 2;

  @Override
  public boolean needFrame() {
    return numNeeded > 0;
  }

  @Override
  public int getScore(final Frame frame) {
    int result = 0;
    final int numGotten = Math.min(numNeeded, frame.numRolls());
    for (int i = 0; i < numGotten; i++) {
      result += frame.pins(i);
    }
    numNeeded -= numGotten;
    return result;
  }

}

Now we need to glue all the previous together to calculate the game’s score:

public class FramesScorerTest {

  @Test
  public void score() {
    final FramesScorer scorer = new FramesScorer();
    Frame frame = new FakeFrame(2);
    scorer.add(frame);
    Assert.assertEquals("Score", 9, scorer.getScore());

    List<ExtraScore> extraScores = scorer.getExtraScores();
    Assert.assertNotNull("Missing extra scores", extraScores);
    Assert.assertEquals("# Extra scores", 1, extraScores.size());
    Assert.assertTrue("Extra score", extraScores.get(0) instanceof FakeExtraScore);

    frame = new FakeFrame(1);
    scorer.add(frame);
    Assert.assertEquals("Score 2", 19, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 2", 2, extraScores.size());

    frame = new FakeFrame(0);
    scorer.add(frame);
    Assert.assertEquals("Score 3", 30, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 3", 3, extraScores.size());

    scorer.add(frame);
    Assert.assertEquals("Score 4", 41, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 4", 3, extraScores.size());
  }


  private static class FakeFrame extends BaseFrame {

    protected FakeFrame(final int pins) {
      super(Arrays.asList(pins, 9 - pins));
    }

    @Override
    public ExtraScore getExtraScore() {
      return new FakeExtraScore(pins(0));
    }

  }


  private static class FakeExtraScore implements ExtraScore {

    private final int numNeeded;

    public FakeExtraScore(final int numNeeds) {
      numNeeded = numNeeds;
    }

    @Override
    public boolean needFrame() {
      return numNeeded  > 0;
    }

    @Override
    public int getScore(final Frame frame) {
      return 1;
    }

  }

}

This test is a lot more involved than normal, and it took some time to get it right. This is because it’s really the sequence of steps that we want to test, as all the individual steps are already tested.

Let’s implement this assert by assert. First, the base score:

public class FramesScorer {

  private int score;

  public void add(final Frame frame) {
    score += frame.getBaseScore();
  }

  public int getScore() {
    return score;
  }

  public List<ExtraScore> getExtraScores() {
    return null;
  }

}

Next, we need to remember the extra score object:

public class FramesScorer {

  private final List<ExtraScore> extraScores = new ArrayList<ExtraScore>();

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    extraScores.add(frame.getExtraScore());
  }

  public List<ExtraScore> getExtraScores() {
    return extraScores;
  }

  // ...
}

Then we need to add the collected extra scores:

public class FramesScorer {

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      score += extraScore.getScore(frame);
    }
    extraScores.add(frame.getExtraScore());
  }

  // ...
}

And we must not forget to remove extra scores that are done:

public class FramesScorer {

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      if (extraScore.needFrame()) {
        score += extraScore.getScore(frame);
      } else {
        iterator.remove();
      }
    }
    extraScores.add(frame.getExtraScore());
  }

  // ...
}

Actually, the way I implemented this puts the ExtraScore object on the list even if it is a NoExtraScore object, which seems a bit wasteful. So let’s fix that:

public class FramesScorerTest {

  @Test
  public void score() {
    final FramesScorer scorer = new FramesScorer();
    Frame frame = new FakeFrame(2);
    scorer.add(frame);
    Assert.assertEquals("Score", 9, scorer.getScore());

    List<ExtraScore> extraScores = scorer.getExtraScores();
    Assert.assertNotNull("Missing extra scores", extraScores);
    Assert.assertEquals("# Extra scores", 1, extraScores.size());
    Assert.assertTrue("Extra score", extraScores.get(0) instanceof FakeExtraScore);

    frame = new FakeFrame(1);
    scorer.add(frame);
    Assert.assertEquals("Score 2", 19, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 2", 2, extraScores.size());

    frame = new FakeFrame(0);
    scorer.add(frame);
    Assert.assertEquals("Score 3", 30, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 3", 2, extraScores.size());

    scorer.add(frame);
    Assert.assertEquals("Score 4", 41, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 4", 2, extraScores.size());
  }

  // ...
}

public class FramesScorer {

  public void add(final Frame frame) {
    score += frame.getBaseScore();
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      score += extraScore.getScore(frame);
      if (!extraScore.needFrame()) {
        iterator.remove();
      }
    }

    final ExtraScore extraScore = frame.getExtraScore();
    if (extraScore.needFrame()) {
      extraScores.add(extraScore);
    }
  }

  //  ...
}

Now we need to clean this up a bit:

public class FramesScorer {

  private int score;
  private final List<ExtraScore> extraScores = new ArrayList<ExtraScore>();

  public void add(final Frame frame) {
    score += frame.getBaseScore() + extraScore(frame);
    rememberExtraScore(frame);
  }

  private int extraScore(final Frame frame) {
    int result = 0;
    final Iterator<ExtraScore> iterator = extraScores.listIterator();
    while (iterator.hasNext()) {
      final ExtraScore extraScore = iterator.next();
      result += extraScore.getScore(frame);
      if (!extraScore.needFrame()) {
        iterator.remove();
      }
    }
    return result;
  }

  private void rememberExtraScore(final Frame frame) {
    final ExtraScore extraScore = frame.getExtraScore();
    if (extraScore.needFrame()) {
      extraScores.add(extraScore);
    }
  }

  // ...
}

All that’s left to do, is collect the rolls and provide them to the scorer. First the collecting:

public class GameTest {

  @Test
  public void rolls() {
    final Game game = new Game();
    game.roll(3);
    game.roll(1);
    game.roll(3);
    Assert.assertEquals("Rolls", Arrays.asList(3, 1, 3), game.getRolls());
  }

}

public class Game {

  private final List<Integer> rolls = new ArrayList<Integer>();

  public void roll(final int pins) {
    rolls.add(pins);
  }

  protected List<Integer> getRolls() {
    return rolls;
  }

}

And finally the glue that ties the scoring together:

public class GameTest {

  @Test
  public void score() {
    final Game game = new Game();
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    game.roll(1);
    Assert.assertEquals("Score", 20, game.getScore());
  }

}

public class Game {

  public int getScore() {
    final FramesScorer scorer = new FramesScorer();
    final FrameIterator frames = new FrameIterator(getRolls());
    while (frames.hasNext()) {
      scorer.add(frames.next());
    }
    return scorer.getScore();
  }

  // ...
}

I’m confident that the code works, but let’s make sure by adding some tests with well-known answers:

public class GameTest {

  @Test
  public void perfect() {
    final Game game = new Game();
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    game.roll(10);
    Assert.assertEquals("Score", 300, game.getScore());
  }

  @Test
  public void alternateStrikesAndSpares() {
    final Game game = new Game();
    for (int i = 0; i < 5; i++) {
      game.roll(10);
      game.roll(4);
      game.roll(6);
    }
    game.roll(10);
    Assert.assertEquals("Score", 200, game.getScore());
  }

}

All green, so I guess we’re done!

Reflection

Let’s take another look at all the code to see if there is anything that needs some more attention.

One thing I notice, is that the code for TwoRollsExtraScore is a generalization for the other extra scores, so we could extract a base class. First, I introduce a constructor to set the private field:

public class TwoRollsExtraScore implements ExtraScore {

  private int numNeeded;

  public TwoRollsExtraScore() {
    this(2);
  }

  protected TwoRollsExtraScore(final int numNeeded) {
    this.numNeeded = numNeeded;
  }

  // ...
}

Then use Extract Superclass (again with manual cleanup of the errors that Eclipse introduces):

public class TwoRollsExtraScore extends BaseExtraScore {

  public TwoRollsExtraScore() {
    super(2);
  }

}

public class BaseExtraScore implements ExtraScore {

  private int numNeeded;

  protected BaseExtraScore(final int numNeeded) {
    this.numNeeded = numNeeded;
  }

  @Override
  public boolean needFrame() {
    return numNeeded > 0;
  }

  @Override
  public int getScore(final Frame frame) {
    int result = 0;
    final int numGotten = Math.min(numNeeded, frame.numRolls());
    for (int i = 0; i < numGotten; i++) {
      result += frame.pins(i);
    }
    numNeeded -= numGotten;
    return result;
  }

}

And now we can use the base class to derive the other extra score classes from:

public class OneRollExtraScore extends BaseExtraScore {

  protected OneRollExtraScore() {
    super(1);
  }

}

public class NoExtraScore extends BaseExtraScore {

  protected NoExtraScore() {
    super(0);
  }

}

With that little code in the classes, one may wonder wether they are still pulling their weight. I like to think so, since they express the concepts in the game well. I introduced them because of that, after all. So I’m keeping them.

I also find a “bug” in FakeExtraScore: the numNeeded field is never decreased, so basically it will always keep requesting new frames. Here’s the fix:

public class FramesScorerTest {

  @Test
  public void score() {
    final FramesScorer scorer = new FramesScorer();
    Frame frame = new FakeFrame(2);
    scorer.add(frame);
    Assert.assertEquals("Score", 9, scorer.getScore());

    List<ExtraScore> extraScores = scorer.getExtraScores();
    Assert.assertNotNull("Missing extra scores", extraScores);
    Assert.assertEquals("# Extra scores", 1, extraScores.size());
    Assert.assertTrue("Extra score", extraScores.get(0) instanceof FakeExtraScore);

    frame = new FakeFrame(1);
    scorer.add(frame);
    Assert.assertEquals("Score 2", 19, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 2", 2, extraScores.size());

    frame = new FakeFrame(0);
    scorer.add(frame);
    Assert.assertEquals("Score 3", 30, scorer.getScore());
    extraScores = scorer.getExtraScores();
    Assert.assertEquals("# Extra scores 3", 0, extraScores.size());
  }


  private static class FakeFrame extends BaseFrame {

    protected FakeFrame(final int pins) {
      super(Arrays.asList(pins, 9 - pins));
    }

    @Override
    public ExtraScore getExtraScore() {
      return new FakeExtraScore(pins(0));
    }

  }


  private static class FakeExtraScore implements ExtraScore {

    private int numNeeded;

    public FakeExtraScore(final int numNeeds) {
      numNeeded = numNeeds;
    }

    @Override
    public boolean needFrame() {
      return numNeeded  > 0;
    }

    @Override
    public int getScore(final Frame frame) {
      numNeeded--;
      return 1;
    }

  }

}

The rest of the code seems fine.

I must say that of all the times I’ve done this exercise, this time I ended up with the most classes/interfaces: 14 all together! But these total just 356 lines, or about 25 lines per type. Between all the syntactic cruft that Java makes me write and the generous use of blank lines that I prefer, I’d say that’s a pretty good score. I wonder how that will turn out in Groovy. Stay tuned.

The Case for Test-Driven Development

Not everybody is convinced that Test-Driven Development (TDD) is a good idea. So here’s my attempt to change that ;). Changing the world is hard, though, so this will be a long post.

Feedback
There is value in faster feedback: it allows us to steer earlier, giving us a better chance to accomplish our goals. In software development, the only reliable way to get feedback is by trying the software out in the wild, i.e. by having real end users perform their work with it.

Don’t be fooled into thinking that having someone review a design document is appropriate feedback. The reviewer does give feedback, of course, but not of the kind that will guarantee that we’ll ship a workable product. Just as the original author of the design document may miss things, so may the reviewer. The only way to be sure that our software works, is to see it working for our users. That doesn’t mean a design review isn’t valuable, just that it’s not enough. We need defense in depth all the way through.

So, the only real way of ensuring early feedback is to deliver working software frequently and get it into the hands of end users. This is done in iterations, short time-boxed periods of development. Since we value feedback, we want our iterations to be as short as possible. And short iterations require automated testing, because a manual tester simply doesn’t have enough time to test the entire application.

TDD is one form of automated testing. It is a way of coming up with lots of small, focused, and fast tests. That’s why it’s more suited for rapid feedback than automated acceptance testing. But again, we need to use all techniques in our defense in depth.

So that’s reason #1 for using TDD: it’s required to get real feedback early and often, which gives us a better chance at delivering on time, on budget by allowing us to steer often.

Quality: reliability
There are at least two aspects of quality in software development. The most obvious one is defect density. This is the external view of quality, the one experienced by our end users, and therefore the ultimate one.

Traditionally, quality was achieved using inspection, i.e. looking at some (intermediate) product and determining whether it was good enough. Manual acceptance testing falls into this category, but so do design and code reviews.

One problem with this approach is that testing comes at the end and is thus the most likely to suffer from schedule overruns. By writing the test before the code is written, you guarantee that testing will happen, since you can’t ship without the code.

Another problem is that inspection of products is expensive. You first put effort into creating a product, then into inspecting it, then into reworking it, inspecting it again, etc. That’s why many organizations changed their ways to build quality in from the start, i.e. to inspect the process instead of the product produced by the process.

TDD is a way to do just that: build quality in, i.e. prevent bugs from happening because you write the tests first. We know the code will work, since it passes the test. And since no code is written unless a test fails, we know that all code works. (Unless, of course, a test is wrong, incomplete, or missing, which is why we also need other tools in our defense in depth.)

So that’s reason #2 for using TDD: it builds in quality, leading to fewer defects, leading to happier customers and better productivity (through less time spent fixing bugs).

Quality: modifyability
But there is also the internal view of quality. Here we’re talking about code quality from a developer’s perspective. This is obviously less important than making our customers happy, but it’s significant nonetheless. Poor code slows us down when making changes, because it’s hard to understand. And it might be correct now, but if we don’t understand it well, we have a higher chance of introducing a defect when we change it.

So, what makes code difficult to understand? It’s the complexity of the code: the more things that are going on, the higher the chance that you’re missing some of the subtle interactions between them. The formal name is cyclomatic complexity, which is a measure of the number of possible paths of execution through a piece of code. Higher cyclomatic complexity is linked to higher defects.

Static code analyzers, like CheckStyle, can measure it and report warnings when limits are exceeded, so that you can then fix the code. But low cyclomatic complexity is also a byproduct of TDD, since simpler code is easier to test. Thus using TDD prevents the rework of fixing the CheckStyle warnings.

It’s a pain to have to set up a whole bunch of objects just so you can test one of them. That’s why writing the tests first naturally encourages having objects depend on not to many other objects. This is called low coupling, and together with high cohesion, it’s also a very important aspect of code quality.

So that’s reason #3 for using TDD: it improves code quality, which leads to better productivity and fewer defects (which leads to better productivity as well).

Design
“This is where the fun begins.”

Some people claim that TDD is not primarily a testing technique, but a design technique. They say TDD stands for Test-Driven Design and the tests are just a fortunate by-product of the design process.

To evaluate that claim we need to look at what design really is: moving from a problem (requirements) to a solution (working software that fulfills those requirements). Here’s a rough outline of how we do that:

We take one requirement and think of how it constraints the solution.
We then think of possible ways of satisfying those constraits.
We take the next requirement and do the same.
We modify any solutions for the first requirement that conflict with those for the second one.
We repeat until we have satisfied all requirements.

Now compare that with how TDD works:

We take one requirement and think of how it constraints the solution. Then we express these constraints with one or more tests.
We write the simplest code that can make the test pass and then refactor to improve the code organization.
We take the next requirement and do the same.
We fix any test or code for the first requirement that broke while implementing the second one.
We repeat until we have satisfied all requirements.

As you can see, doing TDD is doing design. In fact, TDD is a leaner, more effecient way of doing design, since it limits work in progress. And limiting work in progess is an important driver for productivity gains in Lean, as work in progress is seen as one of the 7 forms of waste.

So how does TDD limit work in progress? First, TDD prevents rework from testing to coding by limiting the amount of untested code.

Second, it limits the amount of design decisions awaiting implementation. Any programmer who has ever been handed a design written by someone else will know that the devil is in the details and those details will require the design to be modified. (In reality it’s likely that the design will not be updated, which is even worse.)

So that’s reason #4 for using TDD: it’s a leaner, more efficient way of designing.

Documentation
Don’t be fooled by the lack of a design document in the above description. Not having a design document does not mean there is no design or that there is no thinking before coding. The design is in the code, and the tests document it. That doesn’t mean we can’t write documentation, just that we don’t have to.

Not only are the tests documentation, they are a superior form of documentation: you can check whether the code matches the design by compiling and running the tests. And since tests are code as well, you get the full power of your IDE to help you keep the tests up-to-date when refactoring your code under test.

So that’s reason #5 for using TDD: it’s a leaner, more efficient way of keeping the design documentation up-to-date.

Conclusion
There you have it, 5 very good reasons to practice TDD:

It’s required to get real feedback early and often.
It builds in quality, preventing rework.
It improves code quality, making maintenance easier.
It’s a leaner, more efficient way of designing.
It’s a leaner, more efficient way of keeping the design documentation up-to-date.

What others are saying
Don’t just take my word for it, read what others have to say as well:

But there is more than just opinions. Although it’s always hard to scientifically test any activity that involves humans, some experiments have been performed to assess the effectiveness and efficiency of TDD.

Moving forward
So now that you’re convinced 😉 of the power of TDD, how do you start?

Well, read the book on it. And maybe read some more on the web, e.g.

The Three Laws of TDD
Unit test patterns, like Four-Phase Test
The TDD Checklist (Red-Green-Refactor in Detail)
Keep insignificant details out of tests
Test data builders

Or, you could just give it a spin. Download one of the xUnit families of unit testing frameworks, like JUnit or NUnit, and get you hands dirty. And once you’ve been there and done it, get the T-shirt.

Brian Marick: I think I finally understand mocks

Yesterday I attended a meeting co-organized by Devnology and Agile Holland and hosted by the Dutch eBay markplaats.nl where Brian Marick talked about mocks.

Brian started out with a visual demonstration of what object oriented programming is all about: interaction between objects. Each object doesn’t do very much by itself, but it’s the complex web of interacting objects that gets the job done. He visualized this interaction by having “volunteers” (representing objects) passing around a little ball (representing the flow of control):

He then went on to introduce interaction based testing using mock objects. This approach is a really white form of white box testing, since it not only knows about objects and their methods, but also about how these methods are implemented, i.e. what other objects they call and how.

Interaction based testing lends itself naturally to a top-down approach of TDD. This maximizes the chance that the objects that are designed into existence by the tests fit seamlessly with the objects calling them.

Brian described some other differences between interaction based (“London school”) and the more traditional state based (“Detroit school”) of TDD. Both have pros and cons, but ultimately Brian feels that interaction based testing using mocks makes it more likely to work with ease.

The Art of Pair Programming

Pair programming (PP) is one of the eXtreme Programming (XP) practices. When doing pair programming, two programmers share a mouse and keyboard while they write code. One of the two, the driver, types, while the other, the navigator, reviews the code, and thinks ahead. The two persons switch roles often. This is another example of XP ‘turning the knobs to 10’: if reviewing code is good, then we should do it all the time.

There is a good post on PP by Rod Hilton. He starts out with

When I first heard I’d be pairing at the new job, I was a bit apprehensive and skeptical.

I can relate to that. At a former company I worked for, I introduced XP. I had just read XP Explained: Embrace Change and thought it could improve our software development process. But pair programming was the one practice I was apprehensive about. The thought of someone watching over your shoulder all day made me feel uneasy. Yet the book made it clear that PP is a foundational practice, so I tried to keep an open mind.

I shouldn’t have worried. Rod explains that PP has nothing to do with “looking over a shoulder”:

The way pair programming works in practice is quite a bit different than I imagined it. […] When doing Test-Driven Development, one of the things we do is called “ping-pong pairing”. So the other developer will write a test, then make it compile but fail. Then he passes the keyboard to me. I implement the feature just enough to make the test pass, then I write another failing test and pass it back.

I didn’t know about ping-pong pairing when we started out doing XP. In fact, Rod’s post introduced it to me. It seems like a really good technique, and I’d love to try it out.

Also, the “all day” part is a misconception:

In reality, you don’t sit down at a desk with another person and work all day with them. You pair up for tasks. […] When the task is done and code is checked in, the pair breaks up. Generally tasks only have 2 hour estimates (sometimes less) so you’re only pairing for the two hours. Then you pair up with someone else to work on another task. […] We take breaks often because getting away from the code for a few minutes helps keep a fresh perspective when you come back to the task.

When I did XP, we paired up for about three hours at a time. We all came in on different times, so PP time generally started at about 9:30 AM, and lasted till lunch. Then we’d switch pairs. Since some of us started early, they also left early (Sustainable Pace), so there was another session of about three hours in the afternoon.

Pairing for about six hours a day is really enough. PP is pretty intense! There is no chance to let your mind wander off a bit, to look out of the window for more than a couple of seconds or to read e-mail. You have to stay focused all the time.

Advantages

So why bother at all with PP? Rod explains:

I see pairing work so well every day that I consider my career prior to my current job to have consisted mostly of wasting time. […] When you have a second person working with you, you find that you try harder to code well. You’re far, far less likely to be willing to apply duct tape to a problem, because someone else is working with you and he or she is more likely to object to the duct tape.

We all know the feeling, I guess. You know that you’re taking a shortcut, that there is a better way. But that would take more effort. When you’re pairing, your partner “keeps you honest”. You don’t want to look like a slouch, so you don’t even consider the shortcut.

This makes a big difference. In fact, while I consider myself a pretty good programmer, I must admit that the code I wrote when pairing was of considerable higher quality than the code written solo. And that is true even when pairing with someone that I knew for sure was a lesser programmer than me!

The “keeping you honest” thingie is one reason for this. “Two brains think of more than one” is another. The interplay between the driver and navigator is a subtle one. When you, as a driver, see the navigator’s eyes go blank, you know you’re code is not as clear as it could be. And you fix it. You either stop to explain, at which point the navigator will likely suggest an improvement (like a better name for a class to better express its purpose), or you switch roles and let the navigator write better code.

Disadvantages

So why isn’t everybody pairing? What’s the catch?

Well, there are downsides. Rod mentions one:

Hygiene can be a serious problem. If one person smells, it’s rough to sit with them. I find myself going back to my desk often and the code suffers for it. If you’re pairing, take a shower, and hold your farts for your next bathroom trip. Just do it, you filthy pig.

I haven’t dealt with this problem much. One guy I paired with was a smoker, so whenever he came back from a smoke outside, I’d smell the smoke. I didn’t like it, but so what. We all have our faults. Pair programming is a partnership, and like in any partnership, you need to give and take a bit 😉 PP takes some time to get good at, but the basics skills should have been acquired at Kindergarten.

Rod also mentions productivity:

there’s no denying that you’re producing fewer lines of code per day since only half your team is coding at any one point. I don’t consider that a bad thing, though (if you have two solutions that equally solve a problem, the solution with fewer lines of code is the superior one) because the QUALITY of the code that IS produced is so, so, so much higher.

This is an important point to stress. Pair programming seems wasteful, but it’s really not. The limiting factor when programming is not the speed with which you type, but the number of bugs you don’t introduce. There hasn’t been much scientific research into this, but there is one nice experiment by Alistair Cockburn and Laurie Williams that finds that PP takes 15% more time, but produces 15% less bugs, while yielding a significantly simpler design. My experiences confirm this.

The long term benefits of these advantages cannot be overestimated. Each bug takes away future coding time, since it needs to be fixed. And more complex designs slow you down as well, because it requires more time to understand the code you’re working on, and increases the chances of introducing bugs because of misunderstandings.

Of course, there will always be nay-sayers. Most of them haven’t actually tried PP, because “that could never work”. Well, if you don’t want to learn, then don’t, but don’t bother me. If you did give PP a try and failed to get good results, I must press you to check whether you did PP properly. If you think you did and still didn’t like PP, then please leave a comment explaining why.

Unit testing a user interface

So I’m on this new cool Google Web Toolkit (GWT) project of ours now. Part of the UI consists of a series of HTML labels that is the view to our model. Since our model has a tree structure, we use the visitor pattern to create this UI.

This all works beautifully, except when it doesn’t, i.e. when there is a bug. With all the recursion and the sometimes convoluted HTML that is required to achieve the desired effect, hunting down bugs isn’t always easy.

So it was about time to write some unit tests. Normally, I write the tests first. But I was added to this project, and there weren’t any tests yet. So I decided to introduce them. Now, it is often easier to start with tests than add them later. If you don’t start out by writing tests, you usually end up with code that is not easily testable. That was also the case here.

Making the code testable

So my first job was to make sure the code became testable. I started out by separating the creation of the HTML labels from the visitor code, since I didn’t want my tests to depend on GWT. So I introduced a simple TextStream:

public interface TextStream {
  void add(String text);
}

The visitor code is injected with this text stream and calls the add() method with some HTML markup. Normally, this TextStream is a HtmlLabelStream:

public class HtmlLabelStream implements TextStream {

  private final FlowPanel parent;

  public HtmlLabelStream(final FlowPanel parent) {
    this.parent = parent;
  }

  public void add(final String text) {
    parent.add(new HTML(text));
  }

}

But my test case also implements the TextStream interface, and it injects itself into the visitor. That way, it can collect the output from the visitor and compare it with the expected output.

Simplifying testing

Now I got a whole lot of HTML code that I needed to compare to the desired output. It was hard to find the deviations in this, since the required HTML is rather verbose.

So I decided to invest some time in transforming the incoming HTML into something more readable. For instance, to indent some piece of text, the HTML code contains something like this:

<div style="padding-left: 20px">...</div>

For each indentation level, 10px were used. So I decided to strip the div, and replace it with the number of spaces that corresponds to the indentation level. I repeated the same trick for a couple of other styles. In the end, the output became much easier to read, and thus much easier to spot errors in. In fact, it now looks remarkably similar to what is rendered by the browser.

This certainly cost me time to build. But it also won me time when comparing the actual and expected outputs. And adding a new test is now a breeze. Which is just the sort of incentive I need for my fellow team mates to also start writing tests…