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.
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.
- 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 )
For each test case output one integer: the score made by the player after they played all the rolls in the test case.
3 2 4 6 4 10 7 3 5 12 10 10 10 10 10 10 10 10 10 10 10 10
10 40 300
Solving it with Forth
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.
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
: 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 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 +! ;
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# ! ;
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:
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 ? ⏎ 4 ok 6 ROLL+ SCORE ? ⏎ 10 ok 3 ROLL+ 2 ROLL+ SCORE ? ⏎ 18 ok 10 ROLL+ SCORE ? ⏎ 28 ok 4 ROLL+ 2 ROLL+ SCORE ? ⏎ 40 ok 10 ROLL+ SCORE ? ⏎ 50 ok 10 ROLL+ SCORE ? ⏎ 70 ok 6 ROLL+ 4 ROLL+ SCORE ? ⏎ 96 ok 3 ROLL+ 5 ROLL+ SCORE ? ⏎ 107 ok 10 ROLL+ SCORE ? ⏎ 117 ok 8 ROLL+ 2 ROLL+ 7 ROLL+ SCORE ? ⏎ 144 ok : PERFECT START 12 0 DO 10 ROLL+ LOOP SCORE ? ; PERFECT ⏎ 300 ok
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
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:
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 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