"Bulls and cows" algorithm

Question

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.

Answer 1

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

2. 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)

Answer 2

Instead of using a vector<string>, use a vector<bool> of constant size, 10000 elements. Element 0 represents answer 0000, and so on, up to 9999. Set all to true initially, except those containing the same digit more than once, and simply flip the bits to false when you've eliminated a particular option.

A vector<bool> has a specialized implementation (the source of much complaint) that packs bits tightly, so it takes only 10000 bits, or approximately 1.2 kB. More importantly, "deletions" are done in constant time.

Answer 3

First comment your variable names are horrible which makes reading the code really hard.

Where:

for(int h=0; Hunters.size() > 1; h++){

• What is h supposed to represent?
• Why is h not part of the condition?
  Since h is not part of the loop you should remove it from the loop construct, which turns this into a while.

Do you really want to make a copy of the string here

    string guess = Hunters.at(0);

    // make it a const reference
    // You are not altering the gurss and you don't need a copy.
    string const& guess = Hunters.at(0);

Curios why you decided to count down.
There does not seem a need for it, counting up is more natural and easier to reason about so you should prefer it when you can.

    for(int i=Hunters.size()-1; i >= 0; i--){

Please declare one variable to a line.

        int pl = 0, fl = 0;

And give those variables meaningful names so we can see what is happening. I have no idea how these two related to bulls/cows/ position in hunters/size of other stuff. Without this context the code is nearly indecipherable. Something that should be obvious at a glance takes 5 minutes of head scratching to understand.

There is something wrong here:

        for (unsigned int ix = 0; ix < Hunters.size(); ix++){
            if(Hunters[i].at(ix) == guess.at(ix))    pl++;
        }

The variable ix is ranging over the size of the array. But is used as index into individual members of the attar (luckily you used at() to generate the appropriate exceptions). Maybe if you had given them reasonable names that would have been easier to spot.

OK. Erasing from a vetor can be expensive. Especially one as large as you claim.

if((pl != P.p) || (fl != P.f)){
       Hunters.erase(cazadores.begin()+i);}

But you have not inherent ordering on the array so you can make this a lot less costly to do (but you would need to invert the above loop so it counts up rather than down).

 if (testToKeep())
 {
       ++hunterIndex;  // Move to the next element.
                       // OK: That name is a bit long for a loop variable.
                       //     But its intent is clear. `huntIdx` would do.
 }
 else
 {
     hunters[hunterIndex].swap(hunters[hunters.size()-1]);
     hunters.resize(hunters.size()-1);

     // Note: We do not increment the loop here
     //       This is because we have a new value to test
     //       at the current location and the size of the array
     //       has decreased thus effectively moving us one closer
     //       to the end.
 }

I can forgive putting the '{' on the wrong line as about 30% of developers prefer that way (the other 30% prefer to line up open and close and the final 40% don't care (as long as you consistent)).

if((pl != P.p) || (fl != P.f)){
       Hunters.erase(cazadores.begin()+i);}

But please put the closing brace '}' underneath. There is absolutely no need for this insane attempt at saving space and making the code unreadable. Also this would make it consistent with the rest of your code (which is much more important).

Answer 4

You are using Hunter.size() function at various places(that too inside a for loop). You could at the begining store it in a variable(like below) and then use it.It will decrease the overhead of a function call in a loop.

var size = Hunter.size();