import itertools
def pornstar(heuristic,cost,around):
	_POS = 0
	_G = 1
	_F = 2
	_PARENT = 3
	_OPEN = 4

	def build(node):
		current = node
		while current:
			yield current[_POS]
			current = current[_PARENT]

	def makeNode(pos,goal,parent=None):
		g = parent[_G]+cost(parent[_POS],pos) if parent else 0
		f = g + heuristic(pos,goal)
		return (pos,g,f,parent)

	def algo(start,goal):
		'''
		current is start
		while current not goal
			add all neighbor to open
			current is smallest F score POP
		return current
		'''
		current = makeNode(start,goal)
		openLst = []
		while current[_POS] != goal:
			#add all neighbor to openlist
			openLst += [	makeNode(neiPos, goal, current)
					for neiPos in around(current[_POS])	]
			#remove duplicate optional, keep best G score only
			openLst = [	min(nodeLst,key=lambda node:node[_G]) 
					for pos,nodeLst in itertools.groupby(openLst,key=lambda node : node[_POS])	]
			#next current will be best F score and will be removed from openlst
			current = min(openLst,key=lambda node : node[_F])
			openLst.remove(current)
		return current

	def find(goal,start):
		tmp = algo(start,goal)
		tmp = build(tmp)
		return tmp

	return find

if __name__ == '__main__':
	maze = [
		'##########',
		'#s  #    #',
		'#  ## #  #',
		'#     # g#',
		'##########'
	]

	def heuristic((x,y),(gx,gy)):
		#print('heuristic((%s,%s)(%s,%s))' % (x,y,gx,gy))

		return abs(gx-x) + abs(gy-y)

	def cost(start,to):
		#print('cost(%s,%s)' % (start, to))
		return 1 if start != to else 0

	def around((x,y)):
		#print ('arround(%x,%x)' %(x,y))
		return (
			(nx,ny)
			for ny in range(y-1,y+2)
			for nx in range(x-1,x+2)
			if (nx != x or ny != y)
			and nx > -1
			and ny > -1
			and ny < len(maze)
			and nx < len(maze[ny])
			and maze[ny][nx] != '#'
		)
	newMaze = maze
	algo = pornstar(heuristic,cost,around)

	#print(list(around((1,1))))
	#print(list(around((0,0))))
	#print(list(around((4,8))))

	path = algo((1,1),(7,3))
	
	print(path)
	i = 1
	for (x,y) in path:
		tmp = list(maze[y])
		tmp[x] = str(i)
		i += 1
		maze[y] = ''.join(tmp)
	for line in maze:
		print(line)