Vector calculation — Vector fun for bowling

The algorithm is obviously based on a functional programming paradigm. Most of my pure functional programming has been in the language Miranda so as well as the J not making any sense to me the terminology is slightly different.

The way I've been thinking about this is that the algorithm in effect forks by calculating two things in parallel: the ball numbers that start frames and the score for each ball (assuming it starts a frame). The final part brings these two together: only sum the scores for the balls that do start a frame.

So let's see if we can't work out what the start balls are. If I've understood the rules correctly then if the first ball scores a ten then the frame only has that one ball, otherwise the frame must have two balls.

When I first started to block this out I was thinking that I would use the standard C++ idiom of iterators in the for loop. As this is using std::vector though and I was actually after generating a vector of array indexes it seemed much more sensible to just use the index for the loop control. My first attempt at this function was:

std::vector< std::vector< int >::size_type > frame_starts( const std::vector< int > &balls ) {
	std::vector< std::vector< int >::size_type > ret;
	for ( std::vector< std::vector< int >::size_type pos( 0 ); pos < balls.size(); balls[ pos ] == 10 ? ( pos += 1 ) : ( pos += 2 ) )
		ret.push_back( pos );
	return ret;
}

A couple of fixed type errors later I had a much more sensible looking version:

std::vector< std::vector< int >::size_type > frame_starts( const std::vector< int > &balls ) {
	std::vector< std::vector< int >::size_type > ret;
	for ( std::vector< int >::size_type pos( 0 ); pos < balls.size(); balls[ pos ] == 10 ? ( pos += 1 ) : ( pos += 2 ) )
		ret.push_back( pos );
	return ret;
}

The next part is to calculate the score for each ball as if it was for the start of a frame. This of course means thinking the rules through a bit:

if the ball is a ten then also add the next two ball's score;
if the sum of it and the next ball is ten then add in the third one;
otherwise it is the sum of itself and the next.

I need to be careful about running off the end of the array here which may well happen if the result is for a game in progress. Running off the end of the array is going to be a fatal problem so I'm going to solve it by writing my own array operator.

My first thought was to supply a global operator[] for std::vector< int >, but I can't do this in C++ so it will have to be a global function instead:

int score( const std::vector< int > &array, std::vector< int >::size_type pos ) {
	if ( pos < array.size() ) return array.at( pos );
	else return 0;
}

My first version of the score calculation was this:

std::vector< int > ball_scores( const std::vector< int > &balls ) {
	std::vector< int > ret;
	for ( std::vector< int >::size_type pos( 0 ); pos < balls.size(); ++pos )
		if ( score( balls, pos ) == 10 )
			ret.push_back( score( balls, pos ) + score( balls, pos + 1 ) + score( balls, pos + 2 ) );
		else if ( score( balls, pos ) + score( balls, pos + 1 ) == 10 )
			ret.push_back( score( balls, pos ) + score( balls, pos + 1 ) + score( balls, pos + 2 ) );
		else
			ret.push_back( score( balls, pos ) + score( balls, pos + 1 ) );
	return ret;
}

There's clearly a load of duplication in here. I can tighten it up a little bit:

std::vector< int > ball_scores( const std::vector< int > &balls ) {
	std::vector< int > ret;
	for ( std::vector< int >::size_type pos( 0 ); pos < balls.size(); ++pos )
		if ( score( balls, pos ) == 10 || score( balls, pos ) + score( balls, pos + 1 ) == 10 )
			ret.push_back( score( balls, pos ) + score( balls, pos + 1 ) + score( balls, pos + 2 ) );
		else
			ret.push_back( score( balls, pos ) + score( balls, pos + 1 ) );
	return ret;
}

There is still a lot of adding the next two balls together, but I don't want to strip this out until I know my calculation is right. I'm not 100% sure that I've understood the rules properly so I want to see if this can produce the right results.

The last part is to sum the scores if their index numbers are correct. My first thought for this is to use a functor object, but I expect I should probably go for something less elegant, but simpler to think about to start with.

int sum_indexes( const std::vector< int > &scores, const std::vector< std::vector< int >:: size_type > &indexes ) {
	int sum( 0 );
	std::vector< std::vector< int >:: size_type >::const_iterator index( indexes.begin() );
	for ( std::vector< int >::size_type pos( 0 ); pos < scores.size() && index != indexes.end(); ++pos ) {
		if ( pos == *index ) {
			++index;
			sum += scores[ pos ];
		}
	}
	return sum;
}

I threw in the extra check of the index iterator so I wouldn't run off the end of that vector either. I think that if my other functions work properly then it will never trigger, but better safe than crashed.

Putting it together I get this:

int calculate_score( const std::vector< int > &balls ) {
	return sum_indexes( ball_scores( balls ), frame_starts( balls ) );
}

