# Connect Four

Take a look at wiki description of Connect Four game:

[Wiki Connect Four](https://en.wikipedia.org/wiki/Connect_Four)

The grid is 6 row by 7 columns, those being named from A to G.

You will receive a list of strings showing the order of the pieces which dropped in columns:

```python
  pieces_position_list = ["A_Red",
                          "B_Yellow",
                          "A_Red",
                          "B_Yellow",
                          "A_Red",
                          "B_Yellow",
                          "G_Red",
                          "B_Yellow"]
```

The list may contain up to 42 moves and shows the order the players are playing.

The first player who connects four items of the same color is the winner.

You should return "Yellow", "Red" or "Draw" accordingly.

Difficulty: MEDIUM
Tags: Fundamentals

Starter code:
def who_is_winner(pieces_position_list):
	

Solutions:
(COLUMNS, ROWS) = ('ABCDEFG', range(6))
LINES = [{(COLUMNS[i + k], ROWS[j]) for k in range(4)} for i in range(len(COLUMNS) - 3) for j in range(len(ROWS))] + [{(COLUMNS[i], ROWS[j + k]) for k in range(4)} for i in range(len(COLUMNS)) for j in range(len(ROWS) - 3)] + [{(COLUMNS[i + k], ROWS[j + k]) for k in range(4)} for i in range(len(COLUMNS) - 3) for j in range(len(ROWS) - 3)] + [{(COLUMNS[i + k], ROWS[j - k]) for k in range(4)} for i in range(len(COLUMNS) - 3) for j in range(3, len(ROWS))]

def who_is_winner(pieces_positions):
	players = {}
	board = dict.fromkeys(COLUMNS, 0)
	for position in pieces_positions:
		(column, player) = position.split('_')
		pos = (column, board[column])
		board[column] += 1
		players.setdefault(player, set()).add(pos)
		if any((line <= players[player] for line in LINES)):
			return player
	return 'Draw'


from itertools import count, takewhile
(X, Y, HALF_DIRS) = (6, 7, ((0, 1), (1, 0), (1, 1), (1, -1)))

def who_is_winner(lstMoves):

	def isWinner():
		return any((countAligned(*dirs) >= 4 for dirs in HALF_DIRS))

	def isInsideAndSameGuy(a, b):
		return 0 <= a < X and 0 <= b < Y and (board[a][b] == who)

	def countAligned(dx, dy):
		return 1 + sum((sum(takewhile(bool, (isInsideAndSameGuy(x + dx * swap * n, y + dy * swap * n) for n in count(1)))) for swap in (1, -1)))
	board = [[' '] * Y for _ in range(X)]
	xIdx = [0] * Y
	for move in lstMoves:
		(y, who) = (ord(move[0]) - 65, move[2])
		x = xIdx[y]
		board[x][y] = who
		xIdx[y] += 1
		if isWinner():
			return move[2:]
	else:
		return 'Draw'


def who_is_winner(pieces_position_list):
	grid = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
	columns = 7
	rows = 6
	rowPosition = 0
	winner = None
	drawCount = 0
	for piece in pieces_position_list:
		if piece[2] == 'Y':
			code = 2
		else:
			code = 1
		if piece[0] == 'A':
			columnPosition = 0
		elif piece[0] == 'B':
			columnPosition = 1
		elif piece[0] == 'C':
			columnPosition = 2
		elif piece[0] == 'D':
			columnPosition = 3
		elif piece[0] == 'E':
			columnPosition = 4
		elif piece[0] == 'F':
			columnPosition = 5
		elif piece[0] == 'G':
			columnPosition = 6
		while grid[rowPosition][columnPosition] != 0:
			if grid[5][columnPosition] == 1 or grid[5][columnPosition] == 2:
				break
			rowPosition += 1
		grid[rowPosition][columnPosition] = code
		rowPosition = 0
		for row in range(rows):
			for column in range(columns - 3):
				if grid[row][column] == 1 and grid[row][column + 1] == 1 and (grid[row][column + 2] == 1) and (grid[row][column + 3] == 1):
					winner = 'Red'
				elif grid[row][column] == 2 and grid[row][column + 1] == 2 and (grid[row][column + 2] == 2) and (grid[row][column + 3] == 2):
					winner = 'Yellow'
		for row in range(rows - 3):
			for column in range(columns):
				if grid[row][column] == 1 and grid[row + 1][column] == 1 and (grid[row + 2][column] == 1) and (grid[row + 3][column] == 1):
					winner = 'Red'
				elif grid[row][column] == 2 and grid[row + 1][column] == 2 and (grid[row + 2][column] == 2) and (grid[row + 3][column] == 2):
					winner = 'Yellow'
		for row in range(3, rows):
			for column in range(columns - 3):
				if grid[row][column] == 1 and grid[row - 1][column + 1] == 1 and (grid[row - 2][column + 2] == 1) and (grid[row - 3][column + 3] == 1):
					winner = 'Red'
				elif grid[row][column] == 2 and grid[row - 1][column + 1] == 2 and (grid[row - 2][column + 2] == 2) and (grid[row - 3][column + 3] == 2):
					winner = 'Yellow'
		for row in range(rows - 3):
			for column in range(columns - 3):
				if grid[row][column] == 1 and grid[row + 1][column + 1] == 1 and (grid[row + 2][column + 2] == 1) and (grid[row + 3][column + 3] == 1):
					winner = 'Red'
				elif grid[row][column] == 2 and grid[row + 1][column + 1] == 2 and (grid[row + 2][column + 2] == 2) and (grid[row + 3][column + 3] == 2):
					winner = 'Yellow'
		if winner == 'Red':
			return 'Red'
			break
		elif winner == 'Yellow':
			return 'Yellow'
			break
	if winner == None:
		return 'Draw'


import numpy as np
from scipy.signal import convolve2d

def who_is_winner(pieces_position_list):
	arr = np.zeros((7, 6), int)
	for a in pieces_position_list:
		(pos, color) = a.split('_')
		pos = ord(pos) - ord('A')
		val = (-1, 1)[color == 'Red']
		arr[pos, np.argmin(arr[pos] != 0)] = val
		t_arr = val * arr
		if any((np.max(cv) == 4 for cv in (convolve2d(t_arr, [[1, 1, 1, 1]], 'same'), convolve2d(t_arr, [[1], [1], [1], [1]], 'same'), convolve2d(t_arr, [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], 'same'), convolve2d(t_arr, [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]], 'same')))):
			return color
	return 'Draw'


