As I am currently rereading Leo Brodie’s Thinking Forth, I am amazed about how most of the program design tips in this 1984 book are still relevant today. The author’s first book, Starting Forth initiated a life-long love story with programming for me, and Forth is still one of my favorite languages. In this post I will try to convey a sense of the Forth philosophy while solving the popular Bowling Score Kata using gforth. Although doing TDD in Forth is very easy, I choose to not include the tests in this post in order to keep it short.

The Problem to Solve

Write a program which, given a series of rolls delivered by a Ten Pin Bowling player, computes the current score of this player. The roll values will be consistent with the game rules: no illegal values (such as -1, 11 or values totaling more than 10 in a frame). In test cases where not all rolls have been played, the resulting value should be the minimum score obtained (i.e the score value if all the subsequent rolls were 0).

Here is an excerpt of the game rules:

A game of bowling consists of ten frames. In each frame, the bowler will have two chances to knock down as many pins as possible with their bowling ball. In games with more than one bowler, as is common, every bowler will take their frame in a predetermined order before the next frame begins. If a bowler is able to knock down all ten pins with their first ball, he is awarded a strike. If the bowler is able to knock down all 10 pins with the two balls of a frame, it is known as a spare. Bonus points are awarded for both of these, depending on what is scored in the next 2 balls (for a strike) or 1 ball (for a spare). If the bowler knocks down all 10 pins in the tenth frame, the bowler is allowed to throw 3 balls for that frame. This allows for a potential of 12 strikes in a single game, and a maximum score of 300 points, a perfect game.

Specifications

To make the expected behavior of the program clearer, here are some specs, in the format usually displayed on the SPOJ online judge. The program will read the input stream and print results on the output stream.

Input

t – the number of test cases, then t test cases follows.
each test case consists in 2 lines:
- n - the number of rolls delivered, ( 0 < n ≤ 21 )
- r1,..rn - the rolls delivered ( 0 ≤ r ≤ 10 )

Output

For each test case output one integer: the score made by the player after they played all the rolls in the test case.

Example

Input

3
2
4 6
4
10 7 3 5
12
10 10 10 10 10 10 10 10 10 10 10 10

Output

10
40
300

Solving it with Forth

Main Routine

Let’s pretend we have one of these bowling score sheets and use it to mark the points made as we receive the numbers: 10, 7, 3, 5:

10 : we mark a strike X and are ready to use the next frame column on the sheet. The score for the frame is still not calculable given that the next frame throws are not known yet.

7 : we mark a 7 on the first column of the frame. The score for frame 1 is still not known yet, as we are expecting two more rolls to determine it.

3 : we mark a spare / and are ready to use the next frame column. The score for the first frame is 20, and the score for this frame is not known yet, as we are expecting a bonus from the next throw.

5 : we mark a 5 on the first column of the frame. The score for frame 1 + frame 2 is 35.

So what we routinely do to keep the score is:

mark the points made for the current frame
keep track of the bonus generated by a strike or a spare
collect the extra points when the roll corresponding to a bonus is being delivered and mark the score on the corresponding frame column
decide, depending on the roll delivered, if we have to “close the frame”, meaning go to a new frame column or play again in the current frame (“open frame”)
keep track of how many frame were already played in order to count the last supplementary rolls as part of the 10th frame, and not the beginning of a new frame.
and of course, add the points (roll + extra) to the current score

This is basically what our main routine will have to do when given a value on the stack. The only difference is that our program will not need to mark the points and the score for each specific frame, just to keep the score updated. Here is some pseudo-code:

