## Algorithm

Problem Name: 843. Guess the Word

You are given an array of unique strings `words` where `words[i]` is six letters long. One word of `words` was chosen as a secret word.

You are also given the helper object `Master`. You may call `Master.guess(word)` where `word` is a six-letter-long string, and it must be from `words`. `Master.guess(word)` returns:

• `-1` if `word` is not from `words`, or
• an integer representing the number of exact matches (value and position) of your guess to the secret word.

There is a parameter `allowedGuesses` for each test case where `allowedGuesses` is the maximum number of times you can call `Master.guess(word)`.

For each test case, you should call `Master.guess` with the secret word without exceeding the maximum number of allowed guesses. You will get:

• `"Either you took too many guesses, or you did not find the secret word."` if you called `Master.guess` more than `allowedGuesses` times or if you did not call `Master.guess` with the secret word, or
• `"You guessed the secret word correctly."` if you called `Master.guess` with the secret word with the number of calls to `Master.guess` less than or equal to `allowedGuesses`.

The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).

Example 1:

```Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in 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 made 5 calls to master.guess, and one of them was the secret, so we pass the test case.
```

Example 2:

```Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation: Since there are two words, you can guess both.
```

Constraints:

• `1 <= words.length <= 100`
• `words[i].length == 6`
• `words[i]` consist of lowercase English letters.
• All the strings of `wordlist` are unique.
• `secret` exists in `words`.
• `10 <= allowedGuesses <= 30`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int idx[100];
int n;
} set_t;

#define IDX(I, J) ((I) * 100 + J)

int solve(set_t *p, int *xp, int *match, int sz) {
int groups[7] = { 0 };  // max match number is 6
int max_group, min_group;
int i, j, g;

if (p->n  < = 2) return p->idx[0];

g = -1; min_group = 1000;
for (i = 0; i  <  sz; i ++) {
if (xp[i]) continue;
memset(groups, 0, sizeof(int) * 7);
for (j = 0; j  <  p->n; j ++) {
if (i != p->idx[j]) groups[match[IDX(i, p->idx[j])]] ++;
}

max_group = groups[0];
for (j = 1; j  <  7; j ++) {
if (max_group < groups[j]) max_group = groups[j];
}

if (min_group > max_group) {
min_group = max_group;
//printf("groups: %d, %d %d, %d, %d, %d, %d\n", groups[0], groups[1], groups[2], groups[3], groups[4], groups[5], groups[6]);
g = i;
}
}

return g;
}

void findSecretWord(char** wordlist, int wordlistSize, Master* master) {
int match[100 * 100];
int i, j, k, m, g;
char *a, *b;

set_t buff[2] = { 0 };
set_t *p1, *p2, *p3;
int xp[100] = { 0 };

p1 = &buff[0];
p2 = &buff[1];

// caculate match matrix
for (i = 0; i  <  wordlistSize; i ++) {
a = wordlist[i];
for (j = i + 1; j  <  wordlistSize; j ++) {
b = wordlist[j];
m = 0;
for (k = 0; k  <  6; k ++) {
if (a[k] == b[k]) m ++;
}
match[IDX(i, j)] = match[IDX(j, i)] = m;
}
}

// all are possible in the beginning
for (i = 0; i  <  wordlistSize; i ++) {
p1->idx[p1->n ++] = i;
}

while (p1->n > 0) {
//printf("POSSIBLE: %d\n", p1->n);
g = solve(p1, xp, match, wordlistSize);
printf("GUESS: %d, %s\n", g, wordlist[g]);
m = guess(master, wordlist[g]);
//printf("MATCH: %d\n", m);
if (m == 6) return;
// find out next possible words
p2->n = 0;                          // reset p2
for (i = 0; i  <  p1->n; i ++) {
if (match[IDX(g, p1->idx[i])] == m) {
p2->idx[p2->n ++] = p1->idx[i];
}
}
// swap p1, p2
p3 = p1;
p1 = p2;
p2 = p3;
// exclude g in future guess
xp[g] = 1;
}
}
``````
Copy The Code &

Input

cmd
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10

