The most recent project that I worked on was building a version of the classic game Mastermind. For those of you who are not familiar, Mastermind is a code-breaking game. This article’s focus will be on the logic I wrote to check whether or not the code had successfully been broken.
In the traditional two-player version of Mastermind, one player creates a secret code of four characters(usually different colored balls) and arranges it on a part of the board that is not visible to the other player. The second player’s job is to crack the secret code, and they get 10 guesses to do so. After each guess, the player who made the code will give the other player feedback on their guess. For each item in the guess, one of the following three pieces of feedback will be given:
- This item is in the secret code and it is in the right place.
- This item is in the secret code but not in the right place.
- This item is not in the secret code at all.
Using this feedback, the guessing player needs to narrow down the possibilities and guess the code before running out of guesses. One other important thing to note is that the order that the feedback appears in should have nothing to do with the order of the code or the guess, as this would make it too easy. The board game version typically looks something like this:
The larger circles are where the guessing player puts their guesses, and the smaller ones on the left are where the feedback goes. While the aesthetics are a little bit outside the scope of this article, I think are valuable in a brief explanation of the game like this one. Without further ado, I’ll get into how I “cracked the code.”
Before writing a function to determine whether a guess is accurate, I needed to figure out how to represent the secret code and guesses. I decided to use arrays for both. They are simple data structures, and I have a lot of experience manipulating and comparing them. So, this function needs to take two arrays as arguments and then return feedback based on how those arrays compare to each other. It seemed simple enough, but it took me a lot of time and several frustrating edge cases to realize the nuances of this problem. Here is my initial solution.
If we ignore the React syntax like setting state, this function boils down to something like this:
- Create variables to keep track of when an item is completely correct or partially correct.
- Create an object to return both the guess and the feedback at the end of the function.
- Begin a for loop that will check whether there are any indexes that are equal in both arrays, or whether there are any elements in the guess that are included in the code but not at the correct index, and update the variables we declared earlier accordingly.
- Once we know how many are correct and how many are included, we can determine how many are wrong by subtracting the total or correct and included characters from the total of 4.
- Return the feedback.
For a while, I thought that this was working as I had hoped. It wasn’t until I tested it very thoroughly that I realized there was a big problem. Let’s say the secret code was “1,2,3,4” and the guess was “1,1,1,1”. The function above would return that there was one fully correct answer, and three that are included but not in the right place. This stumped me for a while, and I decided that I needed to find a way to make sure that the same index would not be checked twice if it was completely correct.
While working on various iterations of this function, I found myself running into a problem. I was writing nested loops, and needed a way to exit the inner loop back to the outer loop if a certain condition was met. I had no idea how to do this, so I took a break from writing the function to do some research. After a bit of digging, I discovered what I had been looking for, the continue statement. as usual, MDN does a great job of explaining how this works. While I’m slightly embarrassed that I did not know about continue before, all that matters is that now I do. I’m not even sure how many leetcode problems have made me want this feature, but it has been a ton of them. Below is the solution that I came to after a ton of work.
Here is a summary of how this function works.
- Run a for loop to find any items in the guess that are both included and in the right place. If any are found, push the appropriate feedback to the feedback array, and set the element at that index in both the guess and the code to -1.
- Once the first loop is done, enter another for loop and create a boolean variable that is initialized as true. If this doesn’t make sense yet, bear with me. If the element in the code at the current index being checked is equal to -1, continue.
- If the continue statement is not triggered, enter another for loop, this time iterating through the guess with the variable named ‘j’ instead of ‘i.’ If the guess at index j is equal to -1, continue.
- If this second loop makes it past the continue statement, it means that both loops are currently at an index that is not -1. So, we can check if the code at the index of i is equal to the guess at the index of j. If so, we can push the appropriate feedback to the feedback array, set guess[j] equal to -1, and set our boolean variable to false. Then, we break out of the inner loop back to the outer one.
- At the end of each iteration of the outer loop, if the boolean variable(I named it “notIncluded” is true, that means that it’s corresponding guess is not in the code. If it were, it would have been set to -1 in one of the loops and set to false.
I hope that you enjoyed this article and my solution to this problem!