O jogo Ghost é jogado entre dois jogadores que se alternam dizendo uma carta em cada turno. Em cada ponto, as letras até agora devem iniciar uma palavra em inglês válida. O perdedor é o jogador que deve completar uma palavra completa primeiro. Assim, por exemplo, se as letras até agora são EAGL, a única próxima letra válida a dizer é "E" e o próximo jogador perderá. (Mesmo que exista palavras mais longas como "aguia").

O desafio

Você deve escrever um programa ou função para determinar, dadas as letras até agora, quem vencerá assumindo dois jogadores perfeitos. A entrada é uma sequência que representa o estado atual do jogo e uma lista de sequências que representam o dicionário de palavras válidas. A saída deve distinguir se o próximo jogador a vencer ganhará ou perderá.

Detalhes

• O código deve lidar com o caso em que o estado atual está vazio. No entanto, você pode assumir que nenhuma palavra no dicionário está vazia.
• Você pode assumir que cada sequência de entrada consiste apenas em letras ASCII minúsculas, ou seja, az.
• Você pode assumir o estado atual e todas as palavras no dicionário têm no máximo 80 caracteres cada.
• É garantido que o dicionário não é vazio (para evitar o caso em que não há primeiro movimento válido).
• Você pode assumir que o "estado atual" será válido: haverá necessariamente alguma palavra começando com o estado atual; Além disso, o estado atual não será uma palavra completa, e nenhum prefixo do estado atual será uma palavra completa.
• O dicionário será pré-filtrado de acordo com as regras em que "palavras em inglês" são consideradas válidas para o jogo - por exemplo, para uma variante na qual palavras de três ou menos letras ainda não terminam o jogo, o dicionário será ser pré-filtrado para incluir apenas as palavras de quatro ou mais letras.
• Você pode assumir que o dicionário será pré-selecionado.

Exemplos

Suponha que o dicionário seja:

abbot
eager
eagle
eaglet
earful
earring

Em seguida, para os seguintes estados atuais, a saída deve ser a seguinte:

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

Da mesma forma, para a lista de palavras em https://raw.githubusercontent.com/dschepler/ghost-word-list/master/wordlist.txt (produzida em um sistema Debian usando pcregrep '^[a-z]{4,80}$' /usr/share/dict/american-english), aqui está uma sessão possível:

Current state   Result
=============   ======
                win
h               loss
ho              win
hoa             loss
hoar            win
hoars           loss

(E então a próxima jogada termina "rouca".)

Pontuação

Este é o código-golf : O programa mais curto em bytes para cada linguagem de programação vence.

JavaScript, 54 bytes

l=>g=w=>!(w+0)||l.some(t=>t==w||!g(t.match(`^${w}.`)))

chame assim: f (wordlist_as_array) (current_word_as_string), retorna true para vitória, false para perda.

desempenho muito ruim T_T, só funciona com o pequeno caso de teste.

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>

Python 3 , 135 129 84 bytes

^{-4 bytes graças ao Sr. Xcoder !}

^{-42 bytes graças a 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})

Experimente online!

A 1indica que o jogador atual vencerá, enquanto a -1indica que eles perderão.

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

função retorna 1para a vitória, NULLpara a perda.
Ligue t(string $word,array $dictionary) ou experimente online .

demolir

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
}

C ++, 243 bytes (não competitivo)

Para sua informação, aqui está a versão básica da minha implementação de referência (marcada como não competitiva, pois é meu próprio desafio). Ele espera que a lista de palavras no wparâmetro seja uma matriz terminada em nulo (de cadeias terminadas em nulo). Ele retorna 1se o próximo jogador perder ou 0se o próximo jogador vencer.

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

Experimente online.

Versão expandida e comentada:

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