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

113 Solutions
14 Solvers

Last Solution submitted on Mar 30, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

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.

Nikolaos Nikolaou on 24 Dec 2020

Where did you put the function score Rafael ? Cause if it is nested or after the first it is just ignored

Please someone with curator rights fix this one cause its a badge problem

William on 6 Mar 2021

Rafael,
Thanks for the tip. That worked fine.

Problem Recent Solvers14

Problem Tags

games probability

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1184. Hangman (strategy)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers14

Suggested Problems

More from this Author38

Problem Tags

Community Treasure Hunt

Problem 1184. Hangman (strategy)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers14

Suggested Problems

More from this Author38

Problem Tags

Community Treasure Hunt

Players