TopCoder problem "AWordGame" used in TCCC '04 Round 2 (Division I Level Three)



Problem Statement

    

Consider the following game played between two players (let's call them Joe and Mary): Joe starts the game by thinking of some English word. He doesn't tell Mary what word, but instead tells Mary the first letter in his word. Now it's Mary's turn, who must think of a word that starts with the letter Joe has revealed. She then tells Joe the first two letters of her word. Now Joe must think of some word again (which may or may not be the same as Joe's original word), starting with the two letters of Mary's word, and tell Mary the first three letters in his word.

This procedure is repeated until the letters that are spoken by either Joe or Mary form a complete word. The player who first forms a complete word loses the game. This means that even if Joe thinks of the word "fire" and tells Mary the first three letters, "fir", he loses because "fir" is also a valid English word.

In reality, the player with the biggest word knowledge will most often win this game, but in this problem we will assume that both players know exactly the same words (and that none of them bluff or cheat). If both players play perfectly, it's possible to determine the outcome of the game. We define "perfect play" to be when a player strives to win the game in as few turns as possible (knowing that his opponent also plays perfectly), but also, if he/she can't win the game, to lose as slowly as possible. See examples 0 and 1 for clarification.

The outcome of the game is the final word said by the player who loses. Note that if the length of this word is odd, it means the second player will win since the first player will always say sequences with an odd number of letters, and vice versa. If at any point it doesn't matter which letter a player chooses, he/she will choose the one that is alphabetically first (see example 2).

Create a class AWordGame containing the method outcome that takes a String[] wordList containing the words that both players know, and returns a String, the final word said by the player that loses the game. Each element in wordList will contain a space separated list of words.

 

Definition

    
Class:AWordGame
Method:outcome
Parameters:String[]
Returns:String
Method signature:String outcome(String[] wordList)
(be sure your method is public)
    
 

Notes

-The words in wordList may not necessarily be English words, or words in any language at all (see example 3).
-You should assume that the players are aware that both players are using the same word list.
 

Constraints

-wordList will contain between 1 and 50 elements inclusive.
-Each element in wordList will contain between 1 and 50 characters, inclusive.
-wordList will contain a space separated list of lowercase words ('a'-'z').
-Each word in wordList will be between 1 and 20 characters, inclusive.
-No word will appear more than once in wordList.
-Elements in wordList will not contain leading or trailing spaces.
-There will be exactly one space between each word in wordList.
 

Examples

0)
    
{"pascal program programmer task tree",
 "treacherous treachery tread trace"}
Returns: "treacherous"

Let's call the two players Joe and Mary, as before. At the beginning of the game, Joe can choose between the letters 'p' and 't', since all words in the wordlist start with either of these letters. Assume first that he chooses 'p'. Mary can then choose 'a', which will narrow down the possible words left to only "pascal". Since that's a word with even length, Mary will lose the game if she chooses 'a'. However, if she chooses 'r', so the two first letters are "pr", she will win the game since Joe will be forced to say "program". Hence Joe will lose the game after 7 turns if he starts the game with 'p'.

If Joe starts with 't', Mary will choose 'r' since choosing 'a' will lead to the work "task" which causes Joe to win. Now Joe will choose 'e' as the third letter since choosing 'a' will cause Joe lose the game with the word "trace" in two more turns. Mary is forced to select 'a' (the four first letters are now "trea"), and Joe must select 'c' to avoid immediate loss. The next three letters, 'h' (by Mary), 'e' (by Joe), 'r' (by Mary) are all forced. Joe can now choose between 'y' and 'o', but both these choices will also lead to a loss. Hence Joe will always lose the game, no matter what he does. The slowest loss is along the most recent path discussed, eventually leading to the word "treacherous".

1)
    
{"pascal programmer task tree",
 "treacherous treachery tread trace"}
Returns: "programmer"

Here we have the same word list as above, with the exception that the word "program" has been removed. If Joe starts the game with 't', he will of course lose again since the absence of "program" won't affect the outcome then. If he chooses 'p' however, he will win the game, because the two words starting with 'p' both have even length. Mary, who after Joe's first turn can select which of the two words will be left, will of course select 'r' since the word "programmer" is longer than "pascal" (and thus a slower loss).

2)
    
{"academic","base","board","cola","code","cute","hack"}
Returns: "code"

If Joe starts with 'b', he will lose the game because Mary will then select 'o' and win the game with the word "board". If Joe starts with some other letter, he will win the game since all other words have even length. The fastest win is any of the words "code", "cola", "cute" or "hack" (but not "academic").

Since selecting both 'c' and 'h' will lead to a fastest win, Joe will select 'c' because it's the first of these letters alphabetically. Mary can select between 'o' and 'u', but since both words will lead to a loss in two more turns, she chooses 'o' which comes before 'u' in the alphabet. Similarly, Joe will next time choose 'd' (comes before 'l') and the final word will then be "code".

