
from timeit import timeit

_A     =  {
    "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      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			0
			lowerCAmelCase_      			=			len(__lowerCAmelCase       ) - 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      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			len(__lowerCAmelCase       ) // 2
			lowerCAmelCase_      			=			len(__lowerCAmelCase       )

			# 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(__lowerCAmelCase       )       )






def      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


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






def      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


			return s == s[::-1]






def      lowerCamelCase__       (       __lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			F"""all({name}(key) is value for key, value in test_data.items())"""
			lowerCAmelCase_      			=			F"""from __main__ import test_data, {name}"""
			lowerCAmelCase_      			=			500000
			lowerCAmelCase_      			=			timeit(stmt=__lowerCAmelCase					,							setup=__lowerCAmelCase					,							number=__lowerCAmelCase       )
			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")





import math





class 			_lowerCAmelCase      :




				def __init__(      self       ,       _UpperCamelCase=0  )       ->   Tuple:  # a graph with Node 0,1,...,N-1
							lowerCAmelCase_      			=			n
							lowerCAmelCase_      			=			[
							    [math.inf for j in range(0       ,       _UpperCamelCase  )] for i in range(0       ,       _UpperCamelCase  )
							]  # adjacency matrix for weight
							lowerCAmelCase_      			=			[
							    [math.inf for j in range(0       ,       _UpperCamelCase  )] for i in range(0       ,       _UpperCamelCase  )
							]  # dp[i][j] stores minimum distance from i to j




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   List[Any]:
							lowerCAmelCase_      			=			w




				def   __a		(      self  )       ->   List[str]:
							for k in range(0       ,       self.n  ):
										for i in range(0       ,       self.n  ):
													for j in range(0       ,       self.n  ):
																lowerCAmelCase_      			=			min(self.dp[i][j]       ,       self.dp[i][k] + self.dp[k][j]  )




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   Dict:
							return self.dp[u][v]


if __name__ == "__main__":
			_A     =  Graph(5)
			graph.add_edge(0, 2, 9)
			graph.add_edge(0, 4, 10)
			graph.add_edge(1, 3, 5)
			graph.add_edge(2, 3, 7)
			graph.add_edge(3, 0, 10)
			graph.add_edge(3, 1, 2)
			graph.add_edge(3, 2, 1)
			graph.add_edge(3, 4, 6)
			graph.add_edge(4, 1, 3)
			graph.add_edge(4, 2, 4)
			graph.add_edge(4, 3, 9)
			graph.floyd_warshall()
			graph.show_min(1, 4)
			graph.show_min(0, 3)



