Problem Statement
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
{"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 .
{"wwtkmcoj","lgsyduoi","oiqisear","hntxjrkf"}
Returns: 0.75
{"a"}
Returns: 1.0
The smallest word database.
{"ppk","bez","ltm","nev","roo"}
Returns: 0.6
{"advanced","absolute","anything","accepted","reflects","cleverly","coaching","winnings","overflow"}
Returns: 0.6666666666666666
{"abcdefghiz","abcdefghyj","abcdefgxik","abcdefwhil","abcdevghim","abcdufghin","abctefghio","absdefghio","arcdefghip","qbcdefghip"}
Returns: 0.5
{"aa","ab","ac","ad","ae","fg","fh","fi","fj","fk"}
Returns: 0.5
{"aaab","aaba","aabb","abaa","abab","abba","abbb","baaa","baab","baba"}
Returns: 1.0
{"hllba","zvcjh","fjftl","rrxld","lkodz","vwugd","jfodw"}
Returns: 0.7142857142857143
{"jmmmarhhpvdpopplneruuzjjiaibwbvzogqjaatzs","adfnkwylckfnlqhspqllqwysjpgefbmrhfekdkgmp","liaxgnqakfrvuajtogylkxopoabiuavkvxifqmbkb","qstebvlupnzioarhygtmoefnhmyrfsbhtzuvasuvz","eaiupcapffctsmziczotdzbwbntdvjifmqzemfajw","fkuxnlwdvkhfnlwtncsuvjkvfhxsoyxhjgfquxllz","gcghokcmhsrxzpemihtstabomyfkprduumxbwbbip","mseqrnzafqdxczihsrlmondelbittrdgeysvbdxee"}
Returns: 0.875
{"scuzzlaxugqpzcpqqzrzyfgkgqajmxnmchoukvnmfwx","wdyjtwfohvktljkjiuwszjusgorbjsigusombmlfoxs","lercedfuauzdrcwrljhvnxzeuhvtfxgfjvecddjqfhr","sbzxptkjpfneysdqcmxqsftdmdiapqottkgkjmssgza","uvuubbqnbmjrllhkrnhgykdjdnmjjycyblbjtbvgtlk","byiqklubhrydhkhdnpqgzlnaiukuhpiundgqwfnllwu","jrwptqxnowbusyvmsvlkujayjscqaklmbkwusvwdrek","xhjjgeopmutacxdoodjivsmjvsgpzjecymiueeuxzex"}
Returns: 0.875
{"abcdefghizqbcdefghizalcdefghizabckefgoizpbndefmhiz","abcdefghyjabcdefghyjalcdefghyjabckefgoyjpbndefmhyj","abcdefgxijabcdefgxijalcdefgxijabckefgxijpbndefmxij","abcdefwhijabcdefwhijalcdefwhijabckefwoijpbndefwhij","abcdevghijabcdevghijalcdevghijabckevgoijpbndevmhij","abcdufghijabcdufghijalcdufghijabckufgoijpbndufmhij","abctefghijabctefghijalctefghijabctefgoijpbntefmhij","absdefghijabsdefghijalsdefghijabskefgoijpbsdefmhij","arcdefghijarcdefghijarcdefghijarckefgoijprndefmhij","qbcdefghijqbcdefghizqlcdefghijqbckefgoijqbndefmhij"}
Returns: 0.6
{"ozeexsuaihtuucqghqsjzqzugmaebvdrddyztehr", "lvjvwhqyeqpapbjusjtxfbcgfbsudrbhpydzryyp", "cigacdzesqanrlflmsxvhvtvtnzelbzlopcchdob", "edqogzausmjxzoagpsssxwnmfranrrswjsdgqcqv", "ptvbnhdcecegnnsofcxaqtizrkwvazfngvzgcsqb", "guiqkikpwwbzgpvtikaaxxjitqkqfughdlmjtdax", "gbubcxhxscszrcuzbggjmnzlzihftpmpmaamtxcp", "tuijqvgvbiwbyjhjmkmmqlmhayvdqhlkpptqqide", "yidryvjmpbjkdzhmhtoynhbwlbsehcbymltrddsj"}
Returns: 0.8888888888888888
{"vjbaglrfkwjyuzdrxvhompvpmypqhhaqgjlutukb","lgujpiqdaxfxoxjavsdlmlsafemjkfglswpcsgiv","omqhozfneccvlqkscqwtqdxcknvchollwimvncvx","rmtatqhipgfvwlcpfbmsgmzejgnaefjbmzvrembv","ocvidozoyrbwptxbwdtgxhhkaxflolwsolwapmzm","dduisyvjstkhplfexwzbavkqhxgatjxieeatlspt","ehhpoczjutgnhhzmrsyibaczppytzzrhadtynyhq","vlrkjqvlnwwdismlggsbouzgneqloddaxxcbjrxz","uqxfisaynbrvrwwfqtmperqhnljolxpacxdbeetd"}
Returns: 0.8888888888888888
{"cxrkapsjxnsetbbhgtwxjejfyqdewkdnvgqzcetpalykfn","vwlaaghwciwahrnxrzkyaftiyasylnphntskssrlmpmcgx","htjmhyaqcyyrowoxpbmaviicyxlwayonlvmpqznbwwjgam","wkbcpbpcehadjhqoaroogmjvmmkehshtwvdxxbbgorphrq","awojqoxbevoeseodeiruiwjuuthiufipdioonwnbfmfpez","fdmcgwixmchdzqwiqyzgnbeulzosujvjwymdxdlkcvhtvr","yftzeifmfkekjtioegtkpgtnoeghmpcunpbtqjtuylynzh","xesxqgqzepssdxywpmgjmxsqlvcxsxivksjncyneiksimg","qvrvxkzbsskmiltqsoptivlsgknxkywaikcbaxfdoixjsx","wpqwpnktbocedlfwsxkxbyqhixqpjlevyixaarumojamtw"}
Returns: 0.9
{"lscozjmdsjwehokektmcrmujmterlxnhbftluhvuv","rpsdofichtxulskmszribwdbfshfwvejllxdcjvvi","smrazccwqdlffkczndjfiywfdbzjvimzsmhfixlgz","cfibnlblfsvuhweulbxyirvnhxwijlofbkdvlwrih","tatlewxofjppobtuimtcnkclettzumhmnubknjkgt","kddnfuxeefhcyfhacfghigaagoxbboooonsagmolr","lggvqmkjwgfysqrdmcscoycwshbizxsmxrfukqumf","meudentdjdbvxnvwwlsphqgsitrijyataqseyuxit","ucbhqgspfqyghyjludaauuapfdlkcntimhblqojzd","wemsyifmrufqssywwgmxggadqogkrizmjcwnwfesk"}
Returns: 0.9
{"gkverxxipmbwoevwhpvolnrsfafrkohfmknjeslgyvyssepls","elcuebyrnrhdydzouubocadpjdidbfrysqyezfjoerrxzzjrz","rbjyjaqjjlyvlesnxdnpcsoidmzovqekqsgfduzkpankhizqa","ljylhfsqkbeqzavicoyauphthxpjsaaxkyrmlxponwmypvame","aogxehfrwujrmniensugbzsjicbpxjryrryzqmoabgldevejq","gbellobqmlxurznewqlendnlcaspnougrzjeesaafttkavqem","nmiymlusdtrcolqqndkpshnrjdirtkbxfkzezledosannngcv","sogczbexhfoeldoukpajojexkcihtxlsbrzvjgfkxbqrvbdhe","nmbbzrnonmyhshmtbirqbrzvmvobaoddtukoakpberqlaywrd","jyesgpgaovcohfhynfwzbhmcqkktphplvefcrihxawqzkqiuk"}
Returns: 1.0
{"bjvwmoqbytwkiadrsvhgnwoqrtpjzxpwjtwlipvsbr","kehqyctlitxccxxvjoattvxxfjdlseqhkrqtglpmpv","pivicslylnkvoebcncsjfcmimlxprewtzpdyyjszzy","qearhjnwaminbcsjidlpwplvmllsxjckprefqrkira","bfmlyirhjnmjwpggjhswjfylcxpzlfqpxxwfcwxtwt","byoctzknvnvugtrmtgpehoyczzxhpcaalfamnxpzjk","akrafkdjaqpmnoodnznqrlhaswfmqbisbyincwnbek","fwqmmcrddhcdskqvgbwbhjcdxpnwzqiqiezezsuwts","yveqcbvwoguvtwvydcjwpqoupzofnairgcnxlnjrim","swabzsmamxcrxrannadcemaofohulfsmproezrovcr"}
Returns: 1.0
{"fnsna","emrop","epdkg","tergs","ttvjc"}
Returns: 0.8
{"qkqrfcsusgpffrxmbzpeeuwwehw","vzgrbbngjxolqwoidtpkhvfisza","dggyrtuvbgqazgmxmhzaugggmkb","uyjcntivluwtcgjaepdwlecdaen","srmalbwzhymeidavnmmtzhucflj","mwxevwjibfnkcwovuafhnihagji"}
Returns: 0.8333333333333334
{"wikzqaojoxtocrdxf","lgpugnymrwdhrrqqu","rzuktdxkxximhanpd","blsymwicllfzpxtxm","rdopaqpogozgbepfu","vjmooyngmxtppkzel","ryerfbrdgxlqcffsc"}
Returns: 0.7142857142857143
{"t","k","v","a","l","w","b"}
Returns: 0.5714285714285714
{"pufohuonaheyevlivuhecdr","igtzepuuwqfizueuvjehagh","dbapygjxtkvziliafjspbfj","aezitwcoxxqdznlujrcnynr","kapzpsohxzgdbljtdkldphm","oqsijuezxxrijfoifmytxsy","blyxyyezoqukkwuorgwvfdp"}
Returns: 0.8571428571428571
{"tkzcfs","ojyfeq","xvahzo","kxxikc","tnxmfo","pheqys","gbjprb","vwwtlz"}
Returns: 0.625
{"zkmcbdod","iypouxhr","lbkqplay","kcxhnhgc","panzjwfx","iilsuvwx","azczjblc","ntvahxlb","xywdcxni","fhrfvwls"}
Returns: 0.7
{"vjghmnritvyswxo","zywbrtqipfgryou","jlenewmenfludzq","jryzlxpcawofauh","ljjovaxbghhzceo","caglxmgryvayzbv","nqtpstjzynbvwrm","xolsyzsefgvdqzb","xfodtoyqvowykso"}
Returns: 0.7777777777777778
{"sct","oii","rmi","dap","yba","tsb","ifp","smu","dwo"}
Returns: 0.5555555555555556
{"caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab","baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad"}
Returns: 1.0
Catches an overflow mistake if int is used instead of long for the known positions bitmask.
{ "ozeexsuaihtuucqghqsjzqzugmaebvdrddyztehr", "lvjvwhqyeqpapbjusjtxfbcgfbsudrbhpydzryyp", "cigacdzesqanrlflmsxvhvtvtnzelbzlopcchdob", "edqogzausmjxzoagpsssxwnmfranrrswjsdgqcqv", "ptvbnhdcecegnnsofcxaqtizrkwvazfngvzgcsqb", "guiqkikpwwbzgpvtikaaxxjitqkqfughdlmjtdax", "gbubcxhxscszrcuzbggjmnzlzihftpmpmaamtxcp", "tuijqvgvbiwbyjhjmkmmqlmhayvdqhlkpptqqide", "yidryvjmpbjkdzhmhtoynhbwlbsehcbymltrddsj" }
Returns: 0.8888888888888888
{ "abcdefgh", "ghghghgh", "fgfgfgfg", "efefefef", "ztztztzt", "tztztztz", "zyzyzyzy", "rrrrrrrr", "rererere", "abdczfgh" }
Returns: 0.7
{ "aab", "aba", "abb" }
Returns: 1.0
{ "top", "web", "cam", "buy", "now" }
Returns: 0.6
{ "a", "b" }
Returns: 0.5