The perverse hangman problem

Perverse Hangman is a game played much like regular开发者_开发问答 Hangman with one important difference: The winning word is determined dynamically by the house depending on what letters have been guessed.

For example, say you have the board _ A I L and 12 remaining guesses. Because there are 13 different words ending in AIL (bail, fail, hail, jail, kail, mail, nail, pail, rail, sail, tail, vail, wail) the house is guaranteed to win because no matter what 12 letters you guess, the house will claim the chosen word was the one you didn't guess. However, if the board was _ I L M, you have cornered the house as FILM is the only word that ends in ILM.

The challenge is: Given a dictionary, a word length & the number of allowed guesses, come up with an algorithm that either:

a) proves that the player always wins by outputting a decision tree for the player that corners the house no matter what

b) proves the house always wins by outputting a decision tree for the house that allows the house to escape no matter what.

As a toy example, consider the dictionary:

bat
bar
car

If you are allowed 3 wrong guesses, the player wins with the following tree:

Guess B
NO -> Guess C, Guess A, Guess R, WIN
YES-> Guess T
      NO -> Guess A, Guess R, WIN
      YES-> Guess A, WIN

This is almost identical to the "how do I find the odd coin by repeated weighings?" problem. The fundamental insight is that you are trying to maximise the amount of information you gain from your guess.

The greedy algorithm to build the decision tree is as follows: - for each guess, choose the guess which for which the answer is "true" and which the answer is "false" is as close to 50-50 as possible, as information theoretically this gives the most information.

Let N be the size of the set, A be the size of the alphabet, and L be the number of letters in the word.

So put all your words in a set. For each letter position, and for each letter in your alphabet count how many words have that letter in that position (this can be optimised with an additional hash table). Choose the count which is closest in size to half the set. This is O(L*A).

Divide the set in two taking the subset which has this letter in this position, and make that the two branches to the tree. Repeat for each subset until you have the whole tree. In worst case this will require O(N) steps, but if you have a nice dictionary this will lead to O(logN) steps.

This isn't strictly an answer, since it doesn't give you a decision tree, but I did something very similar when writing my hangman solver. Basically, it looks at the set of words in its dictionary that match the pattern and picks the most common letter. If it guesses wrong, it eliminates the largest number of candidates. Since there's no penalty to guessing right in hangman, I think this is the optimal strategy given the constraints.

So with the dictionary you gave, it would first guess a correctly. Then it would guess r, also correctly, then b (incorrect), then c.

The problem with perverse hangman is that you always guess wrong if you can guess wrong, but that's perfect for this algorithm since it eliminates the largest set first. As a slightly more meaningful example:

Dictionary:

mar
bar
car
fir
wit

In this case it guesses r incorrectly first and is left with just wit. If wit were replaced in the dictionary with sir, then it would guess r correctly then a incorrectly, eliminating the larger set, then w or f at random incorrectly, followed by the other for the final word with only 1 incorrect guess.

So this algorithm will win if it's possible to win, though you have to actually run through it to see if it does win.