Problem

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.

Examples

Example 1:

Input: code = '123456', guess = {175286: 2, 293416: 3, 654321: 0}
Output: True

Example 2:

Input: code = '123456', guess = {123456: 4, 345678: 4, 567890: 4}
Output: False

Solution

Method 1 - Backtracking

To solve this problem, we need to check if there exists any six-digit number with distinct digits that matches all the given guesses with the specified number of correct positions. This is effectively a constraint satisfaction problem, where we systematically check each potential secret code to see if it satisfies all the given conditions.

Here are the steps we can take:

  1. Generate All Possible Secret Codes:
    • As the secret code is a six-digit number with all distinct digits, we can generate all permutations of the digits 0 through 9, selecting only those with six digits.
  2. Validate the Secret Code:
    • For each generated secret code, compare it with each guess to check if the number of correctly positioned digits matches the given score.
  3. Output the Result:
    • If we find at least one secret code that satisfies all conditions, return True. Otherwise, return False.

Code

Java
public class MastermindSolver {

	public boolean isPossibleSecretCode(Map<Integer, Integer> guesses) {
		// Generate all permutations of 6 distinct digits
		List<String> permutations = generatePermutations("0123456789");

		for (String secretCode: permutations) {
			boolean valid = true;

			for (Map.Entry<Integer, Integer> entry: guesses.entrySet()) {
				String guess = String.valueOf(entry.getKey());
				int expectedScore = entry.getValue();
				int actualScore = getScore(secretCode, guess);

				if (actualScore != expectedScore) {
					valid = false;
					break;
				}
			}

			if (valid) {
				return true;
			}
		}

		return false;
	}

	// Generate all permutations of the given string
	public List<String> generatePermutations(String s) {
		List<String> permutations = new ArrayList<>();
		permute(s.toCharArray(), 0, 6, permutations);
		return permutations;
	}

	// Helper method to generate the permutations via backtracking
	private static void permute(char[] arr, int index, int length, List<String> permutations) {
		if (index == length) {
			permutations.add(new String(arr, 0, length));
			return;
		}

		for (int i = index; i < arr.length; i++) {
			swap(arr, i, index);
			permute(arr, index + 1, length, permutations);
			swap(arr, i, index);
		}
	}

	// Helper method to swap characters in an array
	private void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// Calculate the score of a guess based on its comparison with the secret code
	public int getScore(String secret, String guess) {
		int score = 0;

		for (int i = 0; i < secret.length(); i++) {
			if (secret.charAt(i) == guess.charAt(i)) {
				score++;
			}
		}

		return score;
	}

	public static void main(String[] args) {
		Map<Integer, Integer> guesses1 = new HashMap<>();
		guesses1.put(175286, 2);
		guesses1.put(293416, 3);
		guesses1.put(654321, 0);

		Map<Integer, Integer> guesses2 = new HashMap<>();
		guesses2.put(123456, 4);
		guesses2.put(345678, 4);
		guesses2.put(567890, 4);

		System.out.println(isPossibleSecretCode(guesses1)); // Output: True
		System.out.println(isPossibleSecretCode(guesses2)); // Output: False
	}
}
Python
from itertools import permutations


def is_possible_secret_code(guesses):
    for perm in permutations("0123456789", 6):
        secret_code = "".join(perm)
        # Check if this secret code matches all the given guesses and scores
        if all(
            score == sum(sc == g for sc, g in zip(secret_code, str(guess)))
            for guess, score in guesses.items()
        ):
            return True
    return False


# Example usage:
guesses1 = {175286: 2, 293416: 3, 654321: 0}
guesses2 = {123456: 4, 345678: 4, 567890: 4}

print(is_possible_secret_code(guesses1))  # Output: True
print(is_possible_secret_code(guesses2))  # Output: False

Complexity

  • ⏰ Time complexity: O(G), where G is number of guesses
    • For a 6 digit number, we generate permutations = ${n}P{k}=\frac{n!}{(n - k)!}$ =  $\frac{10!}{4!} = 151,200$.
    • O(6 * 151200) for generating each permutation requires a swap operation and backtracking through the digits.
    • O(151200 * G * 6) for checking each permutation, and it involves comparing two 6-digit numbers
    • To sum up - O(151200 + 151200 * G + 6) = O(G)
  • 🧺 Space complexity: O(G)
    • We generate and store up to 151,200 six-digit numbers, hence O(151200 * 6) = O(906000)
    • Storing the guesses and their scores takes O(G) time