Based on [this kata, Connect Four.](https://www.codewars.com/kata/connect-four-1)

In this kata we play a modified game of connect four. It's connect X, and there can be multiple players.

Write the function ```whoIsWinner(moves,connect,size)```.

```2 <= connect <= 10```

```2 <= size <= 52```

Each column is identified by a character, A-Z a-z:  
``` ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz ```


Moves come in the form:

```
['C_R','p_Y','s_S','I_R','Z_Y','d_S']
```
* Player R puts on C
* Player Y puts on p
* Player S puts on s
* Player R puts on I
* ...

The moves are in the order that they are played. 

The first player who connect ``` connect ``` items in same color is the winner. 

Note that a player can win before all moves are done. You should return the first winner.

If no winner is found, return "Draw".

A board with size 7, where yellow has connected 4:

All inputs are valid, no illegal moves are made.

![alt text](https://i.imgur.com/xnJEsIx.png)

Source: codewars | Difficulty: EASY
Tags: Data structures

Game theory

Starter code: def whoIsWinner(moves, con, sz):
	

Solutions:
from itertools import compress
from string import ascii_uppercase, ascii_lowercase
D = {c: i for (i, c) in enumerate(ascii_uppercase + ascii_lowercase)}

def whoIsWinner(moves, con, sz):

	def gen(i, j):
		for x in range(1, con):
			yield ((i, j - x), (i - x, j), (i + x, j), (i - x, j - x), (i + x, j + x), (i + x, j - x), (i - x, j + x))

	def check(i, j, p):
		(memo, count) = ([True] * 7, [0] * 7)
		for L in gen(i, j):
			for (x, (k, l)) in enumerate(L):
				memo[x] = memo[x] and 0 <= k < sz and (0 <= l < sz) and (grid[k][l] == p)
				count[x] += memo[x]
			if not any(memo):
				return max(count[0], count[1] + count[2], count[3] + count[4], count[5] + count[6]) + 1 >= con
		return True
	if sz >= con <= len(moves):
		grid = [[None] * sz for _ in range(sz)]
		for move in moves:
			(i, p) = (D[move[0]], move[-1])
			j = next((j for (j, x) in enumerate(grid[i]) if x is None))
			if check(i, j, p):
				return p
			grid[i][j] = p
	return 'Draw'


from string import ascii_letters as rows
ROWS = {c: n for (n, c) in enumerate(rows[26:] + rows[:26])}
DIRS = [(1, 0), (1, 1), (0, 1), (-1, 1)]

def whoIsWinner(moves, connect, size):

	def check_line(dx, dy):
		n = 0
		for _ in range(2):
			(dx, dy, x, y) = (-dx, -dy, p, q)
			while 0 <= x < size and 0 <= y < len(grid[x]) and (grid[x][y] == player):
				n += 1
				x += dx
				y += dy
		return n > connect
	grid = [[] for _ in range(size)]
	for move in moves:
		(row, player) = move.split('_')
		p = ROWS[row]
		q = len(grid[p])
		grid[p].append(player)
		if any((check_line(u, v) for (u, v) in DIRS)):
			return player
	return 'Draw'


from itertools import count, takewhile
MOVES = ((0, 1), (1, 1), (1, 0), (-1, 1))

def whoIsWinner(moves, nCon, sz):

	def insideAndSameYet(z):
		(x, y) = z
		return 0 <= x < sz and 0 <= y < sz and (grid[x][y] == who)

	def isWinner(x, y, who):
		for (dx, dy) in MOVES:
			s = 1 + sum((1 for c in (-1, 1) for _ in takewhile(insideAndSameYet, ((x + c * n * dx, y + c * n * dy) for n in count(1)))))
			if s >= nCon:
				return True
		return False
	grid = [[''] * sz for _ in range(sz)]
	xInCols = [0] * sz
	for m in moves:
		who = m[-1]
		y = ord(m[0]) - (65 if m[0].isupper() else 71)
		x = xInCols[y]
		xInCols[y] += 1
		grid[x][y] = who
		if isWinner(x, y, who):
			return who
	else:
		return 'Draw'


import re
from string import Template

def whoIsWinner(moves, con, sz):
	z = (sz + 1) ** 2
	r = ['-'] * z
	d = dict()
	reg = Template('(\\w)(((.{$s1}\\1){$c})|(\\1{$c})|((.{$s2}\\1){$c})|((.{$s3}\\1){$c}))')
	reg = re.compile(reg.substitute(s1=str(sz - 1), c=str(con - 1), s2=str(sz), s3=str(sz + 1)))
	for (i, x) in enumerate(list('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz')[:sz]):
		d[x] = z - (sz + 1) + i
	for s in moves:
		r[d[s[0]]] = s[2]
		d[s[0]] -= sz + 1
		m = reg.findall(''.join(r))
		if m:
			return m[0][0]
	return 'Draw'


whoIsWinner = lambda M, C, Z: (lambda g, X: next((w for (w, y) in map(lambda m: (m[-1], ord(m[0]) - (65 if m[0].isupper() else 71)), M) for x in (X.__getitem__(y),) if X.__setitem__(y, X.__getitem__(y) + 1) or g.__getitem__(x).__setitem__(y, w) or any((C <= 1 + sum((1 for c in (-1, 1) for _ in __import__('itertools').takewhile(lambda z: 0 <= z[0] < Z and 0 <= z[1] < Z and (g[z[0]][z[1]] == w), ((x + c * n * dx, y + c * n * dy) for n in __import__('itertools').count(1))))) for (dx, dy) in ((0, 1), (1, 1), (1, 0), (-1, 1))))), 'Draw'))(*([[''] * Z for _ in range(Z)], [0] * Z))


from itertools import count
MOVES = ((0, 1), (1, 1), (1, 0), (-1, 1))

def whoIsWinner(moves, nCon, sz):

	def isWinner(rX, rY, who):
		for (dx, dy) in MOVES:
			s = 1
			for c in (-1, 1):
				for n in count(1):
					(x, y) = (rX + c * n * dx, rY + c * n * dy)
					if not (0 <= x < sz and 0 <= y < sz and (grid[x][y] == who)):
						break
					s += 1
			if s >= nCon:
				return True
		return False
	grid = [[''] * sz for _ in range(sz)]
	xInCols = [0] * sz
	for m in moves:
		who = m[-1]
		y = ord(m[0]) - (65 if m[0].isupper() else 71)
		x = xInCols[y]
		xInCols[y] += 1
		grid[x][y] = who
		if isWinner(x, y, who):
			return who
	else:
		return 'Draw'


from string import ascii_uppercase, ascii_lowercase
from collections import Counter
import re
A = {x: i for (i, x) in enumerate(ascii_uppercase + ascii_lowercase)}

def f(P, W):
	(row, col) = divmod(P, W)
	r = [[row * W + i for i in range(W)], [W * i + col for i in range(W)]]
	if P >= (W + 1) * row:
		s = P - row * (W + 1)
		r.append([s + (W + 1) * i for i in range(W - s)])
	else:
		s = W * (row - col)
		r.append([s + (W + 1) * i for i in range(W - row + col)])
	if P >= (W - 1) * (row + 1):
		s = W * (W - 2) + col + row + 1
		r.append([s - (W - 1) * i for i in range(W - s % W)])
	else:
		s = W * row + W * col
		r.append([s - (W - 1) * i for i in range(s // W + 1)])
	return r

def whoIsWinner(G, n, w, d='Draw'):
	if n > w:
		return d
	(D, P, C) = (dict(), Counter(), Counter())
	for x in G:
		(p, t) = x.split('_')
		col = A[p]
		rp = col + P[col] * w
		P[col] += 1
		D[rp] = t
		C[t] += 1
		if C[t] < n:
			continue
		if next((1 for x in f(rp, w) if re.search(f'({t})\\1{{{n - 1}}}', ''.join((D.get(y, '.') for y in x)))), None):
			return t
	return d


import re

def check(line, ch, connect):
	return re.search(re.escape(ch) + '{' + re.escape(str(connect)) + '}', ''.join(line))

def decide(matrix, i, j, connect, size):
	ch = matrix[i][j]
	row = matrix[i][max(0, j - connect + 1):j + connect]
	if check(row, ch, connect):
		return True
	column = [k[j] for k in matrix[max(0, i - connect + 1):i + connect]]
	if check(column, ch, connect):
		return True
	for x in [[(-1, -1), (1, 1)], [(-1, 1), (1, -1)]]:
		diagonal = []
		for (ind, (k, l)) in enumerate(x):
			(ni, nj, li) = (i + k, j + l, [])
			while 0 <= ni < size and 0 <= nj < size and (len(li) != connect) and (matrix[ni][nj] != ' '):
				li.append(matrix[ni][nj])
				ni += k
				nj += l
			diagonal.extend(li[::[-1, 1][ind]] + [ch])
		if check(diagonal[:-1], ch, connect):
			return True
	return False

def whoIsWinner(moves, connect, size):
	matrix = [[' ' for _ in range(size)] for _ in range(size)]
	columns = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'[:size]
	AVL = {i: size - 1 for i in columns}
	for move in moves:
		(col, player) = move.split('_')
		(r, c) = (AVL[col], columns.index(col))
		matrix[r][c] = player
		AVL[col] -= 1
		if decide(matrix, r, c, connect, size):
			return player
	return 'Draw'


columns = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'

def parseMove(move):
	(loc, player) = move.split('_')
	return (columns.index(loc), player)

def placeMove(move, board):
	(loc, player) = parseMove(move)
	board[loc].append(player)

def isConnect(loc, dir, connect, board):
	count = 1
	(x, y) = loc
	player = board[x][y]
	s = 1
	isCheckForward = True
	isCheckBack = True
	while count < connect and (isCheckForward or isCheckBack):
		(sx, sy) = tuple((e * s for e in dir))
		if isCheckForward and x + sx < len(board) and (x + sx >= 0) and (y + sy < len(board[x + sx])) and (y + sy >= 0) and (board[x + sx][y + sy] == player):
			count += 1
		else:
			isCheckForward = False
		if isCheckBack and x - sx >= 0 and (x - sx < len(board)) and (y - sy >= 0) and (y - sy < len(board[x - sx])) and (board[x - sx][y - sy] == player):
			count += 1
		else:
			isCheckBack = False
		s += 1
	return count >= connect

def findWinner(move, connect, board):
	(x, player) = parseMove(move)
	y = len(board[x]) - 1
	loc = (x, y)
	for d in [(1, 0), (0, 1), (1, 1), (1, -1)]:
		if isConnect(loc, d, connect, board):
			return player
	return None

def whoIsWinner(moves, connect, size):
	board = [[] for _ in range(size)]
	winner = None
	while not winner and len(moves) > 0:
		move = moves.pop(0)
		placeMove(move, board)
		winner = findWinner(move, connect, board)
	return winner if winner else 'Draw'