import core


def transitionSequence(state1, state2, diff, limit=0):
	return []


class SpecGo(core.Go):
	def __init__(self):
		super().__init__()

	def load(self,state):
		for (r,row) in enumerate(state):
			for (c,x) in enumerate(row):
				self.board[r][c]=x

	def listRelevantMoves(self,diff):
		"""There can be 3 different changes in the diff: additions, deletions and replacements.
		Additions can be taken as relevant right away.
		Deletions and replacements had to be captured, so we add their liberties.
		Also any non-missing stones of partially deleted (or replaced) groups had to be replayed, so add them too.
		Needs to handle: Take n, return 1. Snapback.
		There's no end to what could be theoretically relevant, but such sequences are long and we will pretend they won't happen."""
		res=(set(),set())
		for d in diff:
			(r,c,action,color)=d
			colorKey=(1-color)<<1 # {-1,1}->{1,0}
			if action!="-" and (r,c) not in res[colorKey]:
				res[colorKey].append((r,c))
			# this is rather sloppy but correct. the time will show if it is effective enough
			if action!="+" and (r,c) not in res[colorKey] and (r,c) not in res[1-colorKey]:
				self._helper.clear()
				self._helper.floodFill(color if action=="-" else 1-color, r, c)
				res[colorKey].union(self._helper.getContinuousArea())
				for (ri,ci) in self._helper.getContinuousArea():
					res[colorKey].add((ri,ci))
					res[1-colorKey].add((ri,ci))
					if ri>0:
						res[colorKey].add((ri-1,ci))
						res[1-colorKey].add((ri-1,ci))
					if ri<self.boardSize:
						res[colorKey].add((ri+1,ci))
						res[1-colorKey].add((ri+1,ci))
					if ci>0:
						res[colorKey].add((ri,ci-1))
						res[1-colorKey].add((ri,ci-1))
					if ci<self.boardSize:
						res[colorKey].add((ri,ci+1))
						res[1-colorKey].add((ri,ci+1))
		return res


class Engine:
	def __init__(self):
		self._g=SpecGo()
		self._moveList=(set(),set())

	def load(self,state1,diff):
		self._g.load(state1)
		self._moveList=self._g.listRelevantMoves(diff)

	def iterativelyDeepen(self,state2):
		for i in range(1,10):
			seq=self.dfs(state2,i)
			if seq: return seq

	def dfs(self,state2,limit):
		g=self._g
		for (r,c) in self._moveList[g.toMove]:
			g.doMove(g.toMove,r,c)
			if g.board==state2: return [(r,c)]
			if limit>1:
				seq=self.dfs(state2,limit-1)
				if seq:
					seq.append((r,c))
					return seq
			g.undoMove(m)
		return False

eng=Engine()