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:
- The specific letters that can be used are limited and given to us beforehand.
- A letter can only be used once. For example, HELLO is not a valid guess since ‘L’ is used twice.
- 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!