Who will win Ghost?

The game of Ghost is played between two players who alternate saying a letter on each turn. At each point, the letters so far must start some valid English word. The loser is the player to complete a full word first. So, for example, if the letters so far are E-A-G-L, then the only valid next letter to say is "E" and so the next player will lose. (Even though there are longer words such as "eaglet".)

The challenge

You are to write a program or function to determine, given the letters so far, who will win assuming two perfect players. The input is a string representing the current state of the game, and a list of strings representing the dictionary of valid words. The output should distinguish whether the next player to go will win or lose.

Details

• The code must handle the case where the current state is empty. However, you may assume no word in the dictionary is empty.
• You may assume that each input string consists only of lowercase ASCII letters, i.e. a-z.
• You may assume the current state and all words in the dictionary have at most 80 characters each.
• The dictionary is guaranteed to be nonempty (to avoid the case where there is no valid first move).
• You may assume the "current state" will be valid: there will necessarily be some word starting with the current state; also, the current state will not be a full word, nor will any prefix of the current state be a full word.
• The dictionary will be prefiltered according to the rules of which "English words" are considered to be valid for the game - so for example, for a variant in which words of three or fewer letters don't end the game yet, the dictionary will be prefiltered to include only the words of four or more letters.
• You may assume the dictionary will be presorted.

Examples

Suppose the dictionary is:

abbot
eager
eagle
eaglet
earful
earring


Then for the following current states, the output should be as follows:

Current state   Result
=============   ======
loss
a               win
eag             win
eagl            loss
ear             win
earf            win
earr            loss


