Leetcode: Guess the Word
Here is the following problem statement:
We are given a word list of unique words where each word is 6 letters long and one word on this list is chosen as the secret word.
The following function returns an integer type representing the number of exact matches of my guess to the secret word. The function returns -1 if the guess is not inside of the wordlist.
For each test case, I have 10 guesses to guess the word and if one of the guesses was the secret, then I pass the testcase. Don't circumvent (find away) over the judge.
The following is an example of the case:
Input: secret = "acckzz" wordlist = ["acckzz", "ccbazz", "eiowzz", "abcczz"]
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in the wordlist.
master.guess("acckzz") returns 6 because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3 because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2 because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4 because "abcczz" has 4 matches.
We found the secret, so we pass the test case.
The solution is as follows.
First of all we cannot guarantee there to be 10 guesses for a word. The intuition here is to take a word from the wordlist and guess it, and get the number of matches for this word, and update the wordlist and keep only the same matches for the guess. The issue is. which word should we guess from the wordlist?
The first function I want to write is the match function in order to match words of particular sequences.
int match(String a, String b){
int matches = 0;
for(int i = 0; i < a.length(); ++i){
if(a.charAt(i) == b.charAt(i)) matches++;
}
return matches;
}
The first solution is to guess a random word inside of the wordlist. There's a master class provided in this module which I will discuss later.
The following is the code enumerated in the problem, It also shows a Java tactic of nested for loops that I have not seen before. Hey, you find something new every day.
The following is the code and the output:
Code:
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* interface Master {
* public int guess(String word) {}
* }
*/
class Solution {
public void findSecretWord(String[] wordlist, Master master) {
//number of guesses
for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
System.out.println("Word list: " + Arrays.toString(wordlist));
System.out.println("i: " + i);
String guess = wordlist[new Random().nextInt(wordlist.length)];
System.out.println("guess: "+ guess);
x = master.guess(guess);
System.out.println("x: " + x);
List<String> wordlist2 = new ArrayList<>();
for (String w : wordlist){
System.out.println("Guess: " + guess + " W: " + w + " Match: " + match(guess,w));
if (match(guess, w) == x){
wordlist2.add(w);
}
}
wordlist = wordlist2.toArray(new String[wordlist2.size()]);
System.out.println("Wordlist: " + Arrays.toString(wordlist));
}
}
public int match(String a, String b) {
int matches = 0;
for (int i = 0; i < a.length(); ++i)
if (a.charAt(i) == b.charAt(i))
matches ++;
return matches;
}
}
Input:
"acckzz"
["acckzz","ccbazz","eiowzz","abcczz"]
10
StdOut:
Word list: [acckzz, ccbazz, eiowzz, abcczz]
i: 0
guess: eiowzz
x: 2
Guess: eiowzz W: acckzz Match: 2
Guess: eiowzz W: ccbazz Match: 2
Guess: eiowzz W: eiowzz Match: 6
Guess: eiowzz W: abcczz Match: 2
Wordlist: [acckzz, ccbazz, abcczz]
Word list: [acckzz, ccbazz, abcczz]
i: 1
guess: abcczz
x: 4
Guess: abcczz W: acckzz Match: 4
Guess: abcczz W: ccbazz Match: 2
Guess: abcczz W: abcczz Match: 6
Wordlist: [acckzz]
Word list: [acckzz]
i: 2
guess: acckzz
x: 6
Guess: acckzz W: acckzz Match: 6
Wordlist: [acckzz]
This is promising since this works, and randomly chooses guess, and chooses a "matchmaking" number, matches the number of instances for the number, and decreases the instance until either the word is found or 10 tries are implemented.
Apparently the worst case for the random approach enumerated above is 14 guesses and the worst case for the minimax approach is 10 guesses. Therefore, if this works the vast majority of the time, let's take a look at the method and figure out why this works.
Most of the time, for the master.guess we yield 0 matches and if we have to make a blind guess, we have an 80% chance that the algorithm wouldn't work.
So we'll assume that we'll always run into the worst case, which is a reasonable pattern in terms of software. Thus, we want to guess a word that minimizes the worst outcome.
We first compare 2 words and count their matches and for each word, not how many words of 0 matches it gets. Guess the word with the minimum words of 0 matches, and with O(N^2) time, we can minimize the time complexity of this. The code is here:
public void findSecretWord(String[] wordlist, Master master) {
for(int i = 0, x = 0; i < 10 && x < 6; ++i){
HashMap<String, Integer> count = new HashMap<>();
for(String w1 : wordlist)
for(String w2 : wordlist)
if(match(w1, w2) == 0)
count.put(w1, count.getOrDefault(w1, 0) + 1);
String guess = "";
int min0 = 100;
for(String w : wordlist)
if(count.getOrDefault(w,0) < min0) {
guess = w;
min0 = count.getOrDefault(w, 0);
}
x = master.guess(guess);
List<String> wordlist2 = new ArrayList<String>();
for(String w : wordlist)
if(match(guess, w) == x)
wordlist2.add(w);
wordlist = wordlist2.toArray(new String[0]);
}
}
So this works for cases where we have to get more words, and only takes 3 loops at most.
Now let's see this in action and output all of the results.
Final Code:
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* interface Master {
* public int guess(String word) {}
* }
*/
class Solution {
public void findSecretWord(String[] wordlist, Master master) {
for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
System.out.println("i: " + i + " wordlist: " + Arrays.toString(wordlist));
HashMap<String, Integer> count = new HashMap<>();
for (String w1 : wordlist)
for (String w2 : wordlist)
if (match(w1, w2) == 0)
count.put(w1, count.getOrDefault(w1 , 0) + 1);
String guess = "";
int min0 = 100;
for (String w : wordlist){
System.out.println("Word: " + w);
System.out.println("Count: " + count.getOrDefault(w, 0));
if (count.getOrDefault(w, 0) <= min0) {
guess = w;
min0 = count.getOrDefault(w, 0);
}
}
System.out.println("Guess: " + guess) ;
System.out.println("Minimum number of Zeros: " + min0);
x = master.guess(guess);
System.out.println("Master guess: " + x);
List<String> wordlist2 = new ArrayList<String>();
for (String w : wordlist){
System.out.println("Word: " + w + " # matches: " + match(guess, w));
if (match(guess, w) == x){
wordlist2.add(w);
}
}
wordlist = wordlist2.toArray(new String[0]);
System.out.println("new wordlist: " + Arrays.toString(wordlist));
}
}
public int match(String a, String b) {
int matches = 0;
for (int i = 0; i < a.length(); ++i)
if (a.charAt(i) == b.charAt(i))
matches ++;
return matches;
}
}
Input:
"acckzz"
["acckzz","ccbazz","eiowzz","abcczz"]
10
Print Output:
i: 0 wordlist: [acckzz, ccbazz, eiowzz, abcczz]
Word: acckzz
Count: 0
Word: ccbazz
Count: 0
Word: eiowzz
Count: 0
Word: abcczz
Count: 0
Guess: abcczz
Minimum number of Zeros: 0
Master guess: 4
Word: acckzz # matches: 4
Word: ccbazz # matches: 2
Word: eiowzz # matches: 2
Word: abcczz # matches: 6
new wordlist: [acckzz]
i: 1 wordlist: [acckzz]
Word: acckzz
Count: 0
Guess: acckzz
Minimum number of Zeros: 0
Master guess: 6
Word: acckzz # matches: 6
new wordlist: [acckzz]
Function Output:
You guessed the secret word correctly.
Comments
Post a Comment