class Go:

	## Initializes self.board to a list[r][c]=EMPTY.

	def __init__(self,boardSize=19):

		self.boardSize=boardSize

		self.board=[[EMPTY]*boardSize for x in range(boardSize)]

		self.toMove=BLACK

		self._helper=HelperBoard(self.board)

		self._record=GameRecord()

	def listMoves(self,diff=[]):

		return []

	## Executes a move.

	#

	#  Doesn't check for kos. Suicide not allowed.

	#

	#  @param color BLACK or WHITE

	#  @return True on success, False on failure (illegal move)

	def move(self,color,row,col):

		if color!=self.toMove: log.warning("move by %s out of order",colorNames[color])

		if self.board[row][col]!=EMPTY: return False

		self.board[row][col]=color

		# capture neighbors

		for r,c in ((-1,0),(1,0),(0,-1),(0,1)):

			self._helper.clear()

			if not self._helper.floodFill(-color,row+r,col+c,EMPTY): self._remove()

		# check for suicide

		self._helper.clear()

		if not self._helper.floodFill(color,row,col,EMPTY):

			self.board[row][col]=EMPTY

			return False

		self._record.move(color,row,col)

		self.toMove=-1*color

		return True

	def undoMove(self,color,r,c,captures):

		self.board[r][c]=color

		if len(captures)>0:

			self._helper.clear()

			for (r,c) in captures:

				self._helper.floodFill(EMPTY,r,c)

			self._fill(-color)

	def transitionMove(self,board):

		res=transitionMove(self.board,board)

		if not res: return res

		(r,c,color)=res

		return self.move(color,r,c)

	## Removes stones at coordinates marked with True in self.helper.

	def _remove(self):

		self._fill(EMPTY)

	def _fill(self,filling):

		for (r,c) in self._helper.getContinuousArea():

			self.board[r][c]=filling

def exportBoard(board):

	substitutions={EMPTY:".", BLACK:"X", WHITE:"O"}

	return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board)

def isLegalPosition(board):

	boardSize=len(board)

	temp=[[None]*boardSize for x in range(boardSize)]

	for r in range(boardSize):

		for c in range(boardSize):

			if board[r][c]==EMPTY: continue

			if temp[r][c]: continue

			if not dfs([(r,c)],board,temp): return False

	return True

def transitionMove(state1,state2):

	moves=[]

	for (r,(row1,row2)) in enumerate(zip(state1,state2)):

		for (c,(item1,item2)) in enumerate(zip(row1,row2)):

			if item1==EMPTY and item2!=EMPTY:

				moves.append((r,c,item2))

	if len(moves)==0:

		log.info("no new stone")

		return None

	elif len(moves)==1:

		log.info("new stone: %s",moves[0])

		return moves[0]

	else:

		log.warning("too many new stones: %s",moves)

		return False

def dfs(stack,board,mask):

	boardSize=len(board)

	(r,c)=stack[0]

	color=board[r][c]

	while len(stack)>0:

		(r,c)=stack.pop()

		if board[r][c]==EMPTY: return True

		elif board[r][c]!=color: continue

		elif mask[r][c]: return True

		mask[r][c]=True

		for (x,y) in ((0,-1),(-1,0),(0,1),(1,0)):

			if 0<=r+y<boardSize and 0<=c+x<boardSize:

				stack.append((r+y,c+x))

	return False

from util import EMPTY

## Utility class for finding continuous regions on a Go.board.

