Cows and Bulls - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To return the hint for a guess in the format "xAyB", where x is the number of bulls and y is the number of cows.
  • What input is provided?
    • Two strings, secret and guess.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Count the bulls in the first pass and the cows in the second pass using Counter.

1) Initialize `bulls` and `cows` to 0.
2) Initialize two frequency dictionaries `secret_count` and `guess_count`.
3) First pass: Count the bulls and populate the dictionaries for non-bull characters.
4) Second pass: Count the cows by finding the minimum count of matching characters in `secret_count` and `guess_count`.
5) Return the result as a string in the format `"xAyB"`.

⚠️ Common Mistakes

• Miscounting cows by not properly excluding bull positions.

I-mplement

def get_hint(secret, guess):
    bulls = 0
    cows = 0
    
    # Manually count the frequency of each character in secret and guess
    secret_count = {}
    guess_count = {}
    
    # First pass to count bulls and populate the dictionaries
    for i in range(len(secret)):
        if secret[i] == guess[i]:
            bulls += 1
        else:
            # Update the count for the character in secret
            if secret[i] in secret_count:
                secret_count[secret[i]] += 1
            else:
                secret_count[secret[i]] = 1
            
            # Update the count for the character in guess
            if guess[i] in guess_count:
                guess_count[guess[i]] += 1
            else:
                guess_count[guess[i]] = 1
    
    # Second pass to count cows
    for char in guess_count:
        if char in secret_count:
            cows += min(secret_count[char], guess_count[char])
    
    return f"{bulls}A{cows}B"