Guess The Word

Guess The Word is an interactive problem. An interactive problem means the data which is given to us is not predetermined. We can print values or call the specific function to interact or get more information regarding the solution. After each step, we also need to FLUSH the buffer to get the correct answer. Now see what exactly guess the word problem is!!! We have given N-words and the length of each word is the same let it will be X. In this problem, if we print a number then the interactor gives us an integer value Y. Y represents the number of characters matching the guess word. Guess the word is always match with any one word among N-words. We only ask a few questions to the interactor by printing the word. We have to find the guess string and print it without exceeding the limit of the question asked.

Guess the word-an interactive problem!

The limit of the question asked is 10 and the value of N(number of words) is 6. Here we take all the words of length 8. See the input’s value which is given.

words = { “abcdefgh”, “riwqsgrd”, “nhtrgjue”, “kueshtew”, “ticqehac”, “nmvdswqz”}.

We print “abcdefgh” to ask the question from interactor and interactor give an integer value 2. Now, we understand that the current number never be our guess number. Ask another question by printing “riwqsgrd”. In this case, interactor give an integer value 1. Then we also remove this word from our answer list. Ask 3rd question by printing “ticqehac”. In this case, interactor give an integer value 8. Here we got guess word because of all the characters of the present word matched with the guess word.

Here only in the 3rd question we got our answer so this is a valid solution.

Algorithm

Step:1 Sort the words in dictionary order.
Step:2 While wordlist.size !=0 and question_asked<=q then:
       A) Pick one random word and ask the question using it.
       B) If interactor answer equal to the length of the word then return the current word.
       C) Create one more list and add all those words whose characters matched by random picked number greater than the answer given by interactor.
       D) wordlist = new_wordlist(created in step 2.C).
Step:3 If no word found then return/print -1.

Implementation

/*C++ Implementation of Guess The Word Problem.*/ 
#include<bits/stdc++.h> 
using namespace std; 
void findSecretWord(vector<string> &wordlist,int guessCnt,int wordlength) 
{
    /*Check edge case.*/
    if(wordlist.size()==0) 
    {
        return;
    }
    int flag=0;
    /*sort(wordlist.begin(), wordlist.end()).*/
    while (wordlist.size()>0&&guessCnt--) 
    {
        /*Get random pick*/
        string candidate = wordlist[rand() % (wordlist.size())];
        /*ask question by printing word.*/
        cout<<candidate<<endl;
        int found;
        /*answer to the question asked.*/
        cin>>found;
        /*Checking current word is guess word or not*/
        if(found==wordlength) 
        {
            flag=1;
            /*Print the Guess Word.*/
            cout<<candidate<<endl;
            break;
        }
        /*Logical reduction of the wordlist.*/
        vector<string> wordlist2;
        for(int i=0;i<wordlist.size();i++) 
        {
            int match=0;
            for(int j=0;j<wordlength;j++)
            {
                if(wordlist[i][j]==candidate[j])
                {
                    match++;
                }
            }
            if(match==found) 
            {
                wordlist2.push_back(wordlist[i]);
            }
        }
        wordlist=wordlist2;
    }
    if(flag==0)
    {
        cout<<-1<<endl;
    }
}
int main() 
{
    /*input values.*/
    int n;
    /*number of words.*/
    cin>>n;
    /*length of word.*/
    int w;
    cin>>w;
    /*maximum limit of question asked.*/
    int q;
    cin>>q;
    vector<string> wordlist;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        wordlist.push_back(x);
    }
    findSecretWord(wordlist,q,w);
    return 0;
}

6
8
10
abcdefgh riwqsgrd nhtrgjue kueshtew ticqehac nmvdswqz

Interactor               You
                       nmvdswqz
    0
                       abcdefgh
    2
                       ticqehac 
    8
                       ticqehac

Time Complexity

O(N*N) where N is the number of words given to us. Here we can’t take care about time complexity because we use random function then we cant able to guess how to code run. For multiple testing of code complexity by taking various examples we found the time complexity varies randomly. Here we also see that we always reduce the length of word-list. So, we can say that worst-case time complexity is O(N*N).

 Space Complexity

O(N) where N is the number of words given to us. We use a vector of string to store those values. So, the maximum space used in the above code is O(N).

References