[Solution]Mastermind Code Decoding [Facebook]
Greedy Algorithms, Brute Force, Combinations, Mastermind, Decoding, Dictionaries
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?
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.