Moo

Writing a program

This is a description of how I might write a program, showing how to keep everything under control

The moo game

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

Playing the game

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

Tasks

The program needs to:

Where to start?

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

Keeping a secret

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};

Integer?

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

String or int array?

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

String

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

A rule

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 rule

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

What's next?

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

Simple counting

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

Complex counting

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

Counting algorithm

There needs to be a method of counting (an algorithm) which works properly

The ideas needed are:

  1. cross out digits when they have been matched
  2. count bulls first, so they take precedence

Counting bulls

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

Being sure

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

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

Fix

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

Testing

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

Better testing

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

Here's my score function

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)

Here are my initial tests

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

Review

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

Cows

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]

The cows function

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;
}

Writing technique

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

Does it work?

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

Testing cows

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));
}

Next

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));
}

Test failure

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

Debugging

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

Discovery

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

Thinking

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

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'

Fix

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';
    ...
}

Pass

All the tests now pass

For me, that's the hard part of the program done!

Generate

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)

Generate function

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));
    ...
}

Testing

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

Notes

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

Alternatives

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

UI

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

Read a guess

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

Manual testing

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

Reporting

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

Play

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

Manual testing

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

More manual testing

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

Finished

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);
    }
}

The moral

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