Bowling score calculation exercise

by Mace on 06 September 2012

Overview

Some time back, I came across a php challenge where the goal was to create a calculator of bowling scores based on frames in the fewest number of characters. In practice, you don't want to try this kind of optimization because it doesn't help anything. The reasoning is that php is interpreted and parsed. If you were doing assembly programming, or low-level C instead, then you'll find some small improvement with a couple of the tricks, but with php, it's just a mental exercise. I wanted to explain the entire process, from nothing to the finished product.

Overview
How to score a game
Sample Data
Testing the data
Solving the scoring system
Minimize the code
Finale
Final source

How to score a game

Most people know that a perfect game is a score of 300, a strike is knocking all 10 pins down on the first throw, and a spare is knocking all 10 pins down on two throws, but many get confused as to how to actually calculate a real score. The score is the number of pins you knock down plus a bonus if you knock all 10 down in a frame. The bonus adds either the next throw, for a spare, or next two throws, for a strike, to the current frame. The bonus doesn't add the subsequent frames to the score, only the individual throws. So since a spare is given a single throw bonus, the most that can be added is 10, and since a strike gives a two throw bonus, the most that can be added is 20. It's because of the bonuses that when you look at someone's score in-progress, the current frames might not have a score associated with them; the bonuses haven't occurred yet. Each frame, the bowler is allowed two throws to knock down 10 pins. If they knock them all down on the first throw, then that is a strike and the second isn't made, and the bowler receives a two throw bonus for the frame. If the bowler knocks down all 10 pins in two, but not one, throws, then that is a spare and the bowler receives a single throw bonus for the frame.

The final, 10th frame, but with special conditions to allow for proper bonuses for frames. In the 10th frame, if you bowl a spare, then you are given an extra bonus throw for the frame, but this is only a bonus for the frame and isn't counted extra as an 11th frame. For a strike, the bowler is allowed two more throws to be added to the current frame. If in any of the bonus throws in the 10th frame, the bowler gets a strike or spare, then they are not awarded any more extra throws.

Sample data

The challenge required the calculator function to accept a string of frame scores such that each throw is provided in a comma separated fashion. If someone bowled a strike, then it would be represented as "10" and not "10,0"; all other forms assumed two throws per frame except the final frame that can allow up to three. I took the provided sample throw results and placed them into an array with the final scores and scoresheet.

 $scores = array(
    array(
        'score' => 300,
        'sheet' => '10,10,10,10,10,10,10,10,10,10,10,10'
    ),
    array(
        'score' => 181,
        'sheet' => '9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,0'
    ),
    array(
        'score' => 193,
        'sheet' => '9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,0,3'
    ),
    array(
        'score' => 87,
        'sheet' => '5,0,3,4,5,2,9,0,3,3,6,3,7,3,9,0,3,4,9,0'
    ),
    array(
        'score' => 191,
        'sheet' => '9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,10'
    ),
    array(
        'score' => 200,
        'sheet' => '10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1'
    ),
    array(
        'score' => 0,
        'sheet' => '0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0'
    ),
);

Testing the data

After having the sample data on hand and in a format digestible, we want to set up a simple test environment. Since this will be run from the command line and it's small, there's no need to fire up something like phpunit for this. We just need to cycle through every game, pump the scoresheet into our function, and compare the result to the expected result.

foreach ($scores as $game) {
 
    if ($game['score'] === score($game['sheet'])) {
 
        echo '.';
 
    } else {
 
        echo "F {$game['score']}::" . score($game['sheet']) . "\n";
 
    }
 
}
 
echo "\n";
 
function score($sheet) {}

We make sure to use the === comparison instead of == because we're trying to explicitly compare scores. In php, 0 and 1 are analogous to false and true respectively, so if we return nothing, aka null, comparing with == yields true.

(0 == 0) -> true
(0 == false) -> true
(0 == null) -> true
(0 === 0) -> true
(0 === false) -> false
(0 === null) -> false

Sometimes you want this sort of check, and sometimes you don't, as is the case when comparing scores.

When initially running, you should get a result like this:

$ php bowl.php 
F 300::
F 181::
F 193::
F 87::
F 191::
F 200::
F 0::

Everything fails because we aren't returning anything from our scoring function. When we add a basic return value of zero, 0, to start with, then we start to see some progress.

function score($sheet)
{
    return 0;
}

$ php bowl.php 
F 300::0
F 181::0
F 193::0
F 87::0
F 191::0
F 200::0
.

The zero test case now passes, and we're on a good path.

Solving the scoring system

