Who will win Ghost?

Question

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 code-golf: Shortest program in bytes for each programming language wins.

Answer 1

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>

Answer 2

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
}

Answer 3

Python 3, 135 129 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.

Answer 4

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();
}