class HelperBoard:

	def __init__(self,board):

		self._refBoard=board # Go.board, readonly

		self._boardSize=len(board)

		self._board=[[EMPTY]*self._boardSize for i in range(self._boardSize)]

		self._visited=[0]*(self._boardSize**2)*2

		self._visitedCount=0

		self._libs=[0]*(self._boardSize**2)*2

		self._libCount=0

	def floodFill(self,filling,r,c,needle=None):

		if c<0 or c>=self._boardSize or r<0 or r>=self._boardSize: return False # out of range

		if self._board[r][c]: return False # already visited

		if self._refBoard[r][c]==needle: return True # found something

		if self._refBoard[r][c]!=filling:

			if self._refBoard[r][c]==EMPTY: # remember group liberties

				self._board[r][c]=True

				self._libs[self._libCount*2]=r

				self._libs[self._libCount*2+1]=c

				self._libCount+=1

			return False # out of area boundary

		self._board[r][c]=True # set visited

		self._visited[self._visitedCount*2]=r

		self._visited[self._visitedCount*2+1]=c

		self._visitedCount+=1

		# check neighbors

		return self.floodFill(filling,r,c-1,needle) or \

			self.floodFill(filling,r,c+1,needle) or \

			self.floodFill(filling,r-1,c,needle) or \

			self.floodFill(filling,r+1,c,needle)

	def getContinuousArea(self):

		for i in range(self._visitedCount):

			yield (self._visited[i*2],self._visited[i*2+1])

	def clear(self):

		for i in range(self._visitedCount):

			(r,c)=(self._visited[i*2],self._visited[i*2+1])

			self._board[r][c]=EMPTY

		self._visitedCount=0

		for i in range(self._libCount):

			(r,c)=(self._libs[i*2],self._visited[i*2+1])

			self._board[r][c]=EMPTY

		self._libCount=0

"""Theory:

We have a sequence S of valid board states s_1, ..., s_n.

We search for a picked subsequence S_p of length k and m additional moves M such that:

- S_p augmented by M forms a valid sequence of moves

- k-m is maximal for S_p picked from S

It is relatively cheap to add new items to S.

User can change detector parameters, presumably in case the previous don't fit the (current) situation.

In such a case we assume the new parameters are correct from the current position onwards.

But the change might have been appropriate even earlier (before the user detected and fixed an error).

So we try to find the correct crossover point like this:

- construct a sequence S' = s'_i, ..., s'_n by reanalyzing the positions with a new set of parameters, where s_i is the point of previous user intervention or s_0

- for each s'_j:

	- try to append it to S[:j]

	- try to append it to S'[:j]

	- remember the better variant

- linearize the fork back by discarding s'_j-s preceding the crossover and s_j-s following the crossover

"""

from util import EMPTY

## Crude lower bound on edit distance between states.

def estimateDistance(diff):

	additions=sum(1 for d in diff if d[2]=="+")

	deletions=sum(1 for d in diff if d[2]=="-")

	replacements=len(diff)-additions-deletions

	if additions>0: return additions+replacements

	elif replacements==0 and deletions>0: return 2 # take n, return 1

class BoardState:

	def __init__(self,board):

		self._board=tuple(tuple(x for x in row) for row in board)

		self.prev=None

		self._next=None

		self.moves=[]

		self.weight=0

		self.diff2Prev=None

	def __iter__(self): return iter(self._board)

	def __getitem__(self,key): return self._board[key]

	def __sub__(self,x):

		res=[]

		for (r,(row1,row2)) in enumerate(zip(self._board,x)):

			for (c,(item1,item2)) in enumerate(zip(row1,row2)):

				if item1==item2: continue

				elif item2==EMPTY: res.append((r,c,"+",item1))

				elif item1==EMPTY: res.append((r,c,"-",item2))

		return res

class StateBag:

	def __init__(self):

		self._states=[]

	def pushState(self,board):

		sn=BoardState(board)

		for s in reversed(self._states):

			diff=sn-s

			distEst=estimateDistance(diff)

			if distEst>3: continue # we couldn't find every such move sequence anyway without a clever algorithm

			weightEst=s.weight-distEst

			if weightEst<=sn.weight: continue

			moves=transitionSequence(s,sn,diff)

			weight=s.weight-len(moves)

			if weight<=sn.weight: continue

			sn.prev=s

			sn.diff2Prev=diff

			sn.moves=moves

			sn.weight=weight

		self._states.append(sn)

	def merge(self,branch):

		pass