Guess word question


  • 0
    T

    I was been asked on question about guess word
    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.

    I have not idea about this question, anyone can help me?


  • 0

    @tangalai Hi, could you share the name of the company which asked you this problem?Thanks
    Here are some thoughts on the problem :
    Start with first word and set it to be possibleGuess

    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.


  • 0

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


  • 0

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


  • 0
    T

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


  • 0
    T

    @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++)
                {
                    result.Add(new StringBuilder());
                }
    
                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="";
        }
    

Log in to reply
 

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