# Our Setup

Alice and Bob work in an office. When the workload is light and the boss isn't looking, they often play simple word games for fun. This is one of those days!

# This Game

Today Alice and Bob are playing what they like to call _Mutations_, where they take turns trying to "think up" a new four-letter word identical to the prior word except for one letter. They just keep on going until their memories fail out.

# Their Words

Alice and Bob have memories of the same size, each able to recall `10` to `2000` different four-letter words. Memory words and initial game word are randomly taken from a list of `4000` (unique, four-letter, lowercased) words, any of which may appear in both memories.

The expression to "think up" a new word means that for their turn, the player must submit as their response word the first valid, unused word that appears in their memory (by lowest array index), as their memories are ordered from the most "memorable" words to the least.

# The Rules
* a valid response word must contain four different letters
* `1` letter is replaced while the other `3` stay in position
* it must be the lowest indexed valid word in their memory
* this word cannot have already been used during the game
* the final player to provide a valid word will win the game
* if 1st player fails 1st turn, 2nd can win with a valid word
* when both players fail the initial word, there is no winner

# Your Task
To determine the winner!

# Some Examples

`alice = plat,rend,bear,soar,mare,pare,flap,neat,clan,pore`

`bob   = boar,clap,farm,lend,near,peat,pure,more,plan,soap`

1) In the case of `word = "send"` and `first = 0`:
* Alice responds to `send` with `rend`
* Bob   responds to `rend` with `lend`
* Alice has no valid response to `lend`
* Bob   wins the game.

2) In the case of `word = "flip"` and `first = 1`:
* Bob   has no valid response to `flip`
* Alice responds to `flip` with `flap`
* Alice wins the game.

3) In the case of `word = "maze"` and `first = 0`:
* Alice responds to `maze` with `mare`
* Bob   responds to `mare` with `more`
* Alice responds to `more` with `pore`
* Bob   responds to `pore` with `pure`
* Alice responds to `pure` with `pare`
* Bob   has no valid response to `pare`
* Alice wins the game.

4) In the case of `word = "calm"` and `first = 1`:
* Bob   has no valid response to `calm`
* Alice has no valid response to `calm`
* Neither wins the game.

# Input

``` c
size_t n                    // number of words (10 <= n <= 2000)
const char *const alice[n]; // Alice's memory of four-letter words
const char *const bob[n];   // Bob's memory of four-letter words
const char* word;           // initial challenge word of the game
int first;                  // whom begins: 0 for Alice, 1 for Bob
```
``` python
alice  #  list of words in Alice's memory (10 <= n <= 2000)
bob    #  list of words in Bob's memory (10 <= n <= 2000)
word   #  string of the initial challenge word
first  #  integer of whom begins: 0 for Alice, 1 for Bob
```
``` javascript
let alice;  //  array of words in Alice's memory (10 <= n <= 2000)
let bob;    //  array of words in Bob's memory (10 <= n <= 2000)
let word;   //  string of the initial challenge word
let first;  //  integer of whom begins: 0 for Alice, 1 for Bob
```

# Output
``` c
return  0  //  if Alice wins
return  1  //  if Bob wins
return -1  //  if both fail
```
``` python
return  0  #  if Alice wins
return  1  #  if Bob wins
return -1  #  if both fail
```
``` javascript
return  0  //  if Alice wins
return  1  //  if Bob wins
return -1  //  if both fail
```

# Enjoy!

