Hangman is a paper and pencil guessing game for two players. One player thinks of a word and the other tries to guess it by suggesting letters. The word to guess is represented by a pattern that initially contains a sequence of underscores (_). Herewith, each underscore represents a letter of the word. The number of underscores in the initial pattern thus corresponds to the number of letters in the word to guess.

If the guessing player suggests a letter which occurs in the word, the other player fills up the pattern at all open positions (indicated by underscores) where the letter occurs in the word. If the suggested letter does not occur in the word, the other player draws one element of a hanged man stick figure as a tally mark. The guessing player wins the game if he completes all letters of the word before all elements of the hanged man stick figure have been drawn. Otherwise the other player wins the game.

Assignment

Implement the player of the hangman game that thinks of a word that the other player must guess. Only words containing lowercase letters are considered. The player, however, make use of a cheating strategy that makes it as a hard as possible for the other player to win the game. The idea behind this strategy is simple. Instead of choosing a fixed word of a given length $$n$$ at the start of the game, the player initially considers all words of length $$n$$ as possible candidates. Each time the other player suggests a new letter, the player fills the pattern in such a way that the number of remaining candidates that are consistent with the pattern and all suggested letters is maximized. By following this strategy, most of the time another body part will be added to the gibbet. To make it concrete, you should implement at least the following functions:

• Write a function candidate that takes three arguments: i) a word (str; containing lowercase letters only), ii) a pattern (str) that can be partially filled (contains underscores and lowercase letters only), and iii) all (lowercase) letters (str) that have been suggested previously. The function must return a Boolean value (bool) that indicates whether the word is consistent with the pattern and all previously suggested letters. This is the case if the word has the same length as the pattern, and each position of the pattern either contains the same letter at the corresponding position of the word that is also contained in the previously suggested letters, or contains an underscore while the letter at the corresponding position of the word is not contained in the previously suggested letters.

• Write a function fill that takes three arguments: i) a word (str; containing lowercase letters only), ii) a pattern (str) that can be partially filled (contains underscores and lowercase letters only), and iii) a lowercase letter (str). The function may assume that the given word is a candidate for the given pattern. The function must return a new pattern (str), that consists of the given pattern that was filled with all occurrences of the new letter in the given word.

• Write a function select that takes three arguments: i) a pattern (str) that can be partially filled (contains underscores and lowercase letters only), ii) all (lowercase) letters (str) that have been suggested previously (where the function may assume that all letters in the pattern occur in this sequence of letters), and iii) a lowercase letter (str) that was not suggested previously. The function may assume that the current directory contains a text file words.txt¹ that contains a sequence of words (lowercase letters only), each on a separate line. First, the function must determine a new pattern for each remaining candidate (the words of the file words.txt² that are consistent with the given pattern and the previously suggested letters (second argument)) that consists of the given pattern that is filled with the newly suggested letter (third argument). Then, the function must return a tuple containing two strings (str). The first string contains the new pattern that was found most often during the previous step. The second string is a randomly selected word from the file words.txt³ that is consistent with the selected new pattern (first string of tuple) and all suggested letters (from both the second and third argument).

Example

>>> candidate('apple', '_ppl_', 'klmnop')
True
>>> candidate('apples', '_ppl_', 'klmnop')
False
>>> candidate('apple', '_ppl_', 'p')
False
>>> candidate('apple', '_ppl_', 'apl')
False
>>> candidate('apple', '__pl_', 'klmnop')
False
>>> candidate('apple', '_kpl_', 'klmnop')
False
>>> candidate('angel', '_ppl_', 'klmnop')
False

>>> fill('apple', '_pp__', 'p')
'_pp__'
>>> fill('apple', '_pp__', 'l')
'_ppl_'
>>> fill('apple', '_ppl_', 'x')
'_ppl_'

>>> select('_ppl_', 'klmnop', 'a')
('appl_', 'apple')
>>> select('a__l_', 'al', 'p')
('a__l_', 'angle')
>>> select('a__l_', 'abcdefghijklmno', 'p')
('a__l_', 'artly')
>>> select('_ppl_', 'klmnop', 'x')
('_ppl_', 'apple')
>>> select('_____', '', 'x')
('_____', 'angle')