



'''simple docstring'''

from timeit import timeit

snake_case_			=     {
    """MALAYALAM""": True,
    """String""": False,
    """rotor""": True,
    """level""": True,
    """A""": True,
    """BB""": True,
    """ABC""": False,
    """amanaplanacanalpanama""": True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):
				SCREAMING_SNAKE_CASE  :						int      					= 0
				SCREAMING_SNAKE_CASE  :						Dict      					= len(_SCREAMING_SNAKE_CASE       ) - 1
				while start_i < end_i:
								if s[start_i] == s[end_i]:
												start_i += 1
												end_i -= 1
								else:
												return False
				return True






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= len(_SCREAMING_SNAKE_CASE       ) // 2
				SCREAMING_SNAKE_CASE  :						List[str]      					= len(_SCREAMING_SNAKE_CASE       )

				# We need to traverse till half of the length of string
				# as we can get access of the i'th last element from
				# i'th index.
				# eg: [0,1,2,3,4,5] => 4th index can be accessed
				# with the help of 1st index (i==n-i-1)
				# where n is length of string
				return all(s[i] == s[n - i - 1] for i in range(_SCREAMING_SNAKE_CASE       )       )






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):







				if len(_SCREAMING_SNAKE_CASE       ) <= 2:
								return True
				if s[0] == s[len(_SCREAMING_SNAKE_CASE       ) - 1]:
								return is_palindrome_recursive(s[1:-1]       )
				else:
								return False






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):
				return s == s[::-1]






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= F'''all({name}(key) is value for key, value in test_data.items())'''
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= F'''from __main__ import test_data, {name}'''
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= 50_00_00
				SCREAMING_SNAKE_CASE  :						Tuple      					= timeit(stmt=_SCREAMING_SNAKE_CASE    ,	setup=_SCREAMING_SNAKE_CASE    ,	number=_SCREAMING_SNAKE_CASE       )
				print(F'''{name:<35} finished {number:,} runs in {result:.5f} seconds'''       )


if __name__ == "__main__":
	for key, value in test_data.items():
		assert is_palindrome(key) is is_palindrome_recursive(key)
		assert is_palindrome(key) is is_palindrome_slice(key)
		print(f'''{key:21} {value}''')
	print("""a man a plan a canal panama""")

	# finished 500,000 runs in 0.46793 seconds
	benchmark_function("""is_palindrome_slice""")
	# finished 500,000 runs in 0.85234 seconds
	benchmark_function("""is_palindrome""")
	# finished 500,000 runs in 1.32028 seconds
	benchmark_function("""is_palindrome_recursive""")
	# finished 500,000 runs in 2.08679 seconds
	benchmark_function("""is_palindrome_traversal""")









'''simple docstring'''

from __future__ import annotations

snake_case_			=     [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]






def       __lowercase  (_SCREAMING_SNAKE_CASE      :list[list[int]]    ,	_SCREAMING_SNAKE_CASE      :list[int]    ,	_SCREAMING_SNAKE_CASE      :list[int]    ,	_SCREAMING_SNAKE_CASE      :int    ,	_SCREAMING_SNAKE_CASE      :list[list[int]]    ,	):
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [
				    [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
				]  # the reference grid
				SCREAMING_SNAKE_CASE  :						Dict      					= 1
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [
				    [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
				]  # the action grid

				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= init[0]
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= init[1]
				SCREAMING_SNAKE_CASE  :						Any      					= 0
				SCREAMING_SNAKE_CASE  :						List[Any]      					= g + heuristic[x][y]  # cost from starting cell to destination cell
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= [[f, g, x, y]]

				SCREAMING_SNAKE_CASE  :						List[str]      					= False  # flag that is set when search is complete
				SCREAMING_SNAKE_CASE  :						Any      					= False  # flag set if we can't find expand

				while not found and not resign:
								if len(_SCREAMING_SNAKE_CASE       ) == 0:
												raise ValueError('''Algorithm is unable to find solution'''       )
								else:  # to choose the least costliest action so as to move closer to the goal
												cell.sort()
												cell.reverse()
												SCREAMING_SNAKE_CASE  :						List[str]      					= cell.pop()
												SCREAMING_SNAKE_CASE  :						List[str]      					= next_cell[2]
												SCREAMING_SNAKE_CASE  :						Dict      					= next_cell[3]
												SCREAMING_SNAKE_CASE  :						str      					= next_cell[1]

												if x == goal[0] and y == goal[1]:
																SCREAMING_SNAKE_CASE  :						Dict      					= True
												else:
																for i in range(len(_SCREAMING_SNAKE_CASE       )       ):  # to try out different valid actions
																				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= x + DIRECTIONS[i][0]
																				SCREAMING_SNAKE_CASE  :						Tuple      					= y + DIRECTIONS[i][1]
																				if xa >= 0 and xa < len(_SCREAMING_SNAKE_CASE       ) and ya >= 0 and ya < len(grid[0]       ):
																								if closed[xa][ya] == 0 and grid[xa][ya] == 0:
																												SCREAMING_SNAKE_CASE  :						Optional[Any]      					= g + cost
																												SCREAMING_SNAKE_CASE  :						Any      					= ga + heuristic[xa][ya]
																												cell.append([fa, ga, xa, ya]       )
																												SCREAMING_SNAKE_CASE  :						List[Any]      					= 1
																												SCREAMING_SNAKE_CASE  :						Optional[int]      					= i
				SCREAMING_SNAKE_CASE  :						Dict      					= []
				SCREAMING_SNAKE_CASE  :						List[Any]      					= goal[0]
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= goal[1]
				invpath.append([x, y]       )  # we get the reverse path from here
				while x != init[0] or y != init[1]:
								SCREAMING_SNAKE_CASE  :						str      					= x - DIRECTIONS[action[x][y]][0]
								SCREAMING_SNAKE_CASE  :						str      					= y - DIRECTIONS[action[x][y]][1]
								SCREAMING_SNAKE_CASE  :						Tuple      					= xa
								SCREAMING_SNAKE_CASE  :						Dict      					= ya
								invpath.append([x, y]       )

				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= []
				for i in range(len(_SCREAMING_SNAKE_CASE       )       ):
								path.append(invpath[len(_SCREAMING_SNAKE_CASE       ) - 1 - i]       )
				return path, action


if __name__ == "__main__":
	snake_case_			=     [
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 1, 0],
	    [0, 0, 0, 0, 1, 0],
	]

	snake_case_			=     [0, 0]
	# all coordinates are given in format [y,x]
	snake_case_			=     [len(grid) - 1, len(grid[0]) - 1]
	snake_case_			=     1

	# the cost map which pushes the path closer to the goal
	snake_case_			=     [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			snake_case_			=     abs(i - goal[0]) + abs(j - goal[1])
			if grid[i][j] == 1:
				# added extra penalty in the heuristic map
				snake_case_			=     99

	snake_case_			,				snake_case_			=     search(grid, init, goal, cost, heuristic)

	print("""ACTION MAP""")
	for i in range(len(action)):
		print(action[i])

	for i in range(len(path)):
		print(path[i])




