Game Ghost dimainkan antara dua pemain yang bergantian mengucapkan huruf pada setiap belokan. Pada setiap titik, surat-surat sejauh ini harus memulai beberapa kata bahasa Inggris yang valid. Yang kalah adalah pemain untuk menyelesaikan satu kata penuh terlebih dahulu. Jadi, misalnya, jika surat-surat sejauh ini adalah EAGL, maka satu-satunya surat berikutnya yang valid untuk mengatakan adalah "E" dan pemain berikutnya akan kalah. (Meskipun ada kata-kata yang lebih panjang seperti "elang".)

Tantangan

Anda harus menulis program atau fungsi untuk menentukan, mengingat surat-surat sejauh ini, siapa yang akan menang dengan asumsi dua pemain sempurna. Input adalah string yang mewakili kondisi permainan saat ini, dan daftar string yang mewakili kamus kata-kata yang valid. Keluaran harus membedakan apakah pemain berikutnya yang akan menang atau kalah.

Detail

• Kode harus menangani kasus di mana keadaan saat ini kosong. Namun, Anda mungkin menganggap tidak ada kata dalam kamus yang kosong.
• Anda dapat mengasumsikan bahwa setiap string input hanya terdiri dari huruf ASCII huruf kecil, yaitu az.
• Anda dapat mengasumsikan keadaan saat ini dan semua kata dalam kamus masing-masing memiliki maksimal 80 karakter.
• Kamus dijamin tidak kosong (untuk menghindari kasus di mana tidak ada langkah pertama yang valid).
• Anda dapat menganggap "kondisi saat ini" akan valid: harus ada beberapa kata yang dimulai dengan kondisi saat ini; juga, kondisi saat ini tidak akan menjadi kata penuh, atau awalan dari kondisi saat ini tidak akan menjadi kata penuh.
• Kamus akan difilter sesuai dengan aturan "kata-kata bahasa Inggris" dianggap valid untuk permainan - jadi misalnya, untuk varian di mana kata-kata dari tiga atau lebih sedikit huruf belum mengakhiri permainan, kamus akan prefiltered untuk memasukkan hanya kata-kata dari empat huruf atau lebih.
• Anda dapat menganggap kamus akan didahului.

Contohnya

Misalkan kamus adalah:

abbot
eager
eagle
eaglet
earful
earring

Kemudian untuk kondisi saat ini, output harus sebagai berikut:

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

Demikian juga, untuk daftar kata di https://raw.githubusercontent.com/dschepler/ghost-word-list/master/wordlist.txt (dibuat menggunakan sistem Debian pcregrep '^[a-z]{4,80}$' /usr/share/dict/american-english) berikut ini adalah sesi yang memungkinkan:

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

(Dan kemudian langkah selanjutnya melengkapi "serak".)

Mencetak gol

Ini adalah kode-golf : Program terpendek dalam byte untuk setiap bahasa pemrograman yang menang.

JavaScript, 54 byte

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

sebut saja seperti ini: f (wordlist_as_array) (current_word_as_string), itu mengembalikan true untuk win, false untuk kalah.

kinerja T_T sangat buruk, hanya bekerja dengan test case kecil.

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 byte

^{-4 byte terima kasih kepada Tn. Xcoder !}

^{-42 byte terima kasih kepada 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})

Cobalah online!

A 1menunjukkan pemain saat ini akan menang, sedangkan a -1menunjukkan mereka akan kalah.

PHP, 192 154 100 98 byte

function t($w,$d){foreach(preg_grep("#^$w#",$d)as$p)if($p==$w||!t($w.$p[strlen($w)],$d))return 1;}

pengembalian fungsi 1untuk menang, NULLuntuk kerugian.
Hubungi dengan t(string $word,array $dictionary) atau coba online .

kerusakan

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 byte (tidak kompetitif)

FYI, inilah versi golf dari implementasi referensi saya (ditandai sebagai tidak kompetitif karena ini adalah tantangan saya sendiri). Itu mengharapkan daftar kata dalam wparameter menjadi array yang diakhiri dengan nol (dari string yang diakhiri dengan nol). Ia kembali 1jika pemain berikutnya akan kalah, atau 0jika pemain berikutnya akan menang.

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

Cobalah online.

Versi yang diperluas dan dikomentari:

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