Entry tags:

software

Bowling in C++
I've been an avid follower of Ron Jeffries' articles on scoring bowling, and the ensuing discussions on the Extreme Programming mailing list. Something about Ron's latest articles on Bowling in Smalltalk enticed me to try it myself in C++. With a twist — I've decided to do it using templates to score bowling at compile time.

Utility functions

I'm doing this using TDD, so I'll start by introducing the basic utility functions:

template<bool value>
struct Assert
{
    char array[value];
};

template<unsigned lhs,unsigned rhs>
struct AssertEqual:
    Assert<lhs==rhs>
{};

The way this works is simple: Assert<true> compiles, but Assert<false> doesn't, as it generates a zero-sized array, which is illegal in C++. Consequently Assert<someCompileTimeExpression> compiles if the expression evaluates to true, and fails if it evaluates to false. AssertEqual uses this to assert that the two parameters are equal.

First Test

That said, let's get started, with our first test:

AssertEqual<Roll<NullGame,0>::totalScore,0> roll0Scores0;

The compiler will complain about Roll and NullGame being undefined, so let's define them:

struct NullGame
{};

template<typename GameState,unsigned roll>
struct Roll
{};

Of course, we need to define totalScore in Roll:

template<typename GameState,unsigned roll>
struct Roll
{
    static const unsigned totalScore=0;
};

Our first test passes! On to the second:

AssertEqual<Roll<NullGame,6>::totalScore,6> roll6Scores6;

That's easy too:

template<typename GameState,unsigned roll>
struct Roll
{
    static const unsigned totalScore=roll;
};

The next test, a single open frame, requires that we get the score from the current game state, so we need to change NullGame as well, to have a zero totalScore:

AssertEqual<Roll<Roll<NullGame,6>,3>::totalScore,9> roll63Scores9;

struct NullGame
{
    static const unsigned totalScore=0;
};

template<typename GameState,unsigned roll>
struct Roll
{
    static const unsigned totalScore=GameState::totalScore+roll;
};

The next test, a whole game of open frames, passes as well:

AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>::totalScore,90> allOpen;

Spares

Handling a spare is more tricky. This requires keeping track of frames, so we know whether a score of 10 is a spare or just a
score of 10.

AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,6>,4>,6>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>::totalScore,22> spare;
AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,4>,4>,2>,4>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>::totalScore,14> notSpare;

Firstly, we need to know whether or not this is the last ball in the frame; this is the last ball if there was one left in the
GameState.

    static const bool thisIsLastBallInFrame=GameState::ballsLeftThisFrame==1;

That implies we need to know how many balls are left this frame — there are none left if this is the last ball, else there is one left.

    static const unsigned ballsLeftThisFrame=thisIsLastBallInFrame?0:1;

With these changes, our tests won't compile; NullGame doesn't have a member called ballsLeftThisFrame, so we need to add it:

struct NullGame
{
    static const unsigned totalScore=0;
    static const unsigned ballsLeftThisFrame=0;
};

Everything compiles again, but our spare test still doesn't pass. What we're really after is does this frame need a bonus, and does this roll score as a bonus for the previous frame.

    static const bool needsBonus=scoreThisFrame==10;
    static const unsigned totalScore=GameState::totalScore+
        (GameState::needsBonus?roll:0)+roll;

Writing by intention, we can see that we need to know the scoreThisFrame:

    static const unsigned scoreThisFrame=(thisIsFirstBallInFrame?0:GameState::scoreThisFrame)+roll;

We therefore need thisIsFirstBallInFrame:

    static const unsigned thisIsFirstBallInFrame=GameState::ballsLeftThisFrame==0;

It still doesn't compile, what's missing? NullGame doesn't have needsBonus or scoreThisFrame. Easily rectified:

struct NullGame
{
...
    static const unsigned scoreThisFrame=0;
    static const bool needsBonus=false;
};

All tests pass. Next add a test for a whole game, just spares:

AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>::totalScore,150> allSpares;

This test fails, because the last roll still counts as a normal roll. Therefore we need some way of identifying whether we're on the last frame or not; we only want to add this roll if we're not on the last frame:

    static const bool thisRollCounts=GameState::ballsLeftThisFrame || 
        !GameState::thisIsLastFrame;
    static const unsigned scoreThisFrame=(thisIsFirstBallInFrame?0:GameState::scoreThisFrame)+
        (thisRollCounts?roll:0);
    static const unsigned totalScore=GameState::totalScore+
        (GameState::needsBonus?roll:0)+
            (thisRollCounts?roll:0);

