Guessing the word from a dictionary [reviewed]

Problem

Assuming you're playing one game that you need guess a word from a dictionary. You're given a machine you can try to guess the word, the machine will return how many characters has been matched by your guess. Design a system to crack the word.

Brute-force approach $O(N \times N!)$

My first approach back in 2016 was to find the length and characters of the secret words by using the repeated words such as "aaaaaaaaaaaaaaaaaaaaaaaaaaa" with the target word.

Longest word in the dictionary is 45 characters-long. So, putting 100 of 'a' and comparing with the tar get word will tell us whether 'a' exists in the target word and how many 'a' is in the word if presents.

For example,

target word is 'beautiful', comparing with "aaaaaaaaaaaaaaaaaaaaaaaaaaa" will return 1.

By comparing from repeated 'a' to 'z', we can get the length of target word and list of alphabet characters.

Previous solution used these information to produce possible permutations and match the words.

This approach takes too long. Especially for 45 chars-longs words. (5.3829999e+57 times of comparison).


Here is the complete code running in $O(N \times  N!)$

Practice statistics

40:00 to write up the code and debug the logical flaw

More advanced approach $O(N)$

This approach still takes advantage of previous solution finding the length of the target word and the characters consisting of it. 

Given that we found the length of the word, $N$ and set of chars, $CHARS$.

With that information, it takes the following steps:

1. create empty array, $Result$ with length of $N$ filled with None
2. iterate for characters in $CHARS$, for each char, $C$ and position, $I$
1.  create a guess word, $G$ filled with $C$ where $Result[i]$ is None.
2.  compare $G$ with the target word and store the matching char count, $M$
3. increment $I$ by 1 to get the next char $C'$.
4. for each positions, $J$ in $N$:
1. replace $G[J]$ with $C'$
2. compare $G$ again and store a new matching char count, $M'$.
3. if $M'$ > $M$, $C'$ is in the right position $J$. Set  $Result[i]$  to $C'$
4. if $M'$ < $M$, old value, $C$ was in the correct position.
1. Set  $Result[J]$  to $C$ and $G[J]$ to $C$ (restore old value)

  

Time complexity

In the algorithm above, the outer for loop runs up to 26 times in the worst case and inner for loop runs N times, where N is the length of the target word.

Therefore, running time is close to $O(N)$.   

Here is the solution in python.


Practice statistics

60:07: did not come up with the complete algorithm
26:39: to write up the complete code
15:43: fixing the bugs. There was one logic bug. alphabet string had a duplicate characters. (- -)