If interested, I also have [this kata](https://www.codewars.com/kata/5cb7baa989b1c50014a53333) as well as [this other kata](https://www.codewars.com/kata/5cab471da732b30018968071) to consider solving.

Difficulty: introductory

Starter code:

def mutations(alice, bob, word, first):
	

Solutions:
import re

def genMask(w):
    x = list(w)
    for i in range(len(w)):
        x[i] = '.'
        yield ''.join(x)
        x[i] = w[i]

def mutations(alice, bob, word, first):
    players, seen  = [alice,bob], {word}
    win, failed, i = -1, -1, first^1
    while 1:
        i    ^= 1
        lst   = players[i]
        reg   = re.compile('|'.join(genMask(word)))
        found = next((w for w in lst if reg.match(w) and w not in seen and len(set(w))==4), None)
        if found is None:
            if failed==i^1: break
            failed = i
        else:
            seen.add(found)
            word, win = found, i
            if failed!=-1: break
    return win

def mutations(alice, bob, word, first):
    seen = {word}
    mapping = {0:alice, 1:bob}
    prev_state,state = -1, -1

    def foo(word,first):
        nonlocal state, prev_state
        foo.counter += 1

        if foo.counter > 2 and state < 0 or foo.counter > 2 and prev_state < 0:
            return
        
        for a_word in mapping[first]:
            counter = 0
            for i,x in enumerate(a_word):
                if a_word[i] == word[i]:
                    counter += 1

            if counter == 3 and len(set(a_word))==4 and a_word not in seen:
                seen.add(a_word)
                prev_state = state
                state = first
                word = a_word
                break

        if counter==3 or state < 0:
            return foo(word,first^1)

    foo.counter = 0
    foo(word,first)
    return state

def mutations(alice, bob, matchWord, first):
    winner = -1
    aliceWords = list(alice)
    bobWords = list(bob)
    aliceFoundAWord = bobFoundAWord = True
    matchingWordFound = True
    numOfIncorrectLetters = 0
    firstRound = -1
    i = 0

    if matchWord in aliceWords: #removes the word from both Alice's and Bob's memory, as they are not allowed to be used again                 
        del aliceWords[aliceWords.index(matchWord)]    
    if matchWord in bobWords:
        del bobWords[bobWords.index(matchWord)]      
    while (aliceFoundAWord and bobFoundAWord and matchingWordFound) or (firstRound < 1):
        firstRound += 1
        i = 0
        numOfIncorrectLetters = 0
        matchingWordFound = False
        if not (first):
            aliceFoundAWord = False
            for word in aliceWords:
                for letter in word:
                    if word.find(letter) != word.rfind(letter):
                        break                    
                    if letter != matchWord[i]:
                        numOfIncorrectLetters += 1
                    i += 1
                    if (i == 4) and (numOfIncorrectLetters == 1):
                        aliceFoundAWord = True
                        matchingWordFound = True
                        del aliceWords[aliceWords.index(word)]
                        matchWord = word
                        if matchWord in bobWords:
                            del bobWords[bobWords.index(word)]                        
                        break
                i = 0
                numOfIncorrectLetters = 0
                if (aliceFoundAWord):
                    break        
        else:
            bobFoundAWord = False
            for word in bobWords:
                for letter in word:
                    if word.find(letter) != word.rfind(letter):
                        break
                    if letter != matchWord[i]:
                        numOfIncorrectLetters += 1
                    i += 1
                    if (i == 4) and (numOfIncorrectLetters == 1):
                        bobFoundAWord = True
                        matchingWordFound = True
                        del bobWords[bobWords.index(word)]
                        matchWord = word
                        if matchWord in aliceWords:
                            del aliceWords[aliceWords.index(word)]
                        break
                i = 0
                numOfIncorrectLetters = 0
                if (bobFoundAWord):
                    break  
        first = not (first)
    if (aliceFoundAWord):
        winner = 0
    elif (bobFoundAWord):
        winner = 1
    else:
        winner = -1
    return winner

def mutations(alice1, bob1, ini, take):
    alice, bob, take_up, initial = alice1.copy(), bob1.copy(), take, ini
    def do(initial):
        for _ in range(bob.count(initial)) : bob.remove(initial)
        for _ in range(alice.count(initial)) : alice.remove(initial)
    find_first=lambda word,li:next((i for i,j in enumerate(li)if sum(k!=l for k,l in zip(j, word))==1 and len(set(j))==4),-1)
    alice__, bob__ = find_first(initial, alice), find_first(initial, bob) 
    do(initial)
    if alice__ == -1 and  bob__ == -1 : return -1
    while True:
        alice__, bob__ = find_first(initial, alice), find_first(initial, bob)
        if take_up:  # bob
            if bob__ == -1 : return  0
            initial = bob[bob__]
        else:  # alice
            if alice__ == -1 : return 1
            initial = alice[alice__]
        do(initial)
        take_up ^= 1

def done(w, seen): return w in seen
def size(w): return len(w) == len(set(w))
def check(w, word):
    found = False
    for c1,c2 in zip(w, word):
        if c1 != c2:
            if found: return False
            else: found = True
    return True

def mutations(alice, bob, word, first):
    okay = lambda w: not done(w, seen) and size(w) and check(w, word)
    player = lambda: bob if first else alice
    seen, state = {word}, 0
    while True:
        try:
            word = next(filter(okay, player()))
            if state == 1: return first
            if state == 0: state = 2
            seen.add(word)
        except:
            if state == 1: return -1
            if state == 2: return 1 - first
            if state == 0: state = 1
        first = 1 - first

def mutations(a,b,w,f):
    z,t,i,P,U=-1,-1,f^1,[a,b],{w}
    while 1:
        i^=1
        u=next((x for x in P[i]if x not in U and sum(p==q for p,q in zip(x,w))==3and len(set(x))==4),'')
        if u:
            w,z,U=u,i,U|{u}
            if t!=-1:return z
        else:
            if t==i^1:return z
            t=i

def mutations(alice, bob, word, first):
    
    def isValid(w): return w not in seen and sum(a==b for a,b in zip(w,word))==3 and len(set(w))==4
    
    players, seen  = [alice,bob], {word}
    win, failed, i = -1, -1, first^1
    while 1:
        i    ^= 1
        lst   = players[i]
        found = next((w for w in lst if isValid(w)), None)
        if found is None:
            if failed==i^1: break
            failed = i
        else:
            seen.add(found)
            word, win = found, i
            if failed!=-1: break
    return win

def mutations(alice, bob, word, first):
    seen = {word}
    mapping = {0:alice, 1:bob}
    prev_state,state = -1, -1

    def foo(word,first):
        nonlocal state, prev_state
        foo.counter += 1

        if foo.counter > 2 and (state < 0 or prev_state < 0):
            return
        
        for a_word in mapping[first]:
            counter = 0
            for i,x in enumerate(a_word):
                if a_word[i] == word[i]:
                    counter += 1

            if counter == 3 and len(set(a_word))==4 and a_word not in seen:
                seen.add(a_word)
                prev_state = state
                state = first
                word = a_word
                break

        if counter==3 or state < 0:
            return foo(word,first^1)

    foo.counter = 0
    foo(word,first)
    return state

cmp=lambda a,b,f:(a,b)==(0,0) and -1 or a>b and 0 or a<b and 1 or a==b and not f and 1 or 0
def mutations(alice, bob, word, first):
    score = {0:0, 1:0}
    seen = {word}
    mapping = {0:alice, 1:bob}

    def foo(alice,bob,word,first):
        foo.counter += 1

        if foo.counter > 2 and not score[0] and not score[1]:
            return
        
        for a_word in mapping[first]:
            counter = 0
            for i,x in enumerate(a_word):
                if a_word[i] == word[i]:
                    counter += 1

            if counter == 3 and len(set(a_word))==4 and a_word not in seen:
                seen.add(a_word)
                word = a_word
                score[first] += 1
                break

        if counter==3 or not score[first]:
            return foo(alice,bob,word,first^1)

    foo.counter = 0
    foo(alice,bob,word,first)
    return cmp(score[0],score[1],first)

cmp=lambda a,b,f:(a,b)==(0,0) and -1 or a>b and 0 or a<b and 1 or a==b and not f and 1 or 0
def mutations(alice, bob, word, first):
    al,bo = 0,0
    start = first
    seen = {word}

    def foo(alice,bob,word,first):
        nonlocal al,bo,start
        if first == 0:
            for a_word in alice:
                c1 = 0
                for i,x in enumerate(a_word):
                    if a_word[i] == word[i]:
                        c1 += 1

                if c1 == 3 and len(set(a_word))==4 and a_word not in seen:
                    seen.add(a_word)
                    word = a_word
                    al += 1
                    return foo(alice,bob,word,first+1)
                    
            if not al and not start:
                return foo(alice,bob,word,first+1)
         
 
        else:
            for b_word in bob:
                c2 = 0
                for i,j in enumerate(b_word):
                    if b_word[i] == word[i]:
                        c2 += 1

                if c2 == 3 and len(set(b_word))==4 and b_word not in seen:
                    seen.add(b_word)
                    word = b_word
                    bo += 1
                    return foo(alice,bob,word,first-1)
            
            if not bo and start:
                return foo(alice,bob,word,first-1)
            

    foo(alice,bob,word,first)
    return cmp(al,bo,first)