# This class represents the state of a board at a point in time.
# The class implements functions for basic manipulation of the board
# such as playing moves and doing captures. The board is not aware whose turn it is.
# The Baord class does *not* contain the move history or the prisoner counts,
# by design. These things are contained in a Game object intead, which
# uses the board class as a utility.

class Board(object):

    def __init__(self, width):
        self.grid = list()
        self.width = width
        for i in range(0,self.width):
            self.grid.append(list())
            for j in range(0,self.width):
                self.grid[-1].append(".")

    def to_string(self):
        s = ""
        for i in range(0,self.size):
            for j in range(0,self.size):
                s += self.board.grid[i][j]
            s += "\n"
        return s

    def clear(self):
        for i in range(0,self.width):
            for j in range(0,self.width):
                self.grid[i][j] = '.'


    # Plays a move on the board and returns the intersections that had stones
    # that were captures as a set (possibly empty). Raises an exception in case
    # of an illegal move
    def play_stone(self, row, column, color):
        if self.grid[row][col] != '.':
            raise Exception("Can't play on top of another stone")

        captured = self.get_captured_stones(row,col,color)

        # Try to place the stone
        self.grid[row][col] = color

        if len(self.get_liberties(row,col)) == 0:
            if len(captured) == 0:
                self.grid[row][col] = '.' # undo
                raise Exception("Suicide is not allowed")

        # Move is legal. Remove captured stones from the board
        for pos in captured:
            self.grid[pos[0]][pos[1]] = '.'

        return captured

    # Returns the list of coordinates of the intersections that are adjacent
    # to the given position
    def get_neighbors(self,row,col):
        neighbors = set()
        if row > 0: neighbors.add((row-1,col))
        if row < self.width-1: neighbors.add((row+1,col))
        if col > 0: neighbors.add((row,col-1))
        if col < self.width-1: neighbors.add((row,col+1))
        return neighbors

    # Returns the set of positions of stones which are captured by
    # placing a stone to (row,col) of the given color
    # Assumes the intersection at (row,col) is empty
    def get_captured_stones(self,row,col,color):
        assert(self.grid[row][col] == '.')
        captured = set()
        enemy = ('W' if color == 'B' else 'B')
        for neighbor in self.get_neighbors(row,col):
            r,c = neighbor[0], neighbor[1]
            if self.grid[r][c] == enemy:
                liberties = self.get_liberties(r,c)
                if len(liberties) == 1: # Was in atari?
                    captured = captured.union(self.get_group(r,c))
        return captured

    # Returns the set of coordinates which correspond to the liberties of the group that
    # contains the the position (row,col).
    # If there is no stone at (row,col), returns an empty set
    def get_liberties(self,row,col):
        group = self.get_group(row,col)
        liberties = set()
        for pos in group:
            for neighbor in self.get_neighbors(pos[0],pos[1]):
                if self.grid[neighbor[0]][neighbor[1]] == '.':
                    liberties.add(neighbor)
        return liberties

    # Returns set set of coordinates that correspond to the group that contains the given position
    # If the given position is empty, returns an empty set
    def get_group(self, row, col):

        if self.grid[row][col] == '.': return set()

        color = self.grid[row][col]
        # Run a depth first search from the starting position
        visited = set()
        stack = [(row,col)] # DFS stack
        while len(stack) != 0:
            pos = stack.pop()
            r, c = pos[0], pos[1]

            if pos in visited or self.grid[r][c] != color: continue
            visited.add(pos)

            for neighbor in self.get_neighbors(r,c):
                stack.append(neighbor)

        return visited

    def score_game(self, komi):
        black_score = 0
        white_score = 0
        stack = [] # DFS stack containing triples (row, column, color)
        # In effect we have two DFS searches going on at the same time, one from black stones,
        # one from white stones. I use only one stack to run both at the same time

        # Initialize the stack with the empty neighbors of all points
        for r in range(0,self.size):
            for c in range(0,self.size):
                if self.grid[r][c] == 'B': black_score += 1
                if self.grid[r][c] == 'W': white_score += 1
                for neighbor in self.get_neighbors(r,c):
                    if self.grid[neighbor[0]][neighbor[1]] == 'B':
                        stack.append((r,c,'B'))
                    if self.grid[neighbor[0]][neighbor[1]] == 'W':
                        stack.append((r,c,'W'))

        point_owners = list() # 2d array of dicts {'W': True/False, 'B': True/False}
        for i in range(0,self.size):
            point_owners.append(list())
            for j in range(0,self.size):
                point_owners[-1].append({'W': False, 'B': False})

        # Run a depth first search
        visited = set() # Triples (row, column, color)

        while len(stack) != 0:
            r,c,color = stack.pop()

            if self.grid[r][c] != '.' or (r,c,color) in visited: continue

            visited.add((r,c,color))
            point_owners[r][c][color] = True

            for neighbor in self.get_neighbors(r,c):
                stack.append((neighbor[0], neighbor[1], color))

        for r in range(0,self.size):
            for c in range(0,self.size):
                if point_owners[r][c]['W'] == True and point_owners[r][c]['B'] == True:
                    continue # Dame
                if point_owners[r][c]['B'] == True: black_score += 1
                if point_owners[r][c]['W'] == True: white_score += 1

return black_score, white_score + komi, point_owners