Mastermind Challenge Implementation

Introduction

This challenge requires defeating a number of gladiators with a larger set of weapons. Each gladiator can only be defeated by a specific weapon, and all gladiators must be defeated at once to complete a level. There are limited guesses, but on each guess we receive back both how many weapons were correctly chosen and how many were chosen for the right gladiator. We are not given the specific gladiators that the weapons were correctly chosen for, but weapons also cannot be reused for other gladiators within the same round.

If this sounds confusing, it’s basically like a slightly modified version of Wordle. There are three key differences:

  1. The specific letters that can be used are limited and given to us beforehand.
  2. A letter can only be used once. For example, HELLO is not a valid guess since ‘L’ is used twice.
  3. Wordle highlights letter positions as Yellow (letter is in the word) or Green (letter is in the right place). We are only given the number of Yellows and Greens per guess, but not specifically where they are.

Methodology

There is a way to do this deterministically. We must first find the weapons (letters) that are used in general, and then find the correct permutation of the letters using the information given to us.

Filtering Combinations

We can start off by creating every combination of weapons and start guessing by picking a random one. As we guess, we can start to filter out combinations using their response. As we continue to filter out combinations and pick a random one, we will quickly get to the right combination.

One thing to note here is before we guess, we can shuffle the letters within our prediction. This increases the entropy for all of our guesses, and provides us more information for the number of correct places. In the context of Wordle, guessing SHARK and then SHARE gives us less info than SHARK and then HARES, since the second guess now checks the letters in different places.

Filtering Permutations

Once we get the correct combination, we can create all the possible permutations and then use all of our previous guesses and history of correct places to filter out the permutations that don’t work for our scenario. This is where shuffling the combinations becomes key, because we have extra information to filter out words.

We can continue the process of guessing and filtering until we find the right answer!

Implementation

This is my implementation in Python of the algorithm. I did have to create a good amount of member variables in the constructor to hold all the necessary information.

import random
from itertools import combinations, permutations


class Mastermind:
    def __init__(self, numGladiators, numWeapons):
        """
        Initializes the Mastermind game with the specified number of gladiators and weapons.

        Args:
            numGladiators (int): The number of gladiators in the game.
            numWeapons (int): The number of different weapons available.

        Attributes:
            numGladiators (int): Stores the number of gladiators.
            numWeapons (int): Stores the number of weapons.
            guess_history (list): Keeps track of all the guesses made.
            place_history (list): Keeps track of the history of correct places.
            combos (iterator): An iterator for all possible combinations of weapons.
            perms (set): A set to store permutations of the correct combination.
        """
        self.numGladiators = numGladiators
        self.numWeapons = numWeapons
        self.guess_history = []
        self.place_history = []
        self.combos = combinations(range(self.numWeapons), self.numGladiators)
        self.perms = set()

    def predict(self, obs):
        """
        Predicts the next guess based on the observation of correct numbers and correct places.

        Args:
            obs (tuple): A tuple containing two elements:
                - correct_numbers (int): The number of correct numbers in the previous guess.
                - correct_places (int): The number of correct numbers in the correct places in the previous guess.

        Returns:
            tuple: The next predicted guess as a tuple of integers.
        """
        correct_numbers = obs[0]
        correct_places = obs[1]

        # If no guesses have been made, make a random guess
        if not self.guess_history:
            prediction = random.sample(range(self.numWeapons), self.numGladiators)
            prediction = tuple(prediction)

        # If the correct numbers are not equal to the number of gladiators, filter the combinations
        elif correct_numbers != self.numGladiators:
            self.place_history.append(correct_places)
            prev = self.guess_history[-1]
            self.combos = set(
                filter(
                    lambda x: len(set(x) & set(prev)) == correct_numbers, self.combos
                )
            )
            prediction = random.choice(list(self.combos))
            # Shuffle the prediction to get more information for correct places
            prediction = list(prediction)
            random.shuffle(prediction)
            prediction = tuple(prediction)

        # If the correct numbers are equal to the number of gladiators, filter the permutations
        else:
            # If no permutations have been stored, generate all permutations
            if not self.perms:
                self.place_history.append(correct_places)
                for perm in set(permutations(self.guess_history[-1])):
                    for guess, n in zip(self.guess_history, self.place_history):
                        if sum(g == a for g, a in zip(guess, perm)) != n:
                            break
                    else:
                        self.perms.add(perm)
            # Otherwise, filter the permutations based on the correct places
            else:
                prev = self.guess_history[-1]
                self.perms = set(
                    filter(
                        lambda x: sum(g == a for g, a in zip(x, prev))
                        == correct_places,
                        self.perms,
                    )
                )
            prediction = random.choice(list(self.perms))

        self.guess_history.append(prediction)
        return prediction

Usage

Make a POST request to get an auth token for your email.

import requests, json
email = 'YOUR_EMAIL_HERE'
r = requests.post('https://mastermind.praetorian.com/api-auth-token/', data={'email':email})
r.json()
{'Auth-Token': 'YOUR_AUTH_TOKEN'}

Start with the first level, and make a GET request to get level-specific info.

l = 6
headers = r.json()
headers['Content-Type'] = 'application/json'
# Interacting with the game
r = requests.get(f'https://mastermind.praetorian.com/level/{l}/', headers=headers)
level = r.json()
level
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10}

Since there can be multiple rounds, use a while loop to keep guessing until you finish all the rounds.

while level["numRounds"] > 0:
    model = Mastermind(level["numGladiators"], level["numWeapons"])
    obs = [0,0]
    action = model.predict(obs)
    while obs:
        r = requests.post(f'https://mastermind.praetorian.com/level/{l}/', data=json.dumps({'guess':action}), headers=headers)
        if "response" not in r.json():
            print(r.json())
            break
        obs = r.json()["response"]
        # > {'response': [2, 1]}
        action = model.predict(obs)
    level["numRounds"] -= 1
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 9}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 8}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 7}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 6}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 5}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 4}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 3}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 2}
{'numGladiators': 5, 'numGuesses': 7, 'numRounds': 10, 'numWeapons': 10, 'roundsLeft': 1}
{'hash': 'YOUR_HASH_HERE', 'message': 'Congratulations!'}

We completed the challenge and got our hash!