How do we know if thisIsLastFrame? This is the last frame if this is the 10th frame, which implies we need to count frames; this is a new frame if there are no balls left on the previous frame:

    static const unsigned frameCount=GameState::frameCount+
        (GameState::ballsLeftThisFrame!=0?0:1);
    static const bool thisIsLastFrame=frameCount==10;

We now need to add frameCount and thisIsLastFrame to NullGame:

struct NullGame
{
...
    static const unsigned frameCount=0;
    static const bool thisIsLastFrame=false;
};

Reflection

I was going to move on to the test for a strike now, since that's what I did when I worked through the code before writing this. However, on working through again, it strikes me that NullGame is accumulating lots of state; Roll is too, for that matter. In particular, thisIsLastFrame is redundant with frameCount. Before we go on, then, I'm going to move thisIsLastFrame out of both NullGame and Roll:

template<typename GameState>
struct IsLastFrame
{
    static const bool value=GameState::frameCount==10;
};

template<typename GameState,unsigned roll>
struct Roll
{
    static const bool thisRollCounts=GameState::ballsLeftThisFrame || 
        !IsLastFrame<GameState>::value;
...
};

Looking at the code, needsBonus also needs extracting; it's presence is implied from scoreThisFrame:

template<typename GameState>
struct NeedsBonus
{
    static const bool value=GameState::scoreThisFrame==10;
};

template<typename GameState,unsigned roll>
struct Roll
{
    static const unsigned totalScore=GameState::totalScore+
          (NeedsBonus<GameState>::value?roll:0)+
              (thisRollCounts?roll:0);
...
};

Finally, Roll contains 3 variables which are used solely for deducing the values of others, so we can make them private, leaving the same 4 public variables exposed on Roll and NullGame: totalScore, scoreThisFrame, ballsLeftThisFrame and frameCount.

Conclusion

I'll leave it there for now; we've implemented spares, with special handling for the bonus ball to the last frame, and we're ready to add support for strikes. Doing TDD for compile-time code in C++ is turning out to be quite straight-forward, and I'm reasonably happy with the resulting code. I'm not sure I'm happy with the way the list of rolls is built up, but I'm not sure how we could write it that would be better; it's something to think about.

Here's the entire code, as it stands so far:

template<bool value>
struct Assert
{
    char assertion_failed[value];
};

template<unsigned lhs,unsigned rhs>
struct AssertEqual:
    Assert<lhs==rhs>
{};

template<typename GameState>
struct IsLastFrame
{
    static const bool value=GameState::frameCount==10;
};

template<typename GameState>
struct NeedsBonus
{
    static const bool value=GameState::scoreThisFrame==10;
};


struct NullGame
{
    static const unsigned totalScore=0;
    static const unsigned scoreThisFrame=0;
    static const unsigned ballsLeftThisFrame=0;
    static const unsigned frameCount=0;
};

template<typename GameState,unsigned roll>
struct Roll
{
private:
    static const bool thisRollCounts=GameState::ballsLeftThisFrame || 
        !IsLastFrame<GameState>::value;
    static const bool thisIsLastBallInFrame=GameState::ballsLeftThisFrame==1;
    static const bool thisIsFirstBallInFrame=GameState::ballsLeftThisFrame==0;
public:
    static const unsigned ballsLeftThisFrame=(thisIsLastBallInFrame?0:1);
    static const unsigned frameCount=GameState::frameCount+
        (GameState::ballsLeftThisFrame!=0?0:1);
    static const unsigned scoreThisFrame=(thisIsFirstBallInFrame?0:GameState::scoreThisFrame)+
        (thisRollCounts?roll:0);
    static const unsigned totalScore=GameState::totalScore+
        (NeedsBonus<GameState>::value?roll:0)+
            (thisRollCounts?roll:0);
};


AssertEqual<Roll<NullGame,0>::totalScore,0> roll0Scores0;
AssertEqual<Roll<NullGame,6>::totalScore,6> roll6Scores6;
AssertEqual<Roll<Roll<NullGame,6>,3>::totalScore,9> roll63Scores9;
AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>,6>,3>::totalScore,90> allOpen;
AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,6>,4>,6>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>::totalScore,22> spare;
AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,4>,4>,2>,4>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>,0>::totalScore,14> notSpare;
AssertEqual<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<Roll<
    NullGame,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>,5>::totalScore,150> allSpares;