from numpy import diagonal, rot90

def who_is_winner(pieces_position_list):
	board = [[' '] * 6 for _ in range(7)]

	def check(i, j, p):
		if p in ''.join(board[i]):
			return True
		if p in ''.join(list(zip(*board))[j]):
			return True
		if p in ''.join(diagonal(board, j - i)):
			return True
		if p in ''.join(diagonal(rot90(board), +i + j - 5)):
			return True
		return False
	id = [0] * 7
	for move in pieces_position_list:
		(i, p) = (ord(move[0]) - 65, move[2])
		j = id[i]
		(board[i][j], id[i]) = (p, j + 1)
		if check(i, j, p * 4):
			return 'Yellow' if p == 'Y' else 'Red'
	return 'Draw'


import re

def who_is_winner(pieces_position_list):
	tempList = [''.join(['*' for j in range(7)]) + '\t' for i in range(6)]
	for i in pieces_position_list:
		temp = i.split('_')
		columns = ord(temp[0]) - ord('A')
		sign = '1' if temp[1] == 'Red' else '2'
		for j in range(len(tempList)):
			if tempList[j][columns] == '*':
				tempList[j] = tempList[j][:columns] + sign + tempList[j][columns + 1:]
				break
		else:
			return 'Draw'
		win = GetWin(''.join(tempList))
		if win != 'Draw':
			print(win)
			return win
	else:
		return 'Draw'
	pass

def GetWin(string):
	if re.search('1{4,}|1(?:.{7}1){3,}|1(?:.{8}1){3,}|1(?:.{6}1){3,}', string):
		return 'Red'
	if re.search('2{4,}|2(?:.{7}2){3,}|2(?:.{8}2){3,}|2(?:.{6}2){3,}', string):
		return 'Yellow'
	return 'Draw'


def who_is_winner(moves):
	G = {(c, r): ' ' for r in range(6) for c in range(7)}
	for (col, colour) in [(ord(m[0]) - ord('A'), m[2]) for m in moves]:
		for row in range(6):
			if G[col, row] == ' ':
				G[col, row] = colour
				break
		if colour * 4 in ' '.join([''.join((G[col, k] for k in range(6))), ''.join((G[k, row] for k in range(7))), ''.join((G.get((k, row - col + k), ' ') for k in range(7))), ''.join((G.get((k, row + col - k), ' ') for k in range(7)))]):
			return {'Y': 'Yellow', 'R': 'Red'}[colour]
	return 'Draw'


import string

def vertical_win(game_board_matrix):
	win = 0
	for x_value in range(0, 7):
		coloumn = [game_board_matrix[i][x_value] for i in range(0, 6)]
		i = 0
		while i < 3:
			row4 = coloumn[i:i + 4]
			i += 1
			if row4.count('R') == 4:
				win = 1
			if row4.count('Y') == 4:
				win = 1
	if win == 1:
		return True
	elif win == 0:
		return False

def diagonal_left_win(matrix):
	win = 0
	for height_level in range(2, -1, -1):
		for x in range(6, 2, -1):
			diagonal = [matrix[height_level + offset][x - offset] for offset in range(0, 4)]
			if diagonal.count('R') == 4:
				win = 1
			if diagonal.count('Y') == 4:
				win = 1
	return win

