Vector-based Bowling Scores in C++

Tuesday, 02 May 2006

Introduction

In one of his recent articles, Ron Jeffries looks at a vector-based method of calculating scores for Tenpin bowling. He uses Ruby, and makes two comments which inspired me to redo it in C++.

First, he says:

To begin with, did you notice that every method is only one line long? That's a characteristic of good Smalltalk code, and good Ruby code, in my opinion. You can't get there in Java or C# -- much less C++

I disagree — good C++ will have short functions, and many will only be one line. This is borne out by my sample code.

Ron also says:

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

I'm using C++ rather than Java or C#, but I hope Ron will still be interested. I did write versions of accumulate that accept a whole vector at once, rather than requiring a pair of iterators, but otherwise it's all idiomatic C++.

Discussion

As you can see from the code (below), there is only one functions which is more than one line long. This is Game::frame_starts, and the reason for this is the lack of the built-in numeric range generation one gets with Ruby's 1..9 syntax. With such a mechanism, we could make it similar to Game::frame_scores.

Given the range-based versions of accumulate I've added, we could add make_numeric_range to return a range containing the required integers, so Game::frame_starts could be made one line, but the code for this would end up being longer than Game::frame_starts is at the moment.

Of course, as Game::frame_scores demonstrates, the code has to go somewhere — in the case of Game::frame_scores, this is the nested class Game::AddFrameScore, and its operator(). If C++ had lambdas (which hopefully it will, when the next standard comes out), then we could include this code directly in the call to std::accumulate, but as it is, we need a whole new class. Member classes don't have the access to the instance members of their parent class that Java's inner classes enjoy, so we need to keep the reference to the Game object explicitly.

At 75 lines, including blank lines, the code is only marginally longer than the 72 lines for Ron's Ruby version, and just as clear, to my mind.

The code

Here it is, in all its glory. First the implementation:

#include <numeric>
#include <vector>
    
template<typename Range,typename Accum>
Accum accumulate(Range const& range,Accum initial) {
    return std::accumulate(range.begin(),range.end(),initial);
}

template<typename Range,typename Accum,typename Pred>
Accum accumulate(Range const& range,Accum initial,Pred pred) {
    return std::accumulate(range.begin(),range.end(),initial,pred);
}

class Game {
    std::vector<unsigned> rolls;

    struct AddFrameScore {
        Game const& game;
    
        explicit AddFrameScore(Game const& game_):
            game(game_)
        {}
    
        std::vector<unsigned> operator()(std::vector<unsigned> res,unsigned first_roll) {
            return res.push_back(game.frame_score(first_roll)), res;
        }
    };
public:
    static unsigned const frame_count=10;

    template<unsigned Size>
    explicit Game(unsigned const(& rolls_)[Size]):
        rolls(rolls_,rolls_+Size)
    {}

    unsigned score() const {
        return accumulate(frame_scores(),0);
    }

    unsigned is_strike(unsigned first_roll) const {
        return rolls[first_roll]==10;
    }
    
    unsigned is_spare(unsigned first_roll) const {
        return (rolls[first_roll]+rolls[first_roll+1])==10;
    }

    unsigned is_mark(unsigned first_roll) const {
        return is_strike(first_roll) || is_spare(first_roll);
    }

    unsigned rolls_to_score(unsigned first_roll) const {
        return is_mark(first_roll)?3:2;
    }

    unsigned rolls_in_frame(unsigned first_roll) const {
        return is_strike(first_roll)?1:2;
    }

    unsigned frame_score(unsigned first_roll) const {
        return std::accumulate(&rolls[first_roll],&rolls[first_roll+rolls_to_score(first_roll)],0);
    }

    std::vector<unsigned> frame_starts() const {
        std::vector<unsigned> res;
        for(unsigned i=0;res.size()<frame_count;i+=rolls_in_frame(i)) {
            res.push_back(i);
        }
        return res;
    }

