Mastermind hint

See the original problem on HackerRank.

Solutions

A simple solution involves counting the exact matches by checking positions where both strings have the same digit, indicating correct digits in the correct places. To find misplaced digits, it counts digits that appear in both strings but at different positions, subtracting the exact matches count to avoid double counting:

Here is a Python example:

1
2
3
4
5
6
def mastermind(secret: str, guess: str) -> (int, int):
    exact = sum(s == g for s, g in zip(secret, guess))
    secret_count = Counter(secret)
    guess_count = Counter(guess)
    misplaced = sum((secret_count & guess_count).values()) - exact
    print(f"{exact} {misplaced}")

The expression secret_count & guess_count creates a new Counter containing only the keys (digits) that appear in both, and for each key, the count is the minimum of the counts in the two counters. This helps us count how many digits occur in both strings regardless of position. We subtract the exact matches from this intersection to get the count of correct digits in wrong positions.

This solution is concise and efficient but requires multiple passes over the data. Alternatively, we can use a single-pass approach: as we iterate through both the secret and guess simultaneously, we count exact matches immediately when digits match at the same position. For misplaced digits, we keep track of the counts of each digit seen so far in both secret and guess using an array. When encountering a digit, we increment the misplaced count if the digit has already appeared in the opposite string, effectively detecting misplaced matches on the fly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    string secret, guess;
    cin >> secret >> guess;
    array<int, 10> freq{};
    auto exact = 0, misplaced = 0;
    for (size_t i=0; i<secret.size(); ++i)
    {
        if (secret[i] == guess[i])
        {
            ++exact;
        }
        else
        {
            if (freq[secret[i]-'0']++ < 0)
                ++misplaced;
            if (freq[guess[i]-'0']-- > 0)
                ++misplaced;
        }
    }
    cout << exact << " " << misplaced;
}
comments powered by Disqus