We are given non-negative integers nums[i] which are written on a chalkboard.  Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first.  If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses.  (Also, we'll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return True if and only if Alice wins the game, assuming both players play optimally.


Example:
Input: nums = [1, 1, 2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.



Notes: 


       1 <= N <= 1000. 
       0 <= nums[i] <= 2^16.

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Game theory

Mathematics

Starter code: class Solution:
    def xorGame(self, nums: List[int]) -> bool:


Solutions:
class Solution:

	def validTicTacToe(self, board):

		def win(board, w):
			for i in range(3):
				if board[i] == w * 3:
					return True
			for i in range(3):
				if board[0][i] == w and board[1][i] == w and (board[2][i] == w):
					return True
			sign = True
			for i in range(3):
				if board[i][i] != w:
					sign = False
			if sign:
				return True
			sign = True
			for i in range(3):
				if board[i][2 - i] != w:
					sign = False
			if sign:
				return True
		Xnum = 0
		Onum = 0
		for ss in board:
			for s in ss:
				if s == 'X':
					Xnum += 1
				if s == 'O':
					Onum += 1
		if win(board, 'X'):
			if Xnum == Onum + 1:
				return True
			else:
				return False
		if win(board, 'O'):
			if Xnum == Onum:
				return True
			else:
				return False
		if Xnum == Onum or Xnum == Onum + 1:
			return True
		else:
			return False


class Solution:

	def validTicTacToe(self, board):
		xoDict = {'X': [], 'O': [], ' ': []}
		for i in range(0, 3):
			for j in range(0, 3):
				if board[i][j] == 'X':
					xoDict['X'] += ([i, j],)
				elif board[i][j] == 'O':
					xoDict['O'] += ([i, j],)
				elif board[i][j] == ' ':
					xoDict[' '] += ([i, j],)
		if len(xoDict['O']) > len(xoDict['X']):
			return False
		if len(xoDict['X']) - len(xoDict['O']) > 1:
			return False
		xwin = self.check(board, 'X')
		owin = self.check(board, 'O')
		if xwin and owin:
			return False
		if xwin and len(xoDict['X']) == len(xoDict['O']):
			return False
		if owin and len(xoDict['X']) > len(xoDict['O']):
			return False
		return True

	def check(self, board, char):
		for i in range(0, 3):
			if board[i][0] == char and board[i][1] == char and (board[i][2] == char):
				return True
		for i in range(0, 3):
			if board[0][i] == char and board[1][i] == char and (board[2][i] == char):
				return True
		if board[0][0] == char and board[1][1] == char and (board[2][2] == char):
			return True
		if board[0][2] == char and board[1][1] == char and (board[2][0] == char):
			return True
		return False


class Solution:

	def validTicTacToe(self, board):
		cross = 0
		circle = 0
		for i in range(3):
			for j in range(3):
				if board[i][j] == 'X':
					cross += 1
				if board[i][j] == 'O':
					circle += 1
		if cross < circle or cross - circle > 1:
			return False
		cross_winning = 0
		circle_winning = 0
		for i in range(3):
			if board[i][0] == board[i][1] == board[i][2]:
				if board[i][0] == 'X':
					cross_winning += 1
				elif board[i][0] == 'O':
					circle_winning += 1
			if board[0][i] == board[1][i] == board[2][i]:
				if board[0][i] == 'X':
					cross_winning += 1
				elif board[0][i] == 'O':
					circle_winning += 1
		if board[0][0] == board[1][1] == board[2][2]:
			if board[0][0] == 'X':
				cross_winning += 1
			elif board[0][0] == 'O':
				circle_winning += 1
		if board[0][2] == board[1][1] == board[2][0]:
			if board[0][2] == 'X':
				cross_winning += 1
			elif board[0][2] == 'O':
				circle_winning += 1
		if cross_winning > 0 and circle_winning > 0:
			return False
		if cross_winning > 0 and cross <= circle:
			return False
		if circle_winning > 0 and circle < cross:
			return False
		return True


class Solution:

	def validTicTacToe(self, board):
		num_X = 0
		num_O = 0
		for i in range(3):
			for j in range(3):
				if board[i][j] == 'X':
					num_X += 1
				elif board[i][j] == 'O':
					num_O += 1
		if num_X < num_O or num_X > num_O + 1:
			return False

		def win(board, total_X, total_O):
			for i in range(3):
				num_X = 0
				num_O = 0
				for j in range(3):
					if board[i][j] == 'X':
						num_X += 1
					elif board[i][j] == 'O':
						num_O += 1
				if num_X == 3:
					return total_X > total_O
				if num_O == 3:
					return total_X == total_O
			for j in range(3):
				num_X = 0
				num_O = 0
				for i in range(3):
					if board[i][j] == 'X':
						num_X += 1
					elif board[i][j] == 'O':
						num_O += 1
				if num_X == 3:
					return total_X > total_O
				if num_O == 3:
					return total_X == total_O
			num_X = 0
			num_O = 0
			for i in range(3):
				if board[i][i] == 'X':
					num_X += 1
				elif board[i][i] == 'O':
					num_O += 1
			if num_X == 3:
				return total_X > total_O
			if num_O == 3:
				return total_X == total_O
			num_X = 0
			num_O = 0
			for i in range(3):
				if board[i][2 - i] == 'X':
					num_X += 1
				elif board[i][2 - i] == 'O':
					num_O += 1
			if num_X == 3:
				return total_X > total_O
			if num_O == 3:
				return total_X == total_O
			return True
		return win(board, num_X, num_O)


class Solution:

	def validTicTacToe(self, board):
		(O, X) = (0, 0)
		for r in board:
			for c in r:
				if c == 'O':
					O += 1
				elif c == 'X':
					X += 1
		if O - X > 0:
			return False
		if X - O > 1:
			return False
		if X - O == 0:
			for r in board:
				if r == 'XXX':
					return False
			for c in range(2):
				if board[0][c] == board[1][c] == board[2][c] == 'X':
					return False
			if board[0][0] == board[1][1] == board[2][2] == 'X':
				return False
			if board[2][0] == board[1][1] == board[0][2] == 'X':
				return False
		else:
			for r in board:
				if r == 'OOO':
					return False
			for c in range(2):
				if board[0][c] == board[1][c] == board[2][c] == 'O':
					return False
			if board[0][0] == board[1][1] == board[2][2] == 'O':
				return False
			if board[2][0] == board[1][1] == board[0][2] == 'O':
				return False
		return True


class Solution:

	def validTicTacToe(self, board):
		(O, X) = (0, 0)
		for r in board:
			for c in r:
				if c == 'O':
					O += 1
				elif c == 'X':
					X += 1
		if O - X > 0:
			return False
		if X - O > 1:
			return False
		for c in range(2):
			if board[0][c] == 'X' and board[1][c] == 'X' and (board[2][c] == 'X'):
				return X - O == 1
			if board[c][0] == 'X' and board[c][1] == 'X' and (board[c][2] == 'X'):
				return X - O == 1
		if board[0][0] == 'X' and board[1][1] == 'X' and (board[2][2] == 'X'):
			return X - O == 1
		if board[2][0] == 'X' and board[1][1] == 'X' and (board[0][2] == 'X'):
			return X - O == 1
		for c in range(2):
			if board[0][c] == 'O' and board[1][c] == 'O' and (board[2][c] == 'O'):
				return X - O == 0
			if board[c][0] == 'O' and board[c][1] == 'O' and (board[c][2] == 'O'):
				return X - O == 0
		if board[0][0] == 'O' and board[1][1] == 'O' and (board[2][2] == 'O'):
			return X - O == 0
		if board[2][0] == 'O' and board[1][1] == 'O' and (board[0][2] == 'O'):
			return X - O == 0
		return True


class Solution:

	def validTicTacToe(self, board):
		targetState = tuple(board)
		startingState = ('   ', '   ', '   ')
		stateStack = [startingState]
		visited = set()
		while len(stateStack) > 0:
			curState = stateStack.pop()
			if curState == targetState:
				return True
			if curState in visited:
				continue
			visited.add(curState)
			if any((r == 'XXX' for r in curState)) or any((r == 'OOO' for r in curState)) or any((''.join([curState[i][j] for i in range(3)]) == 'XXX' for j in range(3))) or any((''.join([curState[i][j] for i in range(3)]) == 'OOO' for j in range(3))) or (curState[0][0] == curState[1][1] == curState[2][2] == 'X') or (curState[0][0] == curState[1][1] == curState[2][2] == 'O') or (curState[0][2] == curState[1][1] == curState[2][0] == 'X') or (curState[0][2] == curState[1][1] == curState[2][0] == 'O'):
				continue
			moves = set()
			for (i, row) in enumerate(curState):
				for (j, cell) in enumerate(row):
					if cell == ' ' and cell != targetState[i][j]:
						moves.add((i, j, targetState[i][j]))
			if len(moves) == 0:
				continue
			numX = sum((r.count('X') for r in curState))
			numO = sum((r.count('O') for r in curState))
			if numX == numO:
				curTurn = 'X'
			else:
				curTurn = 'O'
			for (i, j, symbol) in moves:
				if symbol != curTurn:
					continue
				newState = [curState[t] for t in range(3)]
				newState[i] = curState[i][:j] + curTurn + curState[i][j + 1:]
				stateStack.append(tuple(newState))
		return False


class Solution:

	def validTicTacToe(self, board):
		(x_count, o_count) = (0, 0)
		for string in board:
			for c in string:
				if c == 'X':
					x_count += 1
				if c == 'O':
					o_count += 1
		if x_count - o_count >= 2 or x_count - o_count < 0:
			return False
		x_win = 0
		o_win = 0
		if board[0] == 'XXX' or board[1] == 'XXX' or board[2] == 'XXX':
			x_win += 1
		if board[0] == 'OOO' or board[1] == 'OOO' or board[2] == 'OOO':
			o_win += 1
		if board[0][0] + board[1][0] + board[2][0] == 'XXX' or board[0][1] + board[1][1] + board[2][1] == 'XXX' or board[0][2] + board[1][2] + board[2][2] == 'XXX':
			x_win += 1
		if board[0][0] + board[1][0] + board[2][0] == 'OOO' or board[0][1] + board[1][1] + board[2][1] == 'OOO' or board[0][2] + board[1][2] + board[2][2] == 'OOO':
			o_win += 1
		if board[0][0] + board[1][1] + board[2][2] == 'XXX' or board[2][0] + board[1][1] + board[0][2] == 'XXX':
			x_win += 1
		if board[0][0] + board[1][1] + board[2][2] == 'OOO' or board[2][0] + board[1][1] + board[0][2] == 'OOO':
			o_win += 1
		if x_win == 1 and o_win == 1:
			return False
		if x_win == 1 and x_count - o_count != 1 or (o_win == 1 and o_count != x_count):
			return False
		return True


class Solution:

	def isWin(self, board, c):
		for i in range(3):
			if board[0][i] == c and board[1][i] == c and (board[2][i] == c):
				return True
		for i in range(3):
			if board[i][0] == c and board[i][1] == c and (board[i][2] == c):
				return True
		if board[0][0] == c and board[1][1] == c and (board[2][2] == c) or (board[0][2] == c and board[1][1] == c and (board[2][0] == c)):
			return True
		return False

	def validTicTacToe(self, board):
		o_cnt = 0
		x_cnt = 0
		for i in range(3):
			for j in range(3):
				x_cnt += 1 if board[i][j] == 'X' else 0
				o_cnt += 1 if board[i][j] == 'O' else 0
		if o_cnt > x_cnt or x_cnt > o_cnt + 1:
			return False
		if o_cnt == x_cnt and self.isWin(board, 'X') or (x_cnt == o_cnt + 1 and self.isWin(board, 'O')):
			return False
		return True


class Solution:

	def validTicTacToe(self, board):
		x = 0
		o = 0
		win_o = 0
		win_x = 0
		for i in range(3):
			for j in range(3):
				if board[i][j] == 'X':
					x += 1
				elif board[i][j] == 'O':
					o += 1
			if board[i] == 'XXX':
				win_x += 1
			elif board[i] == 'OOO':
				win_o += 1
			if board[0][i] == board[1][i] == board[2][i]:
				if board[0][i] == 'X':
					win_x += 1
				elif board[0][i] == 'O':
					win_o += 1
		if board[0][0] == board[1][1] == board[2][2]:
			if board[0][0] == 'O':
				win_o += 1
			elif board[0][0] == 'X':
				win_x += 1
		if board[2][0] == board[1][1] == board[0][2]:
			if board[2][0] == 'O':
				win_o += 1
			elif board[2][0] == 'X':
				win_x += 1
		if x > o + 1 or x < o or (win_o > 0 and win_x > 0):
			return False
		if win_x > 0 and x == o:
			return False
		if win_o > 0 and x > o:
			return False
		return True


class Solution:

	def validTicTacToe(self, board):
		(valid_X, valid_O) = (0, 0)
		(cnt_X, cnt_O) = (0, 0)
		for row in board:
			if row == 'XXX':
				valid_X += 1
			elif row == 'OOO':
				valid_O += 1
			cnt_X += row.count('X')
			cnt_O += row.count('O')
		(a, b, c) = board
		for col in zip(a, b, c):
			if col == 'XXX':
				valid_X += 1
			elif col == 'OOO':
				valid_O += 1
		if board[1][1] != ' ':
			if board[0][0] == board[2][2] == board[1][1]:
				if board[1][1] == 'X':
					valid_X += 1
				else:
					valid_O += 1
			if board[2][0] == board[0][2] == board[1][1]:
				if board[1][1] == 'X':
					valid_X += 1
				else:
					valid_O += 1
		if valid_X + valid_O > 1:
			return False
		if valid_X:
			if cnt_X - cnt_O != 1:
				return False
		elif valid_O:
			if cnt_X != cnt_O:
				return False
		elif not 0 <= cnt_X - cnt_O <= 1:
			return False
		return True


class Solution:

	def playerWon(self, board, player):
		for i in range(3):
			if board[0][i] == board[1][i] == board[2][i] == player:
				return True
		for i in range(3):
			if board[i][0] == board[i][1] == board[i][2] == player:
				return True
		if board[0][0] == board[1][1] == board[2][2] == player or board[0][2] == board[1][1] == board[2][0] == player:
			return True
		return False

	def validTicTacToe(self, board):
		count_x = sum((b.count('X') for b in board))
		count_o = sum((b.count('O') for b in board))
		if count_x - count_o > 1 or count_x - count_o < 0:
			return False
		if self.playerWon(board, 'X') and count_x - count_o != 1:
			return False
		if self.playerWon(board, 'O') and count_x - count_o != 0:
			return False
		return True


class Solution:

	def validTicTacToe(self, board):
		o_cnt = 0
		x_cnt = 0
		bingo_x = 0
		bingo_o = 0
		for i in range(3):
			if board[i] == 'O' * 3:
				bingo_o += 1
			if board[i] == 'X' * 3:
				bingo_x += 1
			if board[0][i] == board[1][i] == board[2][i]:
				if board[0][i] == 'O':
					bingo_o += 1
				if board[0][i] == 'X':
					bingo_x += 1
			for j in range(3):
				if board[i][j] == 'O':
					o_cnt += 1
				elif board[i][j] == 'X':
					x_cnt += 1
		if x_cnt < o_cnt:
			return False
		elif x_cnt - o_cnt > 1:
			return False
		if board[1][1] == board[0][2] == board[2][0]:
			if board[1][1] == 'O':
				bingo_o += 1
			elif board[1][1] == 'X':
				bingo_x += 1
		if board[0][0] == board[1][1] == board[2][2]:
			if board[0][0] == 'O':
				bingo_o += 1
			elif board[0][0] == 'X':
				bingo_x += 1
		if bingo_x >= 1 and bingo_o >= 1:
			return False
		if bingo_x >= 1:
			return x_cnt == o_cnt + 1
		elif bingo_o >= 1:
			return x_cnt == o_cnt
		return True