leetCode Question: Bulls and Cows

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number: "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number: "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Analysis:

It is not hard to discover that if we search the number and guess pair, a "bull" is straightforward to check and count, and also once we have a "bull", it can be viewed as "consumed". We don't have to store it anymore and it will not effect the counting for "cows".

Now the only problem is to handle the "cows". We could use hash map (hash table) to store the count numbers in secret and guess, respectively. It is OK to keep one hash table and search the sequence multiple times. Here, we want to search the whole sequence just once for better efficiency, two hash table are kept.

There are several cases when we go through the sequence and compare the number in secret (denoted as s[ ] ) and guess (denoted as g[ ] ), we also denote mp_s as the hash map for s[ ] and mp_g as the hash map for g[ ]:

• s [ i ] == g [ i ], then it is a "cow", just add the cow count.

• s [ i ] != g [ i ], the below 4 sub cases indicated that: We have the number g[ i ] at hand, check if it has occurred in secret. And then we have the number s[ i ] at hand, check if it has occurred in guess.

  • mp_s[ g[i] ] doesn't exist. It means currently g[i] is not a bull, but we are not sure if it is a bull in the future. E.g.,
    s = [1 2 0 3]
    g = [3 2 0 0]
    when i = 0, 1 != 3, 3 is not a bull for now, but 3 is a bull if we search until the end of sequence.
    Thus, we have to save the g[ i ] in mp_g for later.
  • mp_s[ g[i] ] exists and > 0. It means there is a char g[ i ] in the secret sequence, that is a "bull". So we subtract the value stored in mp_s[ g[i] ] and add the bull count. The reason of >0 condition is for the case of duplicates, if we have already consumed a "bull", the key is still there but value might be <= 0.
  • mp_g[ s[ i ] ] doesn't exist. Similarly, we also store the s[ i ] for later. E.g,
    s = [1 8 0 7]
    g = [5 8 1 6]
    when i = 0, s[i] = 1, which has no match, but later when i = 2, g[ 2 ]=1. g[ 2 ] and s[ 0 ] is a "bull".
  • mp_g[ s[i] ] exists and >0.

Code(C++):

class Solution {

public:

string getHint(string secret, string guess) {

int b = 0;

int c = 0;

int mp1[10] = {0,0,0,0,0,0,0,0,0,0};

int mp2[10] = {0,0,0,0,0,0,0,0,0,0};

for (int i=0;i<secret.size();i++){

if (secret[i] == guess[i]) {

b += 1;

}else{

if (mp1[guess[i]-'0']==0){

mp2[guess[i]-'0'] +=1;

}else{

mp1[guess[i]-'0'] -=1;

c += (mp1[guess[i]-'0']>=0);

}

if (mp2[secret[i]-'0']==0){

mp1[secret[i]-'0'] +=1;

}else{

mp2[secret[i]-'0'] -=1;

c += (mp2[secret[i]-'0']>=0);

}

}

}

return to_string(b) + "A" + to_string(c) + "B";

}

};

Code(Python):

class Solution(object):

def getHint(self, secret, guess):

"""

:type secret: str

:type guess: str

:rtype: str

"""

b = 0

c = 0

mp1 = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

mp2 = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

for i in range(len(secret)):

s = secret[i]

g = guess[i]

if s == g:

b += 1

else:

if mp1[g] == 0:

mp2[g] += 1

else:

mp1[g] -= 1

c += mp1[g]>=0

if mp2[s]==0:

mp1[s] += 1

else:

mp2[s] -= 1

c += (mp2[s]>=0)

return str(b) + "A" + str(c) + "B"