There is something to do with the last frame, but I'm not sure I understand how that is meant to work yet. I'll find a test case to trigger it and then work it out.

Running it on my current test cases I get four passes. Brilliant, but it doesn't really check any of the edge conditions. I need to add some more tests and thankfully Ron Jeffries has included the edge conditions he can think of. As an added bonus the Javascript and Ruby array syntax is identical so I can just copy and paste them. The big advantage of course in using his tests is that I'm still not 100% sure I understand the rules well enough to come up with my own.

Test( 0, [] );
Test( 0, [ 0, 0, 0 ] );
Test( 10, [ 10 ] );
Test( 10, [ 10, 0 ] );
Test( 30, [ 10, 10 ] );
Test( 90, [ 8,1, 7,2, 6,3, 5,4, 4,5, 3,6, 2,7, 1,8, 2,7, 3,6 ] );
Test( 24, [ 6,4, 6,2 ] );
Test( 24, [ 6,4, 6,2, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0 ] );
Test( 300, [ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ] );
Test( 200, [ 10, 5,5, 10, 6,4, 10, 7,3, 10, 4,6, 10, 3,7, 10, 9,1 ] );
Test( 200, [ 9,1, 10, 5,5, 10, 6,4, 10, 7,3, 10, 4,6, 10, 3,7, 10 ] );

As I expected the last tests failed:

Failed: 330/330 not 300: 10,10,10,10,10,10,10,10,10,10,10,10
Failed: 230/230 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1
Failed: 230/230 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10

This must be a problem of overcounting the scores¹ [1Now that I look back through Ron's solution it isn't totally clear to me how he deals with this. I think it is that he forces the frame start vector to always be ten elements long.]. I want to be able to deal with partial games and this means that I can't just strip things off the end, but I can re-examine the rules to see what the actual constraint is.

As far as I understand the game is exactly ten frames. This means that if frame_starts() should only return the first ten possible frame start indexes.

I don't think I can sort this out by changing the for loop condition very easily, but I can make sure that I return a short enough vector. Basically if I get more than ten frames I just return the first ten. Adding this line fixed it:

if ( ret.size() > 10 ) ret.resize( 10 );

The final thing I want to do is to shorten the ball_scores() function to remove a load of the duplication. Now I can see that the duplication is really describing the same thing so I could just calculate it once:

std::vector< int > ball_scores( const std::vector< int > &balls ) {
	std::vector< int > ret;
	for ( std::vector< int >::size_type pos( 0 ); pos < balls.size(); ++pos ) {
		int part_score( score( balls, pos ) + score( balls, pos + 1 ) );
		if ( score( balls, pos ) == 10 || part_score == 10 )
			ret.push_back( part_score + score( balls, pos + 2 ) );
		else
			ret.push_back( part_score );
	}
	return ret;
}

Whether this actually helps or is merely obfuscation is a matter of taste. I suspect obfuscation and it's a real close thing as to whether I rip it out or not. At the last moment, deciding to leave it in gives me a final listing of:

int score( const std::vector< int > &array, std::vector< int >::size_type pos ) {
	if ( pos < array.size() ) return array.at( pos );
	else return 0;
}


std::vector< std::vector< int >::size_type > frame_starts( const std::vector< int > &balls ) {
	std::vector< std::vector< int >::size_type > ret;
	for ( std::vector< int >::size_type pos( 0 ); pos < balls.size(); balls[ pos ] == 10 ? ( pos += 1 ) : ( pos += 2 ) )
		ret.push_back( pos );
	if ( ret.size() > 10 ) ret.resize( 10 );
	return ret;
}


std::vector< int > ball_scores( const std::vector< int > &balls ) {
	std::vector< int > ret;
	for ( std::vector< int >::size_type pos( 0 ); pos < balls.size(); ++pos ) {
		int part_score( score( balls, pos ) + score( balls, pos + 1 ) );
		if ( score( balls, pos ) == 10 || part_score == 10 )
			ret.push_back( part_score + score( balls, pos + 2 ) );
		else
			ret.push_back( part_score );
	}
	return ret;
}


int sum_indexes( const std::vector< int > &scores, const std::vector< std::vector< int >:: size_type > &indexes ) {
	int sum( 0 );
	std::vector< std::vector< int >:: size_type >::const_iterator index( indexes.begin() );
	for ( std::vector< int >::size_type pos( 0 ); pos < scores.size() && index != indexes.end(); ++pos ) {
		if ( pos == *index ) {
			++index;
			sum += scores[ pos ];
		}
	}
	return sum;
}


int calculate_score( const std::vector< int > &balls ) {
	return sum_indexes( ball_scores( balls ), frame_starts( balls ) );
}