# 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.

Source: codewars | Difficulty: EASY
Tags: String algorithms

Data structures

Game theory

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:
		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:
			if bob__ == -1:
				return 0
			initial = bob[bob__]
		else:
			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))) == 3 and (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


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)