Before you can minimize anything, you need to have something working correctly. The first thing we need to do is make sure all of our tests pass, and to do that, we need to figure out how to use that string representing the scoresheet. Most languages have ways to split a string into tokens, and php is no different. There are a few core functions provided, but the preferred one is explode(). This returns an array of tokens from a string split by a delimiter, in this case, a comma. We should also work with a score variable to return after calculating.

function score($sheet)
{
    $score = 0;
    $throws = explode(',', $sheet);
    return $score;
}

The next step is to loop through the throws and add them to the score.

function score($sheet)
{
    $score = 0;
    $throws = explode(',', $sheet);
    foreach ($throws as $throw) {
        $score += $throw;
    }
    return $score;
}

We get closer to the result by getting another test to pass, but it's not factoring in the bonuses.

$ php bowl.php 
F 300::120
F 181::100
F 193::103
F 87::78
F 191::110
..

We have to back up a little to see where the logic in our current setup falters, and it's in the loop. If we just cycle through every throw, then we can't do bonuses per frame easily. Since every game is exactly 10 frames, we should loop exactly 10 times and deal with the throws later.

function score($sheet)
{
    $score = 0;
    $throws = explode(',', $sheet);
    for ($frame = 0; $frame < 10; $frame++) {
        $score += $throws[$frame];
    }
    return $score;
}

Now it appears we're going backwards on the test results, but that sometimes happens when you progress in small steps.

$ php bowl.php 
F 300::100
F 181::50
F 193::69
F 87::34
F 191::50
F 200::70
.

We have a frame counter, but we also need a throw counter to keep track of what we're looking at. We also need to factor in strike and spare detection from the throws.

function score($sheet)
{
    $score = 0;
    $throwCounter = 0;
    $throws = explode(',', $sheet);
    for ($frame = 0; $frame < 10; $frame++) {
        $current = $throws[$throwCounter];
        if ($current > 9) {
            // strike
        } else {
            // no strike, roll again
            $current += $throws[$throwCounter + 1];
            $throwCounter = $throwCounter + 1;
        }
        if ($current > 9) {
            // spare
        }
        $score += $current;
        $throwCounter = $throwCounter + 1;
    }
    return $score;
}

What we're doing now is looking at the current throw score, which would be the first for the frame, and seeing if it's greater than 9. If it's greater than 9, that means you knocked down all 10 and you have yourself and nice little strike. If you didn't get a strike, it adds the next throw to it for your frame total. If that is greater than 9, meaning all 10 were knocked down in a single frame, you have a spare. Now it's time to add in the score bonuses. Remember, we need to add the next two frames on a strike, and only the next frame on a spare. Both instances add the next frame, so let's first check for a strike. If it's a strike, add the bonus frame to the current frame score. Since a strike is also a spare, we don't need a special condition checking the spare instead of a strike so we can let it cascade through.

function score($sheet)
{
    $score = 0;
    $throwCounter = 0;
    $throws = explode(',', $sheet);
    for ($frame = 0; $frame < 10; $frame++) {
        $current = $throws[$throwCounter];
        if ($current > 9) {
            // strike add the frame two ahead
            $current += $throws[$throwCounter + 2];
        } else {
            // no strike, roll again
            $current += $throws[$throwCounter + 1];
            $throwCounter = $throwCounter + 1;
        }
        if ($current > 9) {
            // spare or strike, add the next frame
            $current += $throws[$throwCounter + 1];
        }
        $score += $current;
        $throwCounter = $throwCounter + 1;
    }
    return $score;
}

$ php bowl.php 
.......

Minimize the code

Congratulations, all tests pass and you now have a bowling score calculator. Normally, this would be enough, but we're trying to minimize it, so we should look at ways to shrink it.

Increment and comments

I always increment via ++ and expanded it here for clarity; let's compress that. Let's also go ahead and remove comments since that's wasted space when it comes to minimizing.

function score($sheet)
{
    $score = 0;
    $throwCounter = 0;
    $throws = explode(',', $sheet);
    for ($frame = 0; $frame < 10; $frame++) {
        $current = $throws[$throwCounter];
        if ($current > 9) {
            $current += $throws[$throwCounter + 2];
        } else {
            $current += $throws[$throwCounter + 1];
            $throwCounter++;
        }
        if ($current > 9) {
            $current += $throws[$throwCounter + 1];
        }
        $score += $current;
        $throwCounter++;
    }
    return $score;
}

$ php bowl.php 
.......

Shorter variables

There's no reason to have long variable names now, so let's use single letters for them instead. This makes it a pain to read later and debug, but we don't care now. If we just went with the first letters, we'd have some conflicts, so let's do the following conversions:

$sheet: $s
$score: $t for total
$throwCounter: $x for a common counter name
$throws: $r for thRows
$frame: $f
$current: $c

function score($s)
{
    $t = 0;
    $x = 0;
    $r = explode(',', $s);
    for ($f = 0; $f < 10; $f++) {
        $c = $r[$x];
        if ($c > 9) {
            $c += $r[$x + 2];
        } else {
            $c += $r[$x + 1];
            $x++;
        }
        if ($c > 9) {
            $c += $r[$x + 1];
        }
        $t += $c;
        $x++;
    }
    return $t;
}

$ php bowl.php 
.......

Integrate increments

That's more like it. Now we don't know what in the world we're working with, and that's kind of the point with minimizing. Now let's do a little trick here with the increments of the throws. Since we're incrementing $x on every cycle, we can check to see if the current $x is actually used anywhere. In our case, we're always using $x+1 or $x+2 so let's just increment when we use it. There are a couple shorthand ways to increment and decrement. If you do $x++, then that'll use the variable, and afterwards increment. If you use ++$x, then it'll increment first, then use. Since we're using it in an array setting, $r[$x++] would call the $x item in the array, and increment after usage. It's a shorthand way of doing this.

$r[$x++];
// same as
$r[$x];
$x++;

Knowing this, we can combine the increments at two places to get the following.

function score($s)
{
    $t = 0;
    $x = 0;
    $r = explode(',', $s);
    for ($f = 0; $f < 10; $f++) {
        $c = $r[$x++];
        if ($c > 9) {
            $c += $r[$x + 1];
        } else {
            $c += $r[$x++];
        }
        if ($c > 9) {
            $c += $r[$x];
        }
        $t += $c;
    }
    return $t;
}

$ php bowl.php 
.......

Ternaries

The next part you can compress deals with the if/else statements. When using if statements to conditionally assign a value, it's usually a wise idea to use the ternary operation in those cases. Here, we can use the ternary in two places. The first is the obvious assignment to $c if it's a strike, and the other is in assigning the $t value. The second one is less obvious, but the case is when to add the extra frame to the current score.

function score($s)
{
    $t = 0;
    $x = 0;
    $r = explode(',', $s);
    for ($f = 0; $f < 10; $f++) {
        $c = $r[$x++];
        $c += ($c > 9) ? $r[$x + 1] : $r[$x++];
        $t += ($c > 9) ? $r[$x] + $c : $c;
    }
    return $t;
}

$ php bowl.php 
.......

Variable assignments

One more trick to shave 4 solid characters that comes directly from C is multiple concurrent assignments of variables to the same value, and in this case, the for loop. I tend to avoid this trick because it's not often where you have a legitimate reason to use it. It's basically taking a series of common assignments, and stringing them together. In this example, $t, $x, and $f all start at 0, so can be strung together as $t=$x=$f=0.

function score($s)
{
    $r = explode(',', $s);
    for ($t = $x = $f = 0; $f < 10; $f++) {
        $c = $r[$x++];
        $c += ($c > 9) ? $r[$x + 1] : $r[$x++];
        $t += ($c > 9) ? $r[$x] + $c : $c;
    }
    return $t;
}

$ php bowl.php 
.......

Preincrement loop

We can shave a few extra characters by moving the for loop increment to the comparison section exploiting the fact that after every cycle, the comparison is executed to see if to stop. We leave the third position in the loop empty since there's no use for it.

function score($s)
{
    $r = explode(',', $s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $c = $r[$x++];
        $c += ($c > 9) ? $r[$x + 1] : $r[$x++];
        $t += ($c > 9) ? $r[$x] + $c : $c;
    }
    return $t;
}

$ php bowl.php 
.......

explode to str_getcsv

We can now shave an additional character by using a seldom used function called str_getcsv(). This is basically the same as explode with a comma since it's to grab data from comma separated values, csv, but it's one character less for our implementation so we'll use it.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $c = $r[$x++];
        $c += ($c > 9) ? $r[$x + 1] : $r[$x++];
        $t += ($c > 9) ? $r[$x] + $c : $c;
    }
    return $t;
}

$ php bowl.php 
.......

Remove curly braces

Let's now try to remove those curly braces on the loop. In order to do so, we need to make those three lines a single, long statement. In order to do so, we really need to think both out of box programmatically and inside the box mathematically. We need to use equation substitution to get to our end goal where we substitute the first two statements into the third to create a wild beast of a line.

Separate statements

