This is a description of how I might write a program, showing how to keep everything under control
The program is going to be a variation on an old pencil-and-paper game called Bulls and Cows, quite popular all over the world under various names
There is also a commercial version called Mastermind which you can buy
But I remember one of the early computer versions called moo
The computer is going to choose a four-digit number, and the player is going to make guesses
The computer will give the player a bull for each correct digit, and a cow for each digit which is correct, but in the wrong place
The aim is to succeed using as few guesses as possible
The program needs to:
Most players start with the interaction
My experience tells me that's a bad idea - you immediately get caught up in messy stuff, and you fail to think straight about the logic
For me, it is clear to start with storage, because everything else depends on it
There are, maybe, 3 obvious ways of storing the secret
As an integer:
int secret = 7132;
As a string:
char secret[] = "7132";
As an array of small integers:
int secret[] = {7, 1, 3, 2};
The program is all about comparing individual digits
The number doesn't come into it
In the mastermind version, colours are used instead of digits, making it much clearer that the secret and guess are just patterns, not numbers
Storing the secret as a (binary) number would make it unreasonably difficult to get at the (decimal) digits, so let's rule that out
Whether it is an array of characters or an array of integers won't make much difference to the logic
But (a) there is a variation on the game with four-letter words, which would be easier with strings and (b) using strings means no conversion is needed to print them out
So, I am going to use strings:
char secret[] = "7132";
I am thinking of this as an array of four symbols which can be manipulated, plus a fifth marker character which helps with printing
So, the secret is a string like "7132"
But then, there are questions that arise about the rules
Are leading zeros allowed, such as "0528"
?
Traditionally the answer is often no, but the Mastermind colour variation suggests yes, and yes is more symmetrical, so I am going to decide yes
Another issue is whether repeated digits are allowed, such as
"7131"
Traditionally the answer is often no, which makes no sense (leading zeros are presumably disallowed because "it is a number", but numbers have repeated digits)
The Mastermind variation allows repeats, and it adds interest to the game, so I am going to decide yes
It is a matter of taste what order to do things in, but I feel I will retain control better if I develop the counting next, until I am absolutely confident about it
The simple cases don't cause trouble:
char secret[] = "7132"; char guess[] = "8125";
This scores one bull for the digit 1
in the right place, and one
cow for the digit 2
in the wrong place
Repeated digits (in the secret or guess) complicate things:
char secret[] = "7132"; char guess[] = "8191";
This scores one bull for the first digit 1
, but it can't
also score a cow for the second digit 1
Each digit in the guess can only count once
There needs to be a method of counting (an algorithm) which works properly
The ideas needed are:
Let's have a go:
int bulls(char secret[], char guess[]) { int count = 0; for (int i=0; i<4; i++) { if (guess[i] == secret[i]) { count++; guess[i] = 'X'; } } return count; }
I could cross out the matched digits of the secret instead, but it seems better to keep the secret intact
It looks as if it might work, but am I sure?
I've written too many lines without compiling and testing
So I've added a one-line main
, and it compiles
int main() { printf("%d\n", bulls("7132", "8151")); }
But running it gives a segfault
Adding some printf
calls shows that the segfault happens
here:
guess[i] = 'X';
It's because I am updating a constant string - that's not allowed because they are read-only
Here's my fixed main
:
int main() { char secret[] = "7132", guess[] = "8151"; printf("%d\n", bulls(secret, guess)); }
This copies the constant strings into variables
Now it works!
The secret
and guess
arrays are updatable
copies of the constant strings
But I'm testing in the wrong way, by printing something out and looking at it
I need to automate the testing
I want to write one line tests:
assert(bulls("7132", "8151") == 1);
But I have to get round the constant string problem if I want nice one-line tests
My testing will be even more compact if I test the bulls and cows at the same time, so perhaps I can aim for:
assert(score("7132", "8151", 1, 0));
The score
function will take the two patterns, and the bulls and
cows scores they ought to produce, and check
Now I can write the score
function to combine the bulls and cows
testing and copy the constant strings
bool score(char s[], char g[], int bs, int cs) { char secret[5], guess[5]; strcpy(secret, s); strcpy(guess, g); return bulls(secret, guess) == bs; // TODO: check cows(secret, guess) == cs }
Now I can set up testing properly (only bulls for now)
void testBulls() { assert(score("7132", "5555", 0, 0)); assert(score("7132", "5535", 1, 0)); assert(score("7132", "7535", 2, 0)); assert(score("7132", "7132", 4, 0)); }
If these work, I will be confident about my bulls
function
It has taken me 30 lines to create a program where I am happy with the shape and progress, and I have one function which I am confident of
So it is a very good thing that I started with something reasonably easy!
But now I have a setup where experimenting with the next function is easy - I have all my tools round me
How difficult is the cows score?
I can assume that the bulls have already been crossed out of the guess, so they won't match anything
So it seems like I just need a double loop which checks whether
guess[i]
matches secret[j]
Here's my cows function:
int cows(char secret[], char guess[]) { int count = 0; for (int i=0; i<4; i++) { for (int j=0; j<4; j++) { if (guess[i] == secret[j]) { count++; guess[i] = 'X'; } } } return count; }
How did I write the cows function?
Yes, I cheated and copy-pasted the bulls function
But I also went through it incredibly carefully to change the things that needed changing
I know from experience how easy it is to use copy-paste and forget to change things
It looks as though it should work
It is a bit subtle, though, because after it finds a match for a guess digit, it keeps searching
But the digit has been turned to 'X'
, so the continued search
should not find anything
The inefficiency from not stopping the search early is negligible
But only proper testing gives true confidence
So, I am going to add a test function:
void testCows() { assert(score("7132", "5555", 0, 0)); assert(score("7132", "5553", 0, 1)); assert(score("7132", "5753", 0, 2)); assert(score("7132", "1723", 0, 4)); }
What's the next step?
It is to test repeated digits and the interaction between the bulls and cows functions
The score function calls bulls first, then cows, so I can just add more tests:
void testBoth() { assert(score("7132", "5151", 1, 0)); assert(score("7132", "1551", 0, 1)); assert(score("7111", "1555", 0, 1)); assert(score("7111", "5515", 1, 0)); assert(score("7111", "1511", 2, 1)); }
The first of the new tests fails!
This is a good thing because (a) it means I have found a problem that I might otherwise have missed and (b) it shows that it was worth adding the new test function
So, how do I find the problem?
First, I comment out the two lines in main
that call the first
two test functions, so that the test which fails is the first one
called
Then I put printf
calls in score
to see what
the variables hold
What I find is that, after calling bulls
and before calling
cows
, the secret and guess are "7132"
and
"5X51"
So, the first digit 1
has been crossed out of the guess, but the
second is still there and scores a cow
I need to think
My strategy of crossing the matched digit out of the guess isn't good enough
But if I cross the matching digit out of the secret as well, then it should work
There is a potential problem
I have spotted a problem
If I hadn't spotted it, it wouldn't have mattered, because I would have found out when the tests still didn't work, but spotting it in advance speeds things up
The problem is that if I cross out with 'X'
in both the secret
and guess, then there is a danger of 'X'
matching
'X'
My fix is to cross out using different letters
int bulls(...) { ... guess[i] = 'G'; secret[i] = 'S'; ... } int cows(...) { ... guess[i] = 'G'; secret[j] = 'S'; ... }
All the tests now pass
For me, that's the hard part of the program done!
Let's sort out the generation of a random secret
A bit of googling shows that for 'unimportant' random numbers, call
srand(time(NULL))
once to initialize the (pseudo)
random number generator from the time of day (in seconds), so you don't get the
same random numbers every time you run the program, and then call
rand
repeatedly to get a random int (0
to RAND_MAX
)
Here's my generate function and change to main
:
void gen(char secret[5]) { for (int i=0; i<4; i++) secret[i] = '0' + rand() % 10; secret[4] = '\0'; } ... int main() { srand(time(NULL)); ... }
Can I test the gen
function?
Yes and no
I can't test the time-of-day business, because I don't know what answers to expect
But if I re-seed the generator with a fixed seed, then it produces the same sequence of random numbers every time, I can use print statements to find out what gets generated, and a test to make sure that it is still working
testGen
That leads to a testGen
function
void testGen() { srand(42); char secret[5]; gen(secret); assert(strcmp(secret, "5096") == 0); gen(secret); assert(strcmp(secret, "3964") == 0); }
I am not testing that "5096"
and "3964"
are 'right'
just that they are the same as last time so I know nothing has become
broken
The rand() % 10
strategy I am using has a very slight bias,
probably negligible compared to the problem of the poor quality of the generator
Generating one number from 0
to 9999
is very
dangerous, as are lots of other techniques you might think of - making mistakes
with random numbers is very easy
Possible improvements are to use a better generator, and/or use a more accurate measure of time
If you are a purist, you may feel that using the time of day is a fudge
You are right, it is
Another possibility is to use crypto-random numbers, but they run out, so should be used sparingly, certainly not for games
A purist strategy for pseudo-random generators is to store the seed in a file, and read it in and write out an updated one every time the game is played
If you already have a file to save game state, this is best
It is time to add a user interface
You should read the input/output chapter of the lecture notes if you want to take this seriously
The logic is something like: in a loop, first read in a guess, then either print the scores, or give a success message and stop
Here's a function for reading a guess:
void read(char guess[5]) { printf("Type in a guess at the four digit number\n"); scanf("%4s%*c", guess); }
I am using scanf
, but I'm using it carefully (%s
because what I'm reading in won't have spaces, %4s
to read a max of
4
characters for safety, %*c
to read in and throw away
the newline)
It is still weak - it fails if someone types more than four characters - I
shouldn't really be using scanf
I want to test the read function, but I am going to have to do it manually, so this goes in my main function:
int main() { char guess[5]; read(guess); printf("The guess just read in is: %s\n", guess); read(guess); printf("The guess just read in is: %s\n", guess); }
I'm calling read
twice, to make sure my handling of newlines
is right
Now I'm going to take out the manual testing, add a report
function for printing scores:
void report(int b, int c) { printf("Your scores are: bulls %d, cows %d\n", b, c); }
I don't think I need to test that explicitly
Now I'm going to add a play
function:
void play() { char secret[5], guess[5]; gen(secret); bool playing = true; while (playing) { printf("For testing only, the secret is: %s\n", secret); read(guess); int b = bulls(secret, guess); int c = cows(secret, guess); if (b == 4) playing = false; else report(b, c); } }
I've included a test printout of the secret for now
Testing by hand reveals that the secret gets corrupted
That's because I'm crossing out digits from it
I can't make a copy of the secret in the bulls
function, say,
because I need the digits to be crossed out when the secret is passed to
cows
So, I'll make a copy of the secret during each round
Testing by hand also reveals that the secret is the same every time
That's because the testGen
function resets the random number
generator
So I'll move the srand(time(NULL))
call after the tests
And I'll take out the All tests passed
printout so testing is
done silently
The change to the play loop is:
void play() { while (playing) { char copy[5]; strcpy(copy, secret); printf("For testing only, the secret is: %s\n", secret); read(guess); int b = bulls(copy, guess); int c = cows(copy, guess); if (b == 4) playing = false; else report(b, c); } }
I hope you can see that a typical program, even a small one, contains a lot of issues
I also hope you can see that tiny functions, frequent compiling, and autotesting, help enormously in programming
The approach gives great confidence, makes you feel in control, and helps you to see your steady progress, with a frequent reward for successful new features