3)
    
{"lxxatbwhoh tooj lgwlu xiub lgwdinr rjjmufijoom",
 "vfdx toskry xhttofxo rkgqmb xiyyvyo qwbcpjcz",
 "lgquy ruyyptjv vazlfwy ruyypguoofimw qwbaarpfkukk",
 "xinhekafyi laehdkt lxxyerjt torxi lxxatijcg rkys",
 "xpktuvhcxhbg xiyyddlmf vazlfkxp xhf qwbaivq",
 "tookxlfs xiyydvil lxxatbng qwgzkvt rjlmcuwdug",
 "tdjlbbsr lxtoivq lwevhyms vfdo tfci lwevhyxmmm",
 "xpun qexfaistucs xinhgfyv qexxjfg xvljvc",
 "qwgzgina ruyqzuxbyovm ladihus rjjmufie",
 "qwgzgif xhnqem lwevhner xpuedqzd lpmedevkt",
 "vzefddtid lpmeji tfcypcvkqa tdjlbbcrm rjltci",
 "xhttofxfb xvljve xliwbcyxwg tookxf xhnqnw lgqvnh",
 "qwbqiu tdjlbbcz laehdycq lgqul qwbcpr lwevhyxi",
 "xpktuvhyc tdly rntxz xpanwsck laehdycz",
 "qwgzkva ruyypguj ruyqvsz rntg xibyr qwc xhnss",
 "xltrqddu vzcsdu qwbaijk lwevhymb xinhgfyo qwgzgf",
 "xhnqnggu toskrtau rjlmcums toskwaks xiyydvgx",
 "xiut qwbaartdb qexo rjlquefm xinl rjjifftthu",
 "rkyb lpmvbfn tfcpmbo rjlmczay rpt xltennu",
 "lgwdirzi lpmtvbija xpanwscbh tfur xhnqngrnhci",
 "xltrqbwdbl xlbwe rkghbk qwgzkk tdjw tdjry xvlfztz",
 "qwbaarpuyyse toswj xhttozvtv qwgc lxy toskrtawp",
 "rkgqx lgwdings xinhgfx lxtjtipnoy tfcpmbawxv",
 "vazlfwlo lpmvbxcct tfcpo lgqvnq lgkxgg rjlmczrm",
 "xpke rnte vajnf tfuwqdp qom xinhgcmsbmi tookxlfu",
 "xibyd xpatx lwevhnbn ladihuxw xpuep lxxaq vui",
 "lgkwbgs xvv tfuariim vazb xhva xinjovn xltrqdnqwy",
 "rjlmil xinhgcmk vzyvo lgwdplzpcon xiyydvgge ladp",
 "tdjlbudh lxxb lxxyerjynyx qwf xliwgsno lxtjetr",
 "xhttoftrvcabo xiyyddlqf xinheijxf rkghbn tfcype",
 "vfk xvayc xvlfzti laey rjltgh lgkmp rql vltqmow",
 "vzcsm qwbaivjn lpmvbxcwj qexxjfh lxtoivjrd",
 "lxxydxb xltl toskway xuyf tdlu tfuwhkp lxxatbwp",
 "lgkxgt qexfaiku xpktgyllgg vaq xlbiv lpmtvbikk",
 "lpmtvbgfo xiyphm tfcpmbau ruyd xlbil rkykcbf",
 "xpktgiusyzg lwevhnesh tdjrfy xhnsqe vzcq lgkmk",
 "lgwdirzsec vzefddtdbx lxtoii rjlmczau torak",
 "lpmtvbgoavjeq lxtjtipmhy xltrqddg vltqmytw",
 "rlxnh laehr xhtfmxvjn vltqmycl lgkwe qwbaijhx",
 "rjlmczro rkiaj xpktgia lwevuwow ruyqvsln lxtjtihl",
 "tdssjxz xiyydvie qwbaartk torax xlbwa xinheiha",
 "xvsmy vzcsds ruyqzuykr toskwakl tdjrfg vflz lxta",
 "xhnqnggj lxtoivjw tfuwhr lxtjetdp qexxjtg",
 "rnm xiue xpj vazlfwlfdg xhttozqr rkykcbo",
 "qwbcpjcmv tfuardg qwgzginklo tdssjd tfuardti lxl",
 "rlxb xhttye lwevuwl lgwiw rkykcmhltv qwgbsrgo",
 "tfuwqdgbh ruyqzxw lwemx xiypf xltrqbwm",
 "lpmedevcfkt"}
Returns: "tfcpmbawxv"

Random word list.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5007&pm=2296

Writer:

Yarin

Testers:

lbackstrom , schveiguy

Problem categories:

Recursion, Search