Finding longest ambiguous words with a given set of letters

Question

I have been playing hangman with my friend over an app for a while now, and we have a gentlemen's understanding between us that we are both "cheating" by using online software both to solve the given word (lookup words with given length, filter words with letters in known positions) and to form new words with the random set of letters we are given.

The algorithms work most of the time. We are both given a varying number of incorrect guesses each turn before we lose a life. The only trouble comes with "ambiguous" words, i.e. there are fewer incorrect guesses left than necessary to narrow the search to one word. For example, with one chance left,

_are

could be both "bare" and "care" with equal probability (along with at least 8 other words). I want to find words that have an ambiguity of at least 1.

My question is, how would I go about designing an algorithm that, given a certain set of letters, forms a word with minimum length 4 which is maximally ambiguous?

Answer 1

There are some subtleties in this question that haven't been clarified yet.

However, I have a working prototype that seems to approximate what OP is asking for.

Before describing my approach, here is a test case.

For this test case, the word list is obtained from: http://www.cse.msu.edu/~cse231/PracticeOfComputingUsingPython/05_ListsTuples/Anagrams/3eslWordList.txt
(Disclaimer: search engine results may contain links to materials protected by copyright.)

The following filtering criteria are applied:

• Length at least 4
• All letters (no space, hyphen, apostrophes)
• All lower case (to skip the initialisms)

Then, each unique word is assigned an integer, starting from zero.

For each word, a small list of patterns are generated from it, by replacing one character with a placeholder each time. For example, from the word care a list of 4 patterns would be generated:

?are
c?re
ca?e
car?

Each pattern is then used to search the word list again. Unique hits are counted. Subtracting one from this number gives the number of friends for this word.

There are some other aspects which are merely performance optimizations. Since optimization is mostly a personal taste, I will skip the details unless there is a consensus that I should include them with my answer.

I also have C# source code, but I don't know if I should be posting them here or not, unless there is a consensus.

Of the C# classes, I would mention two for their particular usefulness:

• One is a bidirectional map between string and a sequentially assigned integer value (starting with zero). Essentially a List<string> plus a Dictionary<string, int> plus some logic.
• Another is a bidirectional multi-map between two set of integers from separate namespaces ^(Note). This is used to store tuples of (wordIndex, patternIndex) and allow lookup using either one.

^(Note)say, Tuple.Item1 means word index, Tuple.Item2 means pattern index, and where the coincidence of a word index equal to a pattern index is completely inconsequential. (Please help me improve this description.)

First test case: care should return 22 matches, itself included (therefore, 21 true friends)

care : 22
bare
cafe
cage
cake
came
cane
cape
card
care
carp
cart
case
cave
core
cure
dare
fare
hare
mare
pare
rare
ware

Second test case: butter should return 10 matches, itself included (therefore, 9 true friends)

butter : 10
batter
better
bitter
buster
butler
butter
cutter
gutter
mutter
putter