def diagonal_right_win(matrix):
	win = 0
	for height_level in range(2, -1, -1):
		for x in range(0, 4, 1):
			diagonal = [matrix[height_level + offset][x + offset] for offset in range(0, 4)]
			if diagonal.count('R') == 4:
				win = 1
			if diagonal.count('Y') == 4:
				win = 1
	return win

def horizontal_win(matrix):
	win = 0
	for row in matrix:
		i = 0
		while i < 4:
			row4 = row[i:i + 4]
			i += 1
			if row4.count('R') == 4:
				win = 1
			if row4.count('Y') == 4:
				win = 1
	if win == 1:
		return True
	elif win == 0:
		return False

def who_is_winner(pieces_position_list):
	heigth_list = [5, 5, 5, 5, 5, 5, 5]
	(w, h) = (7, 6)
	game_board = [[0 for x in range(w)] for y in range(h)]
	move_dict = {}
	letters = list(string.ascii_uppercase)[0:7]
	for (letter, i) in enumerate(letters):
		move_dict[i] = letter
	parsed_moves = [parsed_move.split('_') for parsed_move in pieces_position_list]
	converted_moves = [[move_dict[move[0]], move[1]] for move in parsed_moves]
	for move in converted_moves:
		(x_coordinate, colour) = move
		game_board[heigth_list[x_coordinate]][x_coordinate] = colour[0]
		if heigth_list[x_coordinate] > 0:
			heigth_list[x_coordinate] = heigth_list[x_coordinate] - 1
		if horizontal_win(game_board) or vertical_win(game_board) or diagonal_left_win(game_board) or diagonal_right_win(game_board):
			return colour
	diagonal_left_win(game_board)
	return 'Draw'


def who_is_winner(pieces_position_list):
	(C, counts, rows) = ({'R': 'Red', 'Y': 'Yellow'}, [0, 0, 0, 0, 0, 0, 0], 6)
	(grid, slots, I) = (list(), 7, {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5, 'G': 6})
	for i in range(7):
		grid.append([0, 0, 0, 0, 0, 0])
	for piece in pieces_position_list:
		(slot, color) = (I[piece[0]], C[piece[2]])
		grid[slot][counts[slot]] = color
		n = 0
		for y in range(counts[slot], rows):
			if grid[slot][y] == color:
				n += 1
			else:
				break
		for y in range(counts[slot] - 1, -1, -1):
			if grid[slot][y] == color:
				n += 1
			else:
				break
		if n >= 4:
			return color
		n = 0
		for x in range(slot, slots):
			if grid[x][counts[slot]] == color:
				n += 1
			else:
				break
		for x in range(slot - 1, -1, -1):
			if grid[x][counts[slot]] == color:
				n += 1
			else:
				break
		if n >= 4:
			return color
		(x, y, n) = (slot, counts[slot], 0)
		while x < slots and y < rows:
			if grid[x][y] == color:
				(x, y, n) = (x + 1, y + 1, n + 1)
			else:
				break
		(x, y) = (slot - 1, counts[slot] - 1)
		while x >= 0 and y >= 0:
			if grid[x][y] == color:
				(x, y, n) = (x - 1, y - 1, n + 1)
			else:
				break
		if n >= 4:
			return color
		(x, y, n) = (slot, counts[slot], 0)
		while x >= 0 and y < rows:
			if grid[x][y] == color:
				(x, y, n) = (x - 1, y + 1, n + 1)
			else:
				break
		(x, y) = (slot + 1, counts[slot] - 1)
		while x < slots and y >= 0:
			if grid[x][y] == color:
				(x, y, n) = (x + 1, y - 1, n + 1)
			else:
				break
		if n >= 4:
			return color
		counts[slot] += 1
	return 'Draw'


def who_is_winner(moves):
	field = [[' ' for i in range(7)] for j in range(6)]
	for move in moves:
		(column, color) = move.split('_')
		field = place_color(field, column, color)
		result = check_win(field)
		if result:
			return result
	return 'Draw'

def check_win(field):
	field = list(reversed(field))
	for i in field:
		for j in range(4):
			h = set(i[j:4 + j])
			if h == {'R'}:
				return 'Red'
			elif h == {'Y'}:
				return 'Yellow'
	for i in range(3):
		for j in range(7):
			v = set([field[i + k][j] for k in range(4)])
			if v == {'R'}:
				return 'Red'
			elif v == {'Y'}:
				return 'Yellow'
	for i in range(3):
		for j in range(4):
			r = [field[i][j], field[i + 1][j + 1], field[i + 2][j + 2], field[i + 3][j + 3]]
			l = [field[i][-j - 1], field[i + 1][-j - 2], field[i + 2][-j - 3], field[i + 3][-j - 4]]
			if set(r) == {'R'} or set(l) == {'R'}:
				return 'Red'
			elif set(r) == {'Y'} or set(l) == {'Y'}:
				return 'Yellow'
	return 0

def place_color(field, column, color):
	index = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5, 'G': 6}[column]
	for i in range(1, 7 + 1):
		if field[-i][index] == ' ':
			field[-i][index] = color[0]
			break
	return field