The first step is to blend the second line into the third so we only have two lines left. Since we're changing the structure a little, we're going to be adding another holding variable into the mix to take the place of $c cascading through; we'll call this $d. This is an intermediate step, so doesn't really accomplish anything, but here's how it looks.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $c = $r[$x++];
        $d = ($c > 9) ? $r[$x + 1] : $r[$x++];
        $d = $d + $c;
        $t += ($d > 9) ? $r[$x] + $d : $d;
    }
    return $t;
}

$ php bowl.php 
.......

Move ternary

If we look closely, we can play a little trick and move the ternary from the second statement, to the last. If we assume we're incrementing $x always, then we can conditionally revert $x in the last line.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $c = $r[$x++];
        $d = $r[$x++];
        $d = $d + $c;
        $t += ($d > 9) ? $r[$c > 9 ? $x-- : $x] + $d : $d;
    }
    return $t;
}

$ php bowl.php 
.......

First substitution

Now we have something that we can easily substitute. I'll step through the substitutions.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $c = $r[$x++];
        $d = $r[$x++] + $c;
        $t += ($d > 9) ? $r[$c > 9 ? $x-- : $x] + $d : $d;
    }
    return $t;
}

$ php bowl.php 
.......

Second substitution

Simple enough, now put the entire $d declaration into the first comparison. An annoying thing when trying to read and debug a problem so I highly stress not using it, but you're allowed to declare and assign values mid-line.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $c = $r[$x++];
        $t += (($d = $r[$x++] + $c) > 9) ? $r[$c > 9 ? $x-- : $x] + $d : $d;
    }
    return $t;
}

$ php bowl.php 
.......

Third substitution

Now to take the first line and plug it into the last so we get our single line. We use the same methodology as the last step.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $t += (($d = $r[$x++] + ($c = $r[$x++])) > 9) ? $r[$c > 9 ? $x-- : $x] + $d : $d;
    }
    return $t;
}

$ php bowl.php 
..F 193::184
....

Now look at that, a test failed when we did that. The reason is the order in which we have the $c assignment which affects the mathematical order of operations in the calculations, so we'll just flip that around and have another go.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;) {
        $t += (($d = ($c = $r[$x++]) + $r[$x++]) > 9) ? $r[$c > 9 ? $x-- : $x] + $d : $d;
    }
    return $t;
}

$ php bowl.php 
.......

Remove unneeded characters

That's better. We have a functioning bowling score calculator that's a single line inside the loop. We're able to remove those curly braces on the for loop now, and we should also take care of unneeded parentheses while we're at it too.

function score($s)
{
    $r = str_getcsv($s);
    for ($t = $x = $f = 0; ++$f < 11;)
        $t += ($d = ($c = $r[$x++]) + $r[$x++]) > 9 ? $r[$c > 9 ? $x-- : $x] + $d : $d;
    return $t;
}

$ php bowl.php 
.......

Whitespaces

The last thing to do is to remove all newlines and whitespaces so it's as compact as possible. This basically renders the entire thing unreadable, so it's usually the final step to any minimizing.

function score($s)
{
    $r=str_getcsv($s);for($t=$x=$f=0;++$f<11;)$t+=($d=($c=$r[$x++])+$r[$x++])>9?$r[$c>9?$x--:$x]+$d:$d;return$t;
}

$ php bowl.php 
.......

Finale

So there you have it. A bowling score calculation function in only 108 characters. I'm sure there's probably some other way to shave a character off, but this is good enough for this exercise.

Final Source

 $scores = array(
    array(
        'score' => 300,
        'sheet' => '10,10,10,10,10,10,10,10,10,10,10,10'
    ),
    array(
        'score' => 181,
        'sheet' => '9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,0'
    ),
    array(
        'score' => 193,
        'sheet' => '9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,0,3'
    ),
    array(
        'score' => 87,
        'sheet' => '5,0,3,4,5,2,9,0,3,3,6,3,7,3,9,0,3,4,9,0'
    ),
    array(
        'score' => 191,
        'sheet' => '9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1,10'
    ),
    array(
        'score' => 200,
        'sheet' => '10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1,10,9,1'
    ),
    array(
        'score' => 0,
        'sheet' => '0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0'
    ),
);
 
foreach ($scores as $game) {
    if ($game['score'] === score($game['sheet'])) {
        echo '.';
    } else {
        echo "F {$game['score']}::" . score($game['sheet']) . "\n";
    }
}
 
echo "\n";
 
function score($s) {
    $r=str_getcsv($s);for($t=$x=$f=0;++$f<11;)$t+=($d=($c=$r[$x++])+$r[$x++])>9?$r[$c>9?$x--:$x]+$d:$d;return$t;
}

Main menu

Navigation Menu