[Solution]Mastermind Code Decoding [Facebook]

Greedy Algorithms, Brute Force, Combinations, Mastermind, Decoding, Dictionaries

Dec 10, 2021

Problem

This problem was asked by Facebook.

Mastermind is a two-player game in which the first player attempts to guess the secret code of the second. In this version, the code may be any six-digit number with all distinct digits.

Each turn the first player guesses some number, and the second player responds by saying how many digits in this number correctly matched their location in the secret code. For example, if the secret code were 123456, then a guess of 175286 would score two, since 1 and 6 were correctly placed.

Write an algorithm which, given a sequence of guesses and their scores, determines whether there exists some secret code that could have produced them.

For example, for the following scores you should return True, since they correspond to the secret code 123456:

{175286: 2, 293416: 3, 654321: 0}

However, it is impossible for any key to result in the following scores, so in this case you should return False:

{123456: 4, 345678: 4, 567890: 4}

Step 1: Simple Solution

Here we go with the simplest solution we can come up with. In out case, it happens to be a brute force solution. Why is this a step? After all, to do well in your coding interviews, you need an optimal solution (sorry but the competition is insane. To get a good tech company, you need to be perfect).

Notice how the student specifically mentions the process of exploring constraints and working with small cases being helpful to her. Often small brute force simulations will help you see the pattern required to optimize.

By going brute force first you have 3 advantages:

You don’t freeze up and have something. This is important because, at the end of the day, you have to impress your interviewer.
To optimize solutions, brute force approaches can provide helpful hints. Optimizing is often just doing away with the extra steps.
It helps you come across as organized. Also VV imp for impressing.

So how does our brute force work?

Brute Force

We can first write every possible secret code, from 012345 to 987654. Next, we iterate through these codes one by one and check if they correctly match the score for each guess. If we find a successful code, we can return True, otherwise, we will return False.

Instead of coding this up, we can save ourselves some time. For example, we are given some constraints that make life easier. Note that after each guess, we can narrow down the set of possible codes to those that match the corresponding score. This way, each subsequent guess will take less time to evaluate.

Second, we can begin our pool of possible codes with only those that satisfy our most restrictive guess. Instead of iterating through every code to see whether it satisfies this guess, though, we can do this constructively.

For example, suppose our guess is 123456 and its score is five. Then only one of the indices is incorrect, and it must be replaced by some other digit. These replacement digits, however, must not duplicate an existing digit. Therefore, we end up restricting our set of possible codes to the following:

[7/8/9]23456, 1[7/8/9]3456, 12[7/8/9]456, 123[7/8/9]56, 1234[7/8/9]6, 12345[7/8/9]

How much does this matter? Using the first guess, we have narrowed

down the pool of possible solutions from 10^6 to 3^6. How do we calculate this?

Lmk if you want a breakdown of the math in the comments , and I’ll put it in.

Code

from itertools import combinations, permutations, product

def corresponds(guess, code, score):
    correct = 0

    for guess_digit, real_digit in zip(guess, code):
        if guess_digit == real_digit:
            correct += 1

    return correct == score

def get_candidates(guess, score, possible_codes):
    return [code for code in possible_codes if corresponds(guess, code, score)]

def generate_codes(guess, score):
    codes = []

    # Find each possible set of incorrect indices.
    wrong_indices = combinations(range(6), 6 - score)

    # For each set, build a list of all possible digits at each index.
    # For a "correct" index, the only possible digit is the existing one.
    # For an "incorrect" index, we allow any digit from 0-9 except the current one.
    # Finally, perform a Cartesian product to get the possible combined numbers.
    for indices in wrong_indices:
        digits = []

        for index in range(6):
            if index not in indices:
                digits.append([int(str(guess)[index])])
                continue
            else:
                digits.append([x for x in range(10) if x != str(guess)[index]])

        codes.extend([''.join(map(str, num)) for num in product(*digits)])

    # Ensure that all digits are distinct before returning.
    return [code for code in codes if len(set(code)) == 6]

def is_possible(scores):
    # Sort the scores so the most correct guesses come first.
    scores = sorted(scores.items(), key=lambda x: x[1], reverse=True)

    # Start a pool of possible codes which satisfy the first guess.
    possible_codes = generate_codes(*scores[0])

    # Narrow down this pool of possible codes with each guess.
    for guess, score in scores[1:]:
        possible_codes = get_candidates(str(guess), score, possible_codes)

    # Any remaining codes could have produced this game.
    return True if possible_codes else False

With combinatorics problems, it can be difficult to have precise time complexity. And it is possible to come up with a pathological input where these changes result in no improvement: for example, consider N identical guesses, each of which has a score of zero.

Does this mean we don’t calculate it? No. We can do some calculations.

We know our time is bounded on the lower end by O(N*log(N)) for N guesses. This is because we are sorting through the scores dictionary. We are also at least using linear extra space since we are generating codes.We can compute more exact bounds using math, but DM me if you want a breakdown of that.

Bonuses/Promotion (Get Free Stuff)

Have anything to say to me? Use the links below.

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

Technology Made Simple

Discussion about this post