Problem 1184. Hangman (strategy)

What is the best strategy in a hangman game?

Your job is to device a strategy to play the hangman game with a minimal number of errors (wrongly guessed letters).

Your function will receive as input a cell array containing all possible N-letter words and it should output your best letter guess.

Your algorithm will be put to test by recreating a number of hangman game scenarios, and it will be scored based on its performance (average number of errors until correctly guessing the target word)

Example:

words={'AAA','BED','BEG','BAD'};

Your algorithm may return any single letter (e.g. letter='B' might be a good guess);

Fineprint:

You may use the same strategy proposed in the previous Hangman problem, but that is not guaranteed to be the optimal overall strategy (finding out which strategy seems optimal is the goal of this problem). In this case scoring will be based on actually running your algorithm through a set of games and computing the average number of errors it produces until correctly guessing the entire word. Within any given game the history of your guesses is implicit in the updated word list (at any given step in the game the word list will only include those words that still remain possible given the dictionary and your history of guesses, also note that all of your previously guessed letters will be missing from this updated dictionary list; also note that the dictionary list may include a single word). You will receive a passing grade if your function is able to correctly guess a word with less than 5 errors on average. Your score will be proportional to the average number of errors per word.

Example: Game 1

target_word='BEG';

words={'AAA','BED','BEG','BAD','ABE','CAD'};

Step 1: Your algorithm guesses letter 'B' (right)

Updated word list: {'ED','EG','AD'};

Step 2: Your algorithm guesses letter 'E' (right)

Updated word list: {'D','G'};

Step 3: Your algorithm guesses letter 'D' (wrong)

Updated word list: {'G'};

Step 3: Your algorithm guesses letter 'G' (right)

Game ends. Total errors: 1

Example: Game 2

target_word='AAA';

words={'AAA','BED','BEG','BAD','ABE','CAD'};

Step 1: Your algorithm guesses letter 'B' (wrong)

Updated word list: {'AAA','CAD'};

Step 2: Your algorithm guesses letter 'A' (right)

Game ends. Total errors: 1