# Guess word question

Given a distinct word list ["abc","bbc","apk" ....] , all words are the same length. and pick one word as Secret word, There is a method int Guess(string str) , will compare with the secret word, and return how many char are the same as Secret word which index is the same. for example. Secret word is "abcc" , Guess("acck") = 2, Guess("ccba") = 0, Guess("eiow") = 0, Guess("abcc") = 4. Question is how to use min call Guess to get the Secret word. All input for Guess method MUST come from the word list.

• @tangalai Hi, could you share the name of the company which asked you this problem?Thanks
Here are some thoughts on the problem :

1. Calculate k = Guess(possibleGuess).
When k == 0 continue with next string and go to step 1
If k = L (word's length) then algorithms ends and possibleGuess is the Guess word.
2. Otherwise continue with next string W and calculate Similarity(W, possibleGuess) = s.
Similarity gives us count of (letter-index) coincidences between two words.
if s < k skip this string and go to step 2. Otherwise
Calculate l = Guess(W).
If l == L algorith ends
If l >= k possibleGuess = W go to step 1

Another approach could be to take one string, caclulate Guess(s) = k and remove all strings with Similarity different than k. Then take next one and so on till you find Guess word, the only word that leaves in the array.

• @tangalai I guess this is quite similar to the bulls and cows problem: https://leetcode.com/problems/bulls-and-cows/description/.

• Yes, very similar to the problem Bulls and Cows with exception that they require minimum number of calls. I am interested in any suggestions.

• @jeantimex Yes, that is similar. But the question I been asked is more for the game , not just compare the string.

• @elmirap

Here is my code , at lease I can guess the correct secretword . but not sure if it is the less number of guess.

Base idea is to build the whole word into TrieNode . and there is a visited[i,j] where i is the index of the word, j is [0-25] , representative 'a' to 'z' .
when visited[i,j] == true, means , at index of i , it is possible existing 'a'+j .

so will call guess method when node.word != "", if return 0A0B, means every char from current word at it's index has to set to false

``````var r = Guess(item.word);
if (r[0] == 0 && r[1] == 0)
{
for (int i = 0; i < w_len; i++)
{
visited[i, item.word[i]-'a'] = false;
}
}
``````

and ever for each node has to double check if current c is visited or not.

``````if (node.c != ' ' && !visited[index,node.c-'a'])
{
return "";
}
``````
``````    public class GuessWord
{
public List<string> dict = new List<string>();

public string secretWord = "";
public int w_len = 0;
public TrieNode root = new TrieNode();
public bool[,] possible = null;
private int guessTime = 0;
Random rand = new Random();

public void InitGame(int totalWords,int wordLen) {
w_len = wordLen;
var result = new List<StringBuilder>();
for (int i = 0; i < totalWords; i++)
{
}

for (int i = 0; i < wordLen; i++) {
for (int j = 0; j < totalWords; j++)
{
result[j].Append((char)(rand.Next(26)+'a'));
}
}

dict = result.Select(x=>x.ToString()).Distinct().ToList();

Console.WriteLine("Init words : " + dict.Count);
}

private void PickSecretWord()
{
secretWord = dict[rand.Next(int.MaxValue)%dict.Count];
Console.WriteLine("Pick : " + secretWord);
}

public void InitDict() {
possible = new bool[w_len, 26];

foreach (var item in dict)
{
var current = root;

for(int i = 0;i<w_len;i++)
{
char c = item[i];
if (current.Children[c - 'a'] == null)
{
current.Children[c - 'a'] = new TrieNode();
current.Children[c - 'a'].c = c;
}

current = current.Children[c - 'a'];
possible[i, c - 'a'] = true;
}
current.word = item;
}
}

public void Play() {
var visited = (bool[,])possible.Clone();
guessTime = 0;
PickSecretWord();
Console.WriteLine("Answer : " + Helper(root, 0, visited));
Console.WriteLine("Guess Time : " + guessTime);
}

public string Helper(TrieNode node, int index, bool[,] visited) {
if (node == null)
return "";

foreach (var item in node.Children)
{
if (node.c != ' ' && !visited[index,node.c-'a'])
{
return "";
}
if (item != null && visited[index,item.c-'a'])
{
if (item.word != "")
{
var r = Guess(item.word);
if (r[0] == 0 && r[1] == 0)
{
for (int i = 0; i < w_len; i++)
{
visited[i, item.word[i]-'a'] = false;
}
}
else if (r[0] == w_len)
{
return item.word;
}
}
else
{
var result = Helper(item, index + 1, visited);
if (result != "")
{
return result;
}
}
}
}
return "";
}

private int[] Guess(string word) {
guessTime++;
int[] result = new int[2];
var mapping = new int[26];
for (int i = 0; i < w_len; i++) {
if (word[i] == secretWord[i])
{
result[0]++;
}
else {
if (++mapping[word[i] - 'a'] <= 0) {
result[1]++;
}

if (--mapping[secretWord[i] - 'a'] >= 0)
{
result[1]++;
}
}
}

return result;
}
}

public class TrieNode {

public TrieNode[] Children = new TrieNode[26];

public char c=' ';

public string word="";
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.