El juego de Ghost se juega entre dos jugadores que se alternan diciendo una letra en cada turno. En cada punto, las letras hasta ahora deben comenzar con alguna palabra válida en inglés. El perdedor es el jugador que primero completa una palabra completa. Entonces, por ejemplo, si las letras hasta ahora son EAGL, entonces la única siguiente letra válida para decir es "E" y entonces el siguiente jugador perderá. (Aunque hay palabras más largas como "aguilucho").

El reto

Debe escribir un programa o función para determinar, dadas las letras hasta ahora, quién ganará asumiendo dos jugadores perfectos. La entrada es una cadena que representa el estado actual del juego y una lista de cadenas que representa el diccionario de palabras válidas. La salida debe distinguir si el próximo jugador que vaya ganará o perderá.

Detalles

• El código debe manejar el caso donde el estado actual está vacío. Sin embargo, puede suponer que ninguna palabra en el diccionario está vacía.
• Puede suponer que cada cadena de entrada consta solo de letras minúsculas ASCII, es decir, az.
• Puede asumir el estado actual y todas las palabras del diccionario tienen como máximo 80 caracteres cada una.
• Se garantiza que el diccionario no está vacío (para evitar el caso de que no haya un primer movimiento válido).
• Puede suponer que el "estado actual" será válido: necesariamente habrá alguna palabra que comience con el estado actual; Además, el estado actual no será una palabra completa, ni ningún prefijo del estado actual será una palabra completa.
• El diccionario se prefiltrará de acuerdo con las reglas de las cuales las "palabras en inglés" se consideran válidas para el juego, por ejemplo, para una variante en la que las palabras de tres o menos letras aún no terminan el juego, el diccionario prefiltrarse para incluir solo las palabras de cuatro o más letras.
• Puede suponer que el diccionario se clasificará previamente.

Ejemplos

Supongamos que el diccionario es:

abbot
eager
eagle
eaglet
earful
earring

Luego, para los siguientes estados actuales, la salida debería ser la siguiente:

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

Del mismo modo, para la lista de palabras en https://raw.githubusercontent.com/dschepler/ghost-word-list/master/wordlist.txt (producido en un sistema Debian usando pcregrep '^[a-z]{4,80}$' /usr/share/dict/american-english) aquí hay una posible sesión:

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

(Y luego el siguiente movimiento completa "ronco").

Puntuación

Esto es code-golf : gana el programa más corto en bytes para cada lenguaje de programación.

JavaScript, 54 bytes

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

llámalo así: f (wordlist_as_array) (current_word_as_string), devuelve verdadero para ganar, falso para perder.

bastante mal rendimiento T_T, solo funciona con el pequeño caso de prueba.

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 gracias al Sr. Xcoder !}

^{-42 bytes gracias 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})

Pruébalo en línea!

A 1indica que el jugador actual ganará, mientras que a -1indica que perderá.

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

la función vuelve 1para ganar, NULLpara perder.
Llame t(string $word,array $dictionary) o pruébelo en línea .

Descompostura

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 (no competitivo)

Para su información, aquí está la versión de golf de mi implementación de referencia (marcada como no competitiva ya que es mi propio desafío). Espera que la lista de palabras en el wparámetro sea una matriz terminada en nulo (de cadenas terminadas en nulo). Regresa 1si el próximo jugador pierde o 0si gana el siguiente jugador.

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

Pruébalo en línea.

Versión ampliada y 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();
}