Output

cmd
You guessed the secret word correctly.

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
void findSecretWord(vector<string>& wordlist, Master& master) {
vector<string>cur, next;
cur = wordlist;
for (int i = 0; i  <  10; ++i) {
int n = cur.size();
auto word = cur[rand() % n];
int match = master.guess(word);
if (match == 6) {
break;
}
for (auto& s: cur) {
if (distance(s, word) == match) {
next.push_back(s);
}
}
cur.clear();
swap(cur, next);
}
}

int distance(string& a, string& b) {
int res = 0;
for (int i = 0; i  <  a.size(); ++i) {
if (a[i] == b[i]) {
++res;
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10

Output

cmd
You guessed the secret word correctly.

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findSecretWord = function (wordlist, master) {
let group = wordlist
for (let i = 0; i  <  10; i++) {
let currentGuess = findTheTypical(group)
let res = master.guess(currentGuess)
if (res === 6) return
let tmp = []
for (let j = 0; j  <  group.length; j++) {
if (diff(group[j], currentGuess) === 6 - res) tmp.push(group[j])
}
group = tmp
}
}
function findTheTypical(wordlist) {
const count = Array.from({ length: 6 }, (x) => new Object())
for (let i = 0; i  <  wordlist.length; i++) {
for (let j = 0; j  <  6; j++) {
const cur = wordlist[i][j]
if (count[j][cur] === undefined) count[j][cur] = 1
else count[j][cur]++
}
}
let maxPos = 0,
maxCount = 0,
maxAlp = ''
for (let i = 0; i  <  6; i++) {
for (let k of Object.keys(count[i])) {
if (count[i][k] > maxCount) {
maxCount = count[i][k]
maxPos = i
maxAlp = k
}
}
}
for (let i = 0; i  <  wordlist.length; i++) {
if (wordlist[i][maxPos] === maxAlp) return wordlist[i]
}
}
function diff(a, b) {
let count = 0
for (let i = 0; i  <  a.length; i++) {
if (a[i] !== b[i]) count++
}
return count
}
``````
Copy The Code &

Input

cmd

Output

cmd
You guessed the secret word correctly.

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findSecretWord(self, wordlist, master):
n = 0
while n < 6:
count = collections.Counter(w1 for w1, w2 in itertools.permutations(wordlist, 2) if sum(i == j for i, j in zip(w1, w2)) == 0)
guess = min(wordlist, key = lambda w: count[w])
n = master.guess(guess)
wordlist = [w for w in wordlist if sum(i == j for i, j in zip(w, guess)) == n]
``````
Copy The Code &

Input

cmd

Output

cmd
You guessed the secret word correctly.

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0843_GuesstheWord
{
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
*     public int Guess(string word);
* }
*/
public void FindSecretWord(string[] wordlist, Master master)
{
var random = new Random();
var wordlistHashSet = new HashSet < string>(wordlist);

for (int i = 0; i  <  10; i++)
{
var word = wordlistHashSet.ElementAt(random.Next(wordlistHashSet.Count));
var result = master.Guess(word);
if (result == word.Length) return;

wordlistHashSet.RemoveWhere(anotherWord => MatchCount(word, anotherWord) != result);
wordlistHashSet.Remove(word);
}
}

public int MatchCount(string word1, string word2)
{
var count = 0;
for (int i = 0; i  <  word1.Length; i++)
if (word1[i] == word2[i])
count++;

return count;
}
}

public class Master
{
private readonly HashSet < string> wordlist;

public Master(string secret, string[] wordlist)
{
this.secret = secret;
this.wordlist = new HashSet < string>(wordlist);

GuessCount = 0;
}

public int GuessCount { get; set; }

public int Guess(string word)
{
GuessCount++;
if (this.secret.Length != word.Length) { return -1; }
if (!wordlist.Contains(word)) { return -1; }

var count = 0;
for (int i = 0; i  <  word.Length; i++)
if (word[i] == secret[i])
count++;

return count;
}
}
}
``````
Copy The Code &

Input

cmd
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10

Output

cmd
You guessed the secret word correctly.