"Bulls and cows" algorithm

Bulls and cows is a variation of the popular game called 'Mastermind', On a sheet of paper, the players each write a 4-digit secret number. The digits must be all different. Then, in turn, the players try to guess their opponent's number who gives the number of matches. If the matching digits are on their right positions, they are "bulls", if on different positions, they are "cows"

Wikipedia page

One method is to generate a list of all possible numbers that could be the answer, then to prune the list by keeping only those numbers that would give an equivalent score to how the last guess was scored. The next guess can be any number from the pruned list.

Either the program guess correctly or run out of numbers to guess, which indicates a problem with the scoring.

This is the implementation for n digits in C++, hunters (the list of all possible numbers that could be the answer) is a vector of string and cows it he function that counts the cows from two numbers:

for(int h=0; Hunters.size() > 1; h++){
    askBullsCows(h);
    string guess = Hunters.at(0);
    for(int i=Hunters.size()-1; i >= 0; i--){
        int pl = 0, fl = 0;
        for (unsigned int ix = 0; ix < Hunters.size(); ix++){
            if(Hunters[i].at(ix) == guess.at(ix))    pl++;
        }
        Cows(i, guess, fl);
        if((pl != P.p) || (fl != P.f)){
           Hunters.erase(cazadores.begin()+i);}
    }
}

Now, hunters (the vector) have more than 150.000 strings and it's too expensive for erase one by one string that couldn't be the answer.

-
Use char[n] instead of string to store each individual solution.

-
Copy just the eligible solutions to a brand new vector (as Ben Voigt said) instead of deletion.

Assume n<=10. So, memory you need is less than 73Mb (i.e. twice 10*10!). Sequential memory access (#2) and avoiding pointer dereference (#1) means high performance on modern DDR memory.

UPDATE: Some notes on random or even non-random, but non-sequentional DDR memory read. Say, four 8-byte reads at addresses 0x8000 0x8100 0x8200 0x8300 will be slower than four 8-byte reads at 0x9000 0x9008 0x9010 0x9018, because in the later case all the data for the last reads (i.e. 0x9008 0x9010 0x9018) are already in processor 32-byte cache line (also, there are 64-byte cache lines in some processors). Each memory read (say, 8-byte read) transfers the whole 32-byte cache line from memory to processor cache.

Next, even the best possible optimizer can not decrease non-sequentional memory access latency (that is, the time between the memory address was calculated and the memory address contents was arrived into the processor)

StackExchange Code Review Q#8656, answer score: 4