: ROLL+ ( #pins -- )
    \ collect extra point from previous bonus applied to the #pins value 
    ( frame count is between 0 and 9) IF
    ( add the roll value to the score 
    ( check for bonus with this value given the current frame state )
    ( close the frame or make it open depending on bonus found )
    ( increase frame count if the frame is closed )
    ;

Keeping the Score

The first thing we obviously need is a variable to memorize the player’s score. Since that variable needs to be initialized, let’s also create a definition to that effect:

VARIABLE SCORE

: START
    0 SCORE ! ;

Surely we will need to amend this definition to include several other variables.

Bonus

Let’s interest ourselves in the bonus mechanism. When the player delivers a strike, their next roll and the following roll will be added as bonus. When the player delivers several strikes in a row, then the next roll will be added twice as a bonus.

roll    10  10  10   10   3
bonus       1   1+1  1+1
suppl       1   1    1

Bonus works like it is provided by a dispenser: we feed the dispenser with bonus points gained from a strike or a spare, and these bonus points generate a multiplication factor for the subsequent rolls that are added to the game. Once the bonus factor for a roll is consumed, the dispenser is ready to provide the bonus factor to be used with the next roll.

Since there are only 2 factors to consider and these are tiny values, we can store them in the same variable, which makes switching from bonus to supplementary bonus easy. The bonus part will occupy bits 0 to 1, while the supplementary part will be represented by bit 2.

VARIABLE SCORE
VARIABLE BONUS

: START
    0 SCORE !
    0 BONUS ! ;

A spare creates a bonus factor of 1 and sets the next bonus factor to 0:

: SPARE \ set the bonus to 1, no supplement
    1 BONUS ! ;

A strike increments the current bonus factor, and sets the next bonus factor (bit 3) to 1 with a bitwise OR operation:

: STRIKE \ increase bonus, and set supplement to 1
    BONUS @ 1+ 4 OR BONUS ! ;

Consuming the bonus consists in isolating the bonus value (bits 0 and 1) with a bitwise AND, leaving that value on the stack and then right-shifting the bonus value by 2 positions on the right to make the next bonus (bit 2) the current bonus.

: BONUS> ( -- n ) \ produce bonus factor, get supplement ready
    BONUS @ DUP 3 AND
    SWAP 2/ 2/ BONUS ! ;

Now let’s try our definitions.

    START BONUS> .  ⏎
    0 ok
    START SPARE BONUS> . BONUS> . ⏎
    1 0 ok
    START STRIKE BONUS> . BONUS> . ⏎
    1 1 ok
    START STRIKE BONUS> . STRIKE BONUS> . BONUS> . ⏎
    1 2 1

We can see that our dispenser keeps track of the bonus factors to apply.

Collecting Bonus

Collecting the bonus can be done by multiplying the roll value by the bonus factor, and adding that to the score.

: COLLECT-BONUS ( #pins -- ) \ add extra points to score and advance bonus
    BONUS> * SCORE +! ;

Frame Count

Obviously we will have to remember how many frames the player has played. This requires another variable, and this variable should also be initialized at the outset of a game.

VARIABLE SCORE
VARIABLE BONUS
VARIABLE FRAME#

: START
    0 SCORE !
    0 BONUS !
    0 FRAME# ! ;

The frame count has to be incremented every time the player closes a frame (i.e delivers a strike or throw their second roll), but it will not go beyond 10:

: FRAME#> \ advance frame count
    FRAME# @ 1+ 10 MIN FRAME# ! ;

Frame State

When adding a roll to the game, how can we know if that roll is part of an open frame or if it starts a new frame? We have to keep track of the current frame state. If the frame is open, then we should be able to retrieve the first roll value from this frame.

Let’s introducte another variable:

VARIABLE FRAME

A frame is either a new frame, meaning the player hasn’t thrown her first roll yet, or an open frame, meaning the player has already thrown one roll. We can consider that when the value of the FRAME variable is 0, then it is a new frame, an open frame otherwise:

: OPEN-FRAME? ( -- ? )
    FRAME @ ;

: NEW-FRAME? ( -- ? )
    OPEN-FRAME? 0= ;

The player “closes” the frame when she delivers a strike at first roll, or delivers the second roll. Marking the frame as closed can be done by setting the frame state to zero, and advancing the frame count.

: CLOSE-FRAME \ close frame and increment frame count
    0 FRAME ! FRAME#> ;

The player “opens” the frame when the first roll is not a strike. Then the program has to store the value of this roll, and set the frame to open, i.e not zero. This can be done in a single step if we consider the value of the frame to equal the last roll + 1. Since the roll value can be a number from 0 to 9, a frame value between 1 and 10 means the frame is open and the last roll value is this frame value minus 1.

: OPEN-FRAME ( #pins -- ) \ open frame, saving 1st roll value+1
    1+ FRAME ! ;

: LAST-ROLL ( -- #pins ) \ retrieve the first roll value
    FRAME @ 1- ;

Again, we need to initialize the frame state before the game starts.

: START
    0 SCORE !
    0 BONUS !
    0 FRAME# !
    0 FRAME ! ;

And now we can try our definitions.

    START NEW-FRAME? .  ⏎
    -1 ok
    7 OPEN-FRAME NEW-FRAME? . OPEN-FRAME? . LAST-ROLL .  ⏎
    0 -1 7 ok
    3 OPEN-FRAME CLOSE-FRAME NEW-FRAME? .  ⏎
    -1 ok

Checking for Bonus

So far, we have word definitions to collect the bonus, declare a strike or a spare, increment the frame count, and update the frame state. What we need now is a word that will qualify the roll value that has been delivered, implementing the following rules:

We have a strike if the roll is a 10 and we are in a new frame. In that case, add points to the bonus and close the frame.
If the frame is new but we don’t have a strike then open the frame, saving the roll value.
We have a spare if the frame is open and the sum of the rolls in the frame is equal to 10.
If the frame is open, wether we have a spare or not we have to close the frame.

Hence the words:

: CHECK-STRIKE ( #pins -- )
    DUP 10 = IF
        DROP STRIKE CLOSE-FRAME
    ELSE
        OPEN-FRAME
    THEN ;

: CHECK-SPARE ( #pins -- )
    LAST-ROLL + 10 = IF SPARE THEN
    CLOSE-FRAME ;

: CHECK-BONUS ( #pins -- )
    NEW-FRAME? IF CHECK-STRIKE ELSE CHECK-SPARE THEN ;

Adding a Roll to the Current Score

We are almost done. Adding a roll to the game will execute these tasks of collecting bonus, adding the roll points to the score, checking for new bonus, and advancing the frame count. These last 3 tasks has to be executed only if the frame count is below 10, if it’s not the case, then the roll value is dropped instead.

: ROLL+ ( #pins -- )
    DUP COLLECT-BONUS
    FRAME# @ 0 10 WITHIN IF
        DUP SCORE +!
        CHECK-BONUS
    ELSE
        DROP
    THEN ;

Let’s try our word!

    START 4 ROLL+ SCORE ?  ⏎
ok
ROLL+ SCORE ?  ⏎
ok
ROLL+ 2 ROLL+ SCORE ?  ⏎
ok
ROLL+ SCORE ?  ⏎
ok
ROLL+ 2 ROLL+ SCORE ?  ⏎
ok
ROLL+ SCORE ?  ⏎
ok
ROLL+ SCORE ?  ⏎
ok
ROLL+ 4 ROLL+ SCORE ?  ⏎
ok
ROLL+ 5 ROLL+ SCORE ?  ⏎
ok
ROLL+ SCORE ?  ⏎
ok
ROLL+ 2 ROLL+ 7 ROLL+ SCORE ?  ⏎
ok
    : PERFECT START 12 0 DO 10 ROLL+ LOOP SCORE ? ; PERFECT ⏎
ok

Success!

Getting Numbers From the Input Stream

To get a number, we have to read the input stream character by character, skipping them until we find a digit, then reading characters while these are digits, accumulating them into the resulting number.

The standard word DIGIT? ( char -- n,-1|0 ) returns false if the character on the stack is not a digit, or true, preceded with the matching digit otherwise.

    CHAR # DUP . DIGIT? .  ⏎
    35 0  ok
    CHAR 2 DUP . DIGIT? . .   ⏎
    50 -1 2  ok

Here’s a word to skip all input characters until a digit is met:

: SKIP-NON-DIGIT ( -- n )
    BEGIN KEY DIGIT? 0= WHILE REPEAT ;

And here’s a word to get a number:

: GET-NUMBER ( -- n )
    0 SKIP-NON-DIGIT
    BEGIN
        SWAP 10 * +
        KEY DIGIT?
    0= UNTIL ;

    GET-NUMBER . ⏎
    foo4807  ⏎
    4807 ok

Main program

Armed with this word, we can now add the top definition to our program:

: BOWLING
    GET-NUMBER 0 DO
        START
        GET-NUMBER 0 DO
            GET-NUMBER ROLL+
        LOOP
        SCORE ? CR
    LOOP ;

The last commands in the program will execute our BOWLING word and leave gforth:

BOWLING
BYE

Testing

Let’s put our program to test. Given the this input file:

# input.dat: a test file for Bowling.fs
    5
    4
    3 5 2 7
    6
    10 5 4 10 5 2
    12
    10 10 10 10 10 10 10 10 10 10 10 10
    20
    3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5
    3
    10 10 10

The following result is obtained:

    gforth Bowling.fs <input.dat ⏎
    17
    52
    300
    80
    60

Et voilà! The Bowling Score Kata, in Forth.

The Program

The program and tests can be found here

\ Bowling.fs          gforth Bowling.fs <input.dat
VARIABLE SCORE
VARIABLE BONUS
VARIABLE FRAME#
VARIABLE FRAME

: START
    0 SCORE !
    0 BONUS !
    0 FRAME# !
    0 FRAME ! ;

: SPARE \ set the bonus to 1, no supplement
    1 BONUS ! ;

: STRIKE \ increase bonus, and set supplement to 1
    BONUS @ 1+ 4 OR BONUS ! ;

: BONUS> ( -- n ) \ produce bonus factor, get supplement ready
    BONUS @ DUP 3 AND
    SWAP 2/ 2/ BONUS ! ;

: COLLECT-BONUS ( #pins -- ) \ add extra points to score and advance bonus
    BONUS> * SCORE +! ;

: FRAME#> \ advance frame count
    FRAME# @ 1+ 10 MIN FRAME# ! ;

: OPEN-FRAME? ( -- ? )
    FRAME @ ;

: CLOSE-FRAME \ close frame and increment frame count
    0 FRAME ! FRAME#> ;

: NEW-FRAME? ( -- ? )
    OPEN-FRAME? 0= ;

: OPEN-FRAME ( #pins -- ) \ open frame, saving 1st roll value+1
    1+ FRAME ! ;

: LAST-ROLL ( -- #pins ) \ retrieve the first roll value
    FRAME @ 1- ;

: CHECK-STRIKE ( #pins -- )
    DUP 10 = IF
        DROP STRIKE CLOSE-FRAME
    ELSE
        OPEN-FRAME
    THEN ;

: CHECK-SPARE ( #pins -- )
    LAST-ROLL + 10 = IF SPARE THEN
    CLOSE-FRAME ;

: CHECK-BONUS ( #pins -- )
    NEW-FRAME? IF CHECK-STRIKE ELSE CHECK-SPARE THEN ;

: ROLL+ ( #pins -- )
    DUP COLLECT-BONUS
    FRAME# @ 0 10 WITHIN IF
        DUP SCORE +!
        CHECK-BONUS
    ELSE
        DROP
    THEN ;

: SKIP-NON-DIGIT ( -- n )
    BEGIN KEY DIGIT? 0= WHILE REPEAT ;

: GET-NUMBER ( -- n )
    0 SKIP-NON-DIGIT
    BEGIN
        SWAP 10 * +
        KEY DIGIT?
    0= UNTIL ;

: BOWLING
    GET-NUMBER 0 DO
        START
        GET-NUMBER 0 DO
            GET-NUMBER ROLL+
        LOOP
        SCORE ? CR
    LOOP ;

BOWLING
BYE

The Problem to Solve

Specifications

Input

Output

Example

Input

Output

Solving it with Forth

Main Routine

Keeping the Score

Bonus

Collecting Bonus

Frame Count

Frame State

Checking for Bonus

Adding a Roll to the Current Score

Getting Numbers From the Input Stream

Main program

Testing

The Program

Christophe Thibaut est un coach XP, un consultant avec plus de 30 ans d'expérience dans le développement logiciel, le leadership technique, le conseil et le coaching. Il aide ses clients à améliorer leurs pratiques et à résoudre des problèmes complexes ensemble.