Problem 1184. Hangman (strategy)

Created by Alfonso Nieto-Castanon

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>What is the best strategy in a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Hangman_(game)\"><w:r><w:t>hangman</w:t></w:r></w:hyperlink><w:r><w:t> game?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your job is to device a strategy to play the hangman game with a minimal number of errors (wrongly guessed letters).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your function will receive as input a cell array containing all possible N-letter words and it should output your best letter guess.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>words={'AAA','BED','BEG','BAD'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your algorithm may return any single letter (e.g. letter='B' might be a good guess);</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Fineprint:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You may use the same strategy proposed in the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1182-hangman-easy\"><w:r><w:t>previous Hangman problem</w:t></w:r></w:hyperlink><w:r><w:t>, 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</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>updated</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example: Game 1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>target_word='BEG';</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>words={'AAA','BED','BEG','BAD','ABE','CAD'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Step 1: Your algorithm guesses letter 'B' (right)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Updated word list: {'ED','EG','AD'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Step 2: Your algorithm guesses letter 'E' (right)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Updated word list: {'D','G'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Step 3: Your algorithm guesses letter 'D' (wrong)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Updated word list: {'G'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Step 3: Your algorithm guesses letter 'G' (right)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Game ends. Total errors: 1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example: Game 2</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>target_word='AAA';</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>words={'AAA','BED','BEG','BAD','ABE','CAD'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Step 1: Your algorithm guesses letter 'B' (wrong)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Updated word list: {'AAA','CAD'};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Step 2: Your algorithm guesses letter 'A' (right)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Game ends. Total errors: 1</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

What is the best strategy in a <a href="http://en.wikipedia.org/wiki/Hangman_(game)">hangman</a> 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 <a href="http://www.mathworks.com/matlabcentral/cody/problems/1182-hangman-easy">previous Hangman problem</a>, 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 1target_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: 1Example: Game 2target_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

Solve

Solution Stats

83 Solutions
23 Solvers

Last Solution submitted on Aug 03, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

William on 30 May 2019

The 2nd and 3rd test problems now fail with the error message:
Error using evalin
Undefined function or variable 'score'.
Error in Test2 (line 30)
assignin('caller','score',evalin('caller','score')-100+round(a.e/5*100));

Rafael S.T. Vieira on 3 Aug 2020

I've bypassed this problem creating a function called score, which returns 300.

Problem Recent Solvers23

Problem Tags

games probability

Problem 1184. Hangman (strategy)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers23

Suggested Problems

More from this Author38

Problem Tags

Problem 1184. Hangman (strategy)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers23

Suggested Problems

More from this Author38

Problem Tags

Players