# 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: interview

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
        
        #check horizontal positions for winner
        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"
                    
        #check vertical positions
        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"
                    
        #check left vertical positions
        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"
        
        #check right vertical positions
        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"

        #check winning condition
        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):
    # Your code here!
    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(r"1{4,}|1(?:.{7}1){3,}|1(?:.{8}1){3,}|1(?:.{6}1){3,}",string):
        return "Red"
    if re.search(r"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}
  # grid index is 0-6 for A-G. Contains list up to 6 "R"=-1 or "Y"=1 (or None = 0)
  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
    # Test win condition
    # VERTICAL
    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
    # HORIZONTAL
    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
    # NORTHEAST
    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
    # NORTHWEST
    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:  # Horizontal win check
        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):  # Vertical win check
        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):  # Diagonal win check
        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