Likewise, for the word list at https://raw.githubusercontent.com/dschepler/ghost-word-list/master/wordlist.txt (produced on a Debian system using pcregrep '^[a-z]{4,80}$' /usr/share/dict/american-english) here is a possible session: Current state Result ============= ====== win h loss ho win hoa loss hoar win hoars loss  (And then the next move completes "hoarse".) Scoring This is : Shortest program in bytes for each programming language wins. • From review queue, I don't think this challenge is unclear. If you do, please post why. – mbomb007 Aug 22 '17 at 16:35 • I didn't vote to close, but I think the question could use a description of output. Must output be a boolean? One of two values? One of many values partitioned in two? – Jakob Aug 22 '17 at 16:47 • I'm fine with anything from which deriving a win/loss result is trivial. Either a truthy/falsey dichotomy (in either order), or one of two values, or something like positive vs. negative integer result, etc. – Daniel Schepler Aug 22 '17 at 17:04 • @mbomb007 I have voted as unclear. I can't really say what is unclear specifically because I don't understand the question. I've read it five times now and I still do not understand the task at all. – Sriotchilism O'Zaic Aug 22 '17 at 17:14 • @WheatWizard Each player must choose the next letter such that the partial word is still a prefix of a word in the dictionary. When there are no longer any such choices, then the game ends with the last player to go as the loser. – mbomb007 Aug 22 '17 at 18:11 4 Answers C++, 243 bytes (noncompetitive) FYI, here's the golfed version of my reference implementation (marked as noncompetitive since it's my own challenge). It expects the word list in the w parameter to be a null-terminated array (of null-terminated strings). It returns 1 if the next player will lose, or 0 if the next player will win. #define r return int g(char*s,char**w){struct N{int d=0;N*c[128]{};int l(){if(d)r 0;for(N*p:c)if(p&&p->l())r 0;r 1;}void a(char*s){*s?(c[*s]?:c[*s]=new N)->a(s+1),0:d=1;}N*f(char*s){r*s?c[*s]->f(s+1):this;}}d;for(;*w;d.a(*w++));r d.f(s)->l();}  Try it online. Expanded and commented version: int g(char* s, char** w) { /// Node of the prefix tree struct N { int d = 0; ///< 1 if the node represents a word in the dictionary N* c[128] {}; ///< child nodes, indexed by integer value of character // Optional, if you want to eliminate the memory leak from the // golfed version. (Though actually in practice, I would make // "c" into std::array<std::unique_ptr<N>, 128> so the default // destructor would be sufficient.) // ~N() { for (N* p : c) delete p; } /// \retval 1 if the next player going from this node will lose /// \retval 0 if they will win int l() { if (d) return 0; // last player lost, so the player who would // have gone next wins for (N* p : c) if (p && p->l()) return 0; // found a letter to play which forces the // other player to lose, so we win return 1; // didn't find any such letter, we lose } /// Add word \p s under this node void a(char* s) { *s ? (c[*s] ?: c[*s] = new N) // use existing child node or create new one ->a(s+1), 0 // the ,0 just makes the branches of // the ternary compatible : d = 1; } /// Find node corresponding to \p s N* f(char* s) { return *s ? c[*s]->f(s+1) : this; } } d; // d is root node of the prefix tree // Construct prefix tree for (; *w; d.a(*w++)) ; // Find node for input, then run the "loser" method return d.f(s)->l(); }  Python 3, 135129 84 bytes -4 bytes thanks to Mr. Xcoder! -42 bytes thanks to Daniel Schepler! g=lambda s,l:(s in l)or-min(g(w,l)for w in{w[:len(s)+1]for w in l if w[:len(s)]==s})  Try it online! A 1 indicates the current player will win, whereas a -1 indicates they will lose. • 133 bytes – Mr. Xcoder Aug 22 '17 at 16:22 • Not sure, but 131 bytes? – Mr. Xcoder Aug 22 '17 at 16:26 • On the full 61135-word dictionary I posted at github and empty state I haven't been able to run it to completion (it's been running several minutes already). I don't know the custom here for whether you need to be able to run all the test cases I posted in a reasonable time. (On the sandbox post, I did initially have a requirement that the code not be "horribly inefficient" but commenters suggested either dropping that or specifying an asymptotic running time - and I was afraid saying "linear in the size of the input" would be too restrictive.) – Daniel Schepler Aug 22 '17 at 19:55 • Here is an experiment with using an intermediate set to eliminate the duplicate recursive calls. With this, it's at least able to process the full dictionary in a few minutes. (I was also experimenting with another simplification, so the net result is a decrease to 87 bytes.) – Daniel Schepler Aug 23 '17 at 16:53 • @DanielSchepler Nice! I was working on a similar way to reduce recursive calls, but your method is a lot more concise! It also allows me to reduce this to a lambda. – notjagan Aug 23 '17 at 16:57 PHP, 192 154 100 98 bytes function t($w,$d){foreach(preg_grep("#^$w#",$d)as$p)if($p==$w||!t($w.$p[strlen($w)],$d))return 1;}


function returns 1 for win, NULL for loss.
Call with t(string $word,array$dictionary) or try it online.

breakdown

function t($w,$d)
{
// loop through matching words
foreach(preg_grep("#^$w#",$d)as$p)if($p==$w // if word is in dictionary (previous player lost) || // or !t($w.$p[strlen($w)],$d) // backtracking is falsy (next player loses) ) return 1; // then win // implicit return NULL }  JavaScript, 54 bytes l=>g=w=>!(w+0)||l.some(t=>t==w||!g(t.match(^${w}.)))


call it like this: f(wordlist_as_array)(current_word_as_string), it return true for win, false for lose.

quite bad performance T_T , only work with the small test case.

f=
l=>g=w=>!(w+0)||l.some(t=>t==w||!g(t.match(^\${w}.)))
<p><label>Word List:<br/><textarea id="wl"></textarea></label></p>
<p><label>Current:<input type="text" id="c" /></label></p>
<p><button onclick="out.textContent = f(wl.value.split('\n'))(c.value)">Check</button></p>
<p>Result: <output id="out"></output></p>

• Wow, that's an ingenious null-check! – Neil Aug 23 '17 at 8:05