Bowling Score Spiked

An Alternative Implementation

March 14, 2001

Martin & Koss [1] report the development of a program to compute bowling scores. Although they implemented in Java, I was reminded of writing the same program in Fortran years ago. I was startled at how hard the problem was until I realized that the requirement didn't ask the calculation to be done in the same order I might while bowling. That is, spares and strikes are much easier to score if one just looks ahead to see what future roles turn out to be.

Martin & Koss wrote the program to illustrate pair-programming. I decided to repeat their work only this time as a programming spike. A spike is written for the experience. A spike doesn't produce production code and is therefor exempt from Extreme Programing's pair-programming requirement. I spiked the bowling score calculator to see how it would code up as a series of transformations applied to all the data at once.

Here is the data Martin & Koss used.

The input is the sequence of throws recorded along the top of each frame. The output is the running total reported in the bottom. I chose to represent the input as a string of digits with commas at frame boundaries. Strikes and spares are denoted by x and / as is the custom with hand scoring. My program translates the input to output in place with a series of substitution commands of the following form.

      s/from/to/g;
      s/from/to/ge;

Here s means substitute, g means substitute globally over all input and e means to evaluate the to string as an expression before substituting. The input is stored in the special variable $_ which is modified in place. The from string is written as a regular expression where \d means digit and \/ means a slash. Parenthesized substrings of the regular expression can be cited in the to string as $1, $2, etc.

I developed the program in increments of one line and tested the result by inspection. Here is a log of these additions along with the output produced by that version of the program. I sometimes made syntax errors which I corrected by inspection of the line added. I made one logic error which I corrected. I will discuss this later. Here is the annotated transcript of my development.


Write first draft of the program in perl.

	print "hello";

	hello

Replace hello with input data, frames separated with commas.

	$_ = '1 4, 4 5, 6 /, 5 /, x, 0 1, 7 /, 6 /, x, 2 /, 6';
	print;

	1 4, 4 5, 6 /, 5 /, x, 0 1, 7 /, 6 /, x, 2 /, 6

Now we start with logic ... spares count next throw twice

	s/\/, (\d)/\/ $1, $1/g;

	1 4, 4 5, 6 / 5, 5 /, x, 0 1, 7 / 6, 6 /, x, 2 / 6, 6

even if it is a strike.

	s/\/, (x)/\/ 10, x/g;

	1 4, 4 5, 6 / 5, 5 / 10, x, 0 1, 7 / 6, 6 / 10, x, 2 / 6, 6

Now replace / with throw that made it.

	s/(\d )\//$1.(10-$1)/ge;

	1 4, 4 5, 6 4 5, 5 5 10, x, 0 1, 7 3 6, 6 4 10, x, 2 8 6, 6

Strikes count the next two throws twice.

	s/x, (\d \d)/x $1, $1/g;

	1 4, 4 5, 6 4 5, 5 5 10, x 0 1, 0 1, 7 3 6, 6 4 10, x 2 8, 2 8 6, 6

(we would deal with strikes on strikes here if there were any)

Now replace x with the 10 it represents.

	s/x/10/g;

	1 4, 4 5, 6 4 5, 5 5 10, 10 0 1, 0 1, 7 3 6, 6 4 10, 10 2 8, 2 8 6, 6

This is a good time to trim the input to just ten frames
(though this was discovered later).

	s/(((,?)( \d+)+){10}).*/$1/;

	1 4, 4 5, 6 4 5, 5 5 10, 10 0 1, 0 1, 7 3 6, 6 4 10, 10 2 8, 2 8 6

We could just sum these for a total, but let's proceed frame by frame.

	s/(\d+) (\d+)/$1+$2/ge;

	5, 9, 10 5, 10 10, 10 1, 1, 10 6, 10 10, 12 8, 10 6

And again, to add the bonuses.

	s/(\d+) (\d+)/$1+$2/ge;

	5, 9, 15, 20, 11, 1, 16, 20, 20, 16

Now we convert this to a running total.

	my $total;
	s/(\d+)/$total+=$1/ge;

	5, 14, 29, 49, 60, 61, 77, 97, 117, 133

Done. Here is the whole program.

	$_ = '1 4, 4 5, 6 /, 5 /, x, 0 1, 7 /, 6 /, x, 2 /, 6';
	s/\/, (\d)/\/ $1, $1/g;
	s/\/, (x)/\/ 10, x/g;
	s/(\d )\//$1.(10-$1)/ge;
	s/x, (\d \d)/x $1, $1/g;
	s/x/10/g;
	s/(((,?)( \d+)+){10}).*/$1/;
	s/(\d+) (\d+)/$1+$2/ge;
	s/(\d+) (\d+)/$1+$2/ge;
	my $total;
	s/(\d+)/$total+=$1/ge;
	print;

I've since added some comments to the program and enough boilerplate to be a cgi script.

I've declared my spike complete even though I've left two loose ends. First, I didn't handle all possible strike cases, and second, I suspect there is a better solution to partial scoring of the last frame. The strikes will require another substitution or two while the partial scoring might be more easily handled without an eleventh frame. I'll be sure to write tests for these cases should I ever write this as production code.

A spike might be better called a practice program. Here I have been practicing with a vector oriented style, one where simple operations apply to whole vectors of data. Never mind that I simplified my representation by using pattern matching rather than forming each of the necessary vectors. Vector programs often have fewer loops and branches than ordinary programs and are a good fit with today's highly optimized processors.

I encourage all programmers to practice often. Especially practice if you find you are unsure of your own performance while production programming. Practice fills your mind with the little bits of experience that you will draw on continuously while writing far larger and more serious programs.

[1] Advanced Principles, Patterns and Process of Software Development, Robert C. Martin, Prentice Hall, 2001.