1

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?

  • Why would you start from a certain set of letters? Are you picking the word you're going to challenge your opponent with? – candied_orange May 21 '16 at 8:09
  • The game automatically gives you 12 random letters with which we create an anagram with. So I need to find the most ambiguous word with those letters. – Luke Salamone May 22 '16 at 2:33
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
  • What subtleties still need to be clarified? You never mentioned what they were. Great work though! – Luke Salamone May 22 '16 at 2:42
  • I can think of one ... I don't remember exactly how "hangman" is played, but it seems if you guessed "t" when the word is "butter", the two "t"'s are revealed at once. So there needs to be some changes to the patterns to reflect that. Changing the "t's" to "bu**er" would not work because that could match "butler". Also, you haven't defined "maximally ambiguous". Do you consider just the endgame (when there is only one letter left) or a bit further back (when two or letters are still hidden)? – rwong May 22 '16 at 2:55
  • Yes, both t's would be revealed at once. Maximally ambiguous is asking to maximize n where n is the minimum number of guesses to definitively determine the word. – Luke Salamone May 23 '16 at 19:38

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.