# "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"

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++){
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)){
}
}


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 a linked list instead of a vector, then erasure is much cheaper. Or copy just the eligible solutions to a brand new vector. Either one avoids the expense of copying elements down to fill in each erased space. Commented Feb 4, 2012 at 4:23
• After what I heard at Going Native, I would challenge this assertion and say test it first. Lists according to those exalted souls, are going to be slower due to cache and traversal issues.
– Michael Dorgan
Commented Feb 4, 2012 at 4:51
• Erase does not need to be expensive. The version implemented by std::vector<> is because it has some extra constraints that you do not need. A cheap way to remove an element swap it with the last element and then re-size the vector to 1 smaller. Thus erasing is the cost of a single copy. Commented Feb 4, 2012 at 17:37

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)

• Arrays are non copyable. So this involves more work. The cost of copying a string is not that much more (n + 3 pointers) and if the optimizer spots it only actually requires copying three pointers. array memory is the same as pointer memory there is no difference to the machine in terms of de-referencing and using high performance instructions. Though you would potentially gain in code locality. Commented Feb 4, 2012 at 18:14
• @LokiAstari What does this mean: "Arrays are non copyable"? Commented Feb 6, 2012 at 20:32
• @Thomas I can not comment on your "use a vector<bool>" suggestion ( codereview.stackexchange.com/a/8658/10800 ). So I shall comment here. Do you suggest to re-generate each of solution "on the fly" while pruning? If so, this will be much slower than to sequentially read eligible solutions from the memory -- DDR3 sequentional memory read rate is around 16 GB/s, that is, around 2GT/s of 8-byte solutions. (So, the next optimization target is calculation of cows. For the memory read rates you may look at, say, zsmith.co/bandwidth.html ) Commented Feb 6, 2012 at 20:56
• I made a mistake about array copying: stackoverflow.com/q/9167253/14065 Commented Feb 6, 2012 at 21:21

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.

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)){


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)){

var size = Hunter.size();