4
$\begingroup$

Suppose I am given a dictionary of words which contains no more than 100 words, and each word has a maximum length of 50 characters. I want to write a program to guess an unknown word, call it S, that is in the dictionary using 2 weighted operators:

  • int getOccurrences(char x): return the frequency of the character 'x' in S. This operator costs 1 for each query.
  • char getChar(int k): return the character at the position 'k' of S. If the length of S is less than k, it will return '#'. This operator costs 10 for each query.

(those functions will give me feedback when I call them)

It is preferred that the average cost to guess S is minimal.

I completely have no idea with this problem. My thought is that given a list of strings, which operator I should use to divide the set by half like in binary search, but I have no luck yet.

Thank you.

PS: Assume that the words in the dictionary are only containing a-z.

$\endgroup$
  • $\begingroup$ You described the thought you had. What happens when you try that? Why have you rejected it? It seems like a perfectly reasonable thing to try. What does it mean to say you "have no luck yet"? No luck with what? Seems like you've already got a possible answer to your question; now the next step is you should try it and see if it works well enough for your purposes, or if you already know it is not acceptable, describe what requirement it violates. $\endgroup$ – D.W. Jul 29 '16 at 22:56
  • $\begingroup$ I'm still thinking in the direction to find an operator that divides the set in half like in the binary search, but I haven't found one yet. I'm not sure if I'm in the right direction. If so, how can I choose the operator? Thank you. $\endgroup$ – dh16 Jul 29 '16 at 23:12
2
$\begingroup$

A good heuristic: greedy choice

Here is a greedy algorithm. It might not be optimal, but I suspect will yield a solution that is good enough. It is basically an instantiation of your thought, but taking into account a bit of information theory. The idea will be to greedily choose which operator to query at each iteration; to tell which operator is best, we'll simulate all possibilities for the choice of operator and see which gives us the best gain.

Basically, we're building a decision tree on the fly, via greedy choice at each step.

Keep a set $T$ of all possibilities for the unknown word. (Initially this is $S$, but you'll narrow down the possibilities as you go.) In each iteration:

  • For each possible operator $f$ you could possibly try, compute the "information gain" of using that operator, $$I(f) = H(X) - H(X | f(X)),$$ where $X$ is a random variable that is uniformly distributed on the current set $T$. This tells you the expected number of bits of reduction of the entropy -- roughly speaking, the reduction in uncertainty about the word.

  • For each possible operator $f$, compute the cost of that operator, $\text{cost}(f)$. Also compute the gain-per-unit-cost, $I(f)/\text{cost}(f)$.

  • Pick the operator $f$ with the largest value of $I(f)/\text{cost}(f)$, and query that operator. Use the response to reduce the set of possible words, i.e., remove from $T$ each word that is inconsistent with the response you got.

Repeat until you are left with only one possibility.

Notice that there are only $26+50=76$ different possible operators, so it is easy to enumerate over them all in each iteration. This algorithm will be pretty fast.

Information gain

How do you compute the information gain of an operator $f$? Well, you know the set $T$. Also, given any word $w \in T$, you can compute the result $f(w)$ of applying $f$ to word $w$.

It's easy to compute the entropy $H(X)$: that is just $\lg |T|$. The entropy of a uniform distribution on some set is the base-2 logarithm of the size of that set.

To compute $H(X|f(X))$, we partition $T$ into subsets $T_1,T_2,\dots,T_k$ according to what the operator returns (all word that return the same value in response to this operator are grouped into the same subset). Now $H(X|f(X)=y)$ is just $\lg |T_i|$, where $T_i$ is the subset corresponding to words that yield response $y$. The conditional entropy $H(X|f(X))$ is the average of $H(X|f(X)=y)$ over all possible values of $y$, weighted by the probability of getting $y$. Thus,

$$H(X|f(X)) = \sum_i {|T_i| \over |T|} \cdot \lg |T_i|.$$

It follows that

$$I(f) = \lg |T| - \sum_i {|T_i| \over |T|} \cdot \lg |T_i|.$$

Optimal sequence

The algorithm above doesn't guarantee to output the optimal solution. What if we want the optimal sequence of queries? Well, basically this corresponds to building a decision tree, where each node of the tree applies one operator and then branches upon the result.

We can evaluate the "cost" of a decision tree according to the expected cost spent by the decision tree to narrow down the word to a single possibility, with the expectation taken over the random choice of the unknown word. Given a decision tree, it is easy to compute its expected cost. For each of the 100 words, you can simulate what path it will take through the decision tree and the total cost before it hits a leaf; averaging those 100 costs yields the expected cost.

You could now enumerate over all decision trees, and take the one whose expected cost is minimal. Of course, this will be highly inefficient, as there are exponentially many trees, but it does find the optimal solution.

It should be possible to make this more efficient using branch-and-bound. Explore the space of decision trees, by building them up in a top-down fashion (from the root downwards). At any point, you have a partial decision tree (the top of some decision tree, with bottom parts yet to be filled in).

You can get an upper bound for the cost of the best way to complete a partial decision tree to a full decision tree, by applying the greedy heuristic above to complete it to a tree and seeing what the result costs.

Also, you can get a lower bound as follows. Suppose we have any set $U$ of words. Find the letterx such that the number $b$ of different possible results of getOccurrences(x) [taken over all words of $U$] is as large as possible. Then the cost of any decision tree for $U$ will necessarily be at least $\lceil \log_b U \rceil$. For each bottom node in a partial decision tree, find the set $U$ of words that reach that node, compute a lower bound on the cost of the best decision tree to put as a subtree of that node, and average these up over all the bottom nodes of the partial decision tree (together with the cost of reaching that node).

Now use these lower and upper bounds to prune your exploration, following standard branch-and-bound techniques: if the lower bound for a partial decision tree is at least as large as the expected cost of the best complete decision tree seen so far, then you can prune that partial decision tree (there is no need to explore any of the candidate ways to complete it to a complete decision tree).

Whether this algorithm will be efficient enough to use, I don't know. You could implement it and give it a try.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.