Checking a mastermind answer as fast as possible

Question

This is not your typical mastermind question, I am not trying to find the right answer. Merely to check the answer and provide a result as fast as possible. The function signature cannot be changed, however the contents are just my best guess. Here's what I've come up with :

typedef int Code[100]; /* Arbitrary size */

void check_answer(
    int        code_length, /* Effective length of the code */
    const Code answer,      /* Answer to check */
    const Code code,        /* The actual code */
    int        *black,      /* Returns count of right digits in right place */
    int        *white       /* Returns count of right digits in wrong place */
) {
    Code code_mask;   /* Masks already-matched digits of the actual code */
    Code answer_mask; /* Masks already-matched digits of the answer code */
    int i, j;

    *black = 0;
    *white = 0;

    /* Count black pegs */
    for ( i = 0; i < code_length; i++ ) {
        if ( answer[ i ] == code[ i ] ) {
            *black          += 1;
            code_mask[ i ]   = 1;
            answer_mask[ i ] = 1;
        } else {
            code_mask[ i ]   = 0;
            answer_mask[ i ] = 0;
        }
    }

    /* Count white pegs */
    for ( i = 0; i < code_length; i++ ) {
        if ( answer_mask[ i ] ) continue; /* Skip already matched */
        for ( j = 0; j < code_length; j++ ) {

            /*
                Skip already-matched or same-index :
                If mask is 0, same-index is necessarily different
            */
            if ( code_mask[ j ] || i == j ) continue;

            if ( answer[ i ] == code[ j ] ) {
                *white += 1;
                code_mask[ j ] = 1; /* Mask code only, previous answer_mask entries are never used again */
                break; /* Answer digit is matched, skip to next */
            }
        }
    }
}

Context : In this exercise, the solver algorithm uses this same function to check whether each potential next guess, were it to be the actual code, would produce the same answers for previously submitted guesses. Once it finds such a guess, it submits it to be tested against the real code.

The goal is to be as fast as possible with this algorithm structure, the check_answer function being the critical hot-path. For a 12-color 9-digit code, it is called in the order of 10 billion times.

Answer 1

There's some low-hanging fruit getting rid of an if/else:

    for ( i = 0; i < code_length; i++ ) {
        int r = ( answer[ i ] == code[ i ] );
        *black          += r;
        code_mask[ i ]   = r;
        answer_mask[ i ] = r;
    }

UPDATE:
Having had some time to kill, below is code for the game "mastermind" that uses lowercase alpha characters instead of colours. The game reveals the random collection of letters for testing that the somewhat improved tallying of points is easy to test and confirm. I've taken liberties, using character arrays instead of the OP's integer arrays. It should be a small issue to adapt this implementation to suit one's needs.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 6 // "width" of the game board

// Fill array with random collection of chars from 'a' to 'a'+N-1
void gen( char buf[], size_t n ) {
    while( n-- )
        buf[n] = (char)((rand()%N) + 'a');
}

void check_answer( int len, char *poss, char *actl, int *black, int *white ) {
    int a[N] = { 0 }; // tally actual but not guessed
    int g[N] = { 0 }; // tally guessed but not actual

    for( int i = 0; i < len; i++ ) {
        int r = poss[ i ] == actl[ i ]; // matching?
        *black += r;
        a[ actl[i] - 'a' ] += !r; // count not matching
        g[ poss[i] - 'a' ] += !r; // both actual and guessed.
    }

    for( int x = 0; x < len; x++ )
        *white += g[x] < a[x] ? g[x] : a[x]; // credit minimum of guesses
}

int main( void ) {
    srand( time( NULL ) );

    char ans[ N + 1 ];
    gen( ans, N );

    for( int i = 0; i < N; i++ )
        putchar( ans[i] ), putchar( ' ' );
    putchar( '\n' );

    for( ;; ) {
        char guess[ 128 ];

        printf( "Guess: " );
        fgets( guess, sizeof guess, stdin );

        int black = 0;
        int white = 0;
        check_answer( N, guess, ans, &black, &white );
        printf( "black %d, white %d\n", black, white );
    }

    return 0;
}

Play:

d b b d b a  // <== Normally not revealed at the beginning of the game
Guess: cccccc
black 0, white 0
Guess: bddbab
black 0, white 6
Guess: dbbadb
black 3, white 3
Guess: dbbdba
black 6, white 0
Guess:

Because this is a toy written to get the evaluation function to work quickly, error handling has not been given much attention.

If one wants 12 "colours" for a game board of "9 digits", one need only add another #define M 12 and change the applicable Ns to Ms...

Answer 2

The nesting of loops is a danger sign that this scales poorly as code length increases:

for ( i = 0; i < code_length; i++ ) {
    if ( answer_mask[ i ] ) continue; /* Skip already matched */
    for ( j = 0; j < code_length; j++ ) {
        if ( code_mask[ j ] || i == j ) continue;

Since code_length can be anything up to 100, according to the Code typedef, we have around 100² iterations here. (I'd do the move i==j test before the one that indexes code_mask, just as a micro change that a compiler might not be able to spot, if I were keeping that structure)

At this point, if the range of colour choices is reasonable, we want to transform to histograms counting the occurrence of each value in the code and answer. Then the result is the size of intersection of those histograms.

Conveniently, we have the black-counting loop available in which to gather the histogram data:

    /* assume colour values fit in char */
    unsigned code_hist[UCHAR_MAX+1] = { 0 };
    unsigned answer_hist[UCHAR_MAX+1] = { 0 };

    /* Count black pegs */
    for (int i = 0;  i < code_length;  ++i) {
        if (answer[i] == code[i]) {
            ++*black;
        } else {
            ++code_hist[(unsigned char)code[i]];
            ++answer_hist[(unsigned char)answer[i]];
        }
    }

Note that we no longer need the "mask" variables to track what we've already seen.

Counting the white pegs becomes a straightforward loop over the number of colours:

    /* Count white pegs */
    for (unsigned i = 0;  i <= UCHAR_MAX;  ++i) {
        *white += answer_hist[i] < code_hist[i] ? answer_hist[i] : code_hist[i];
    }

However, this is only an improvement when colours are small integers. Otherwise we likely need a full hash-map implementation to store the histograms (and we'd be better off simply sorting the values, and using a modified merge to count matches).