TopCoder problem "Hangman42" used in SRM 229 (Division I Level Three)



Problem Statement

    "Hangman for two" is a game based on the popular Hangman game. In this version of the game, the computer randomly selects a word from its word database and displays a line of dashes, each of which represents one character of the selected word. Then two players alternately try to find out the selected word.

Each turn, the current player may guess one character. If the character occurs in the word, all occurrences of this character are displayed and the current player may continue guessing, otherwise the other player continues. Whenever the current player thinks he knows the word, he can also guess the word directly instead of guessing a character (but only during his turn). If he is right, the game stops and he has won, otherwise the other player continues with guessing either a character or a word.

Now, two players want to try out this game. As they know the word database the computer uses, they try to use this information to find a strategy for maximizing the probability of winning. They ask you if you can tell them the probability that the starting player wins, if both players use a strategy for maximizing their probability of winning the game.
 

Definition

    
Class:Hangman42
Method:probability
Parameters:String[]
Returns:double
Method signature:double probability(String[] words)
(be sure your method is public)
    
 

Notes

-You can assume the probability that the computer selects a certain word is 1 / number of words.
-The probability for winning is the same as the number of words for which the strategy used guarantees a win, divided by the total number of words.
 

Constraints

-words contains between 1 and 10 elements, inclusive.
-Each element of words consists of between 1 and 50 lowercase letters, inclusive.
-Each element of words contains the same number of characters.
-All elements of words are distinct.
 

Examples

0)
    
{"top","web","cam","buy","now"}
Returns: 0.6
The optimal guess for player 1 is 'w'. If this guess is correct, either "w--" or "--w" is displayed and player 1 can guess again. In both cases it is obvious which word the computer selected, so player 1's guess will guarantee him a win for both possibilities. If the guess is not correct, player 2 can for example guess that the word is "top". If this guess is not right, player 1 can guess one of the two remaining words (for example "cam"). So, player 1's strategy leads to a win if the word was either "web", "cam" or "now". That means his probability of winning is 3/5 = 0.6 .
1)
    
{"a"}
Returns: 1.0
The smallest word database.
2)
    
{"ozeexsuaihtuucqghqsjzqzugmaebvdrddyztehr",
"lvjvwhqyeqpapbjusjtxfbcgfbsudrbhpydzryyp",
"cigacdzesqanrlflmsxvhvtvtnzelbzlopcchdob",
"edqogzausmjxzoagpsssxwnmfranrrswjsdgqcqv",
"ptvbnhdcecegnnsofcxaqtizrkwvazfngvzgcsqb",
"guiqkikpwwbzgpvtikaaxxjitqkqfughdlmjtdax",
"gbubcxhxscszrcuzbggjmnzlzihftpmpmaamtxcp",
"tuijqvgvbiwbyjhjmkmmqlmhayvdqhlkpptqqide",
"yidryvjmpbjkdzhmhtoynhbwlbsehcbymltrddsj"}
Returns: 0.8888888888888888

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3068

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6518&pm=3068

Writer:

AdrianKuegel

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Math, Recursion, Simulation