    std::vector<unsigned> frame_scores() const {
        return ::accumulate(frame_starts(),std::vector<unsigned>(),AddFrameScore(*this));
    }
};

And now the tests:

#include <algorithm>
#include <iostream>

#define ASSERT_EQUALS(lhs,rhs)                                          \
    {                                                                   \
        if(lhs!=rhs) {                                                  \
            std::cerr<<__FILE__<<": "<<__LINE__                         \
                     <<": Error: Assertion failed: " #lhs "==" #rhs ", lhs=" \
                     <<lhs<<", rhs="<<rhs<<std::endl;                   \
        }                                                               \
    }

template<typename T>
std::ostream& operator<<(std::ostream& os,std::vector<T> const& vec) {
    os<<"{";
    for(typename std::vector<T>::const_iterator it=vec.begin(),
            end=vec.end();
        it!=end;
        ++it) {
        os<<*it<<",";
    }
    return os<<"}";
}

template<unsigned Size>
std::ostream& operator<<(std::ostream& os,unsigned const (& vec)[Size]) {
    os<<"{";
    for(unsigned i=0;i<Size;++i) {
        os<<vec[i]<<",";
    }
    return os<<"}";
}


template<typename LhsRange,unsigned RhsRangeSize>
bool operator!=(LhsRange const& lhs,unsigned const(& rhs)[RhsRangeSize]) {
    return (std::distance(lhs.begin(),lhs.end()) != RhsRangeSize) ||
        !std::equal(lhs.begin(),lhs.end(),rhs);
}

int main() {
    unsigned const full_game_rolls=20;
    unsigned const all_zeros[full_game_rolls]={0};
    ASSERT_EQUALS(Game(all_zeros).score(),0);
    unsigned const all_open[]={1,2,2,6,3,2,4,1,5,4,6,0,7,2,8,0,9,0,0,2};
    ASSERT_EQUALS(Game(all_open).score(),64);
    unsigned const all_open_frame_starts[]={0,2,4,6,8,10,12,14,16,18};
    ASSERT_EQUALS(Game(all_open).frame_starts(),all_open_frame_starts);
    for(unsigned i=0;i<full_game_rolls;i+=2) {
        ASSERT_EQUALS(Game(all_open).rolls_to_score(i),2);
    }
    unsigned const spare[full_game_rolls]={6,4,6,2};
    ASSERT_EQUALS(Game(spare).rolls_to_score(0),3);
    ASSERT_EQUALS(Game(spare).rolls_to_score(2),2);
    unsigned const all_open_frame_scores[Game::frame_count]={3,8,5,5,9,6,9,8,9,2};
    ASSERT_EQUALS(Game(all_open).frame_scores(),all_open_frame_scores);
    unsigned const spare_frame_scores[Game::frame_count]={16,8};
    ASSERT_EQUALS(Game(spare).frame_scores(),spare_frame_scores);
    ASSERT_EQUALS(Game(spare).score(),24);

    unsigned const strike[full_game_rolls-1]={10,6,2};
    ASSERT_EQUALS(Game(strike).rolls_to_score(0),3);
    ASSERT_EQUALS(Game(strike).rolls_to_score(1),2);
    unsigned const strike_frame_starts[]={0,1,3,5,7,9,11,13,15,17};
    ASSERT_EQUALS(Game(strike).frame_starts(),strike_frame_starts);

    unsigned const alternating[]={10,1,9,10,1,9,10,1,9,10,1,9,10,1,9,10};
    ASSERT_EQUALS(Game(alternating).score(),200);

    unsigned const all_strikes[]={10,10,10,10,10,10,10,10,10,10,10,10};
    ASSERT_EQUALS(Game(all_strikes).score(),300);
    
}

Posted by Anthony Williams
[/ cplusplus /] permanent link
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

Design and Content Copyright © 2005-2024 Just Software Solutions Ltd. All rights reserved. | Privacy Policy