# 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. – Ad Hoc Garf Hunter 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 # 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 # 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
}


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