
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")





def      lowerCamelCase__       (       __lowerCAmelCase						:						int       ):




			"""simple docstring"""


			if upper_limit < 0:
						raise ValueError("Limit for the Catalan sequence must be ≥ 0"       )

			lowerCAmelCase_      			=			[0] * (upper_limit + 1)

			# Base case: C(0) = C(1) = 1
			lowerCAmelCase_      			=			1
			if upper_limit > 0:
						lowerCAmelCase_      			=			1

			# Recurrence relation: C(i) = sum(C(j).C(i-j-1)), from j = 0 to i
			for i in range(2					,							upper_limit + 1       ):
						for j in range(__lowerCAmelCase       ):
									catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

			return catalan_list


if __name__ == "__main__":
			print("\n********* Catalan Numbers Using Dynamic Programming ************\n")
			print("\n*** Enter -1 at any time to quit ***")
			print("\nEnter the upper limit (≥ 0) for the Catalan number sequence: ", end="")
			try:
						while True:
									_A     =  int(input().strip())
									if N < 0:
												print("\n********* Goodbye!! ************")
												break
									else:
												print(f"""The Catalan numbers from 0 through {N} are:""")
												print(catalan_numbers(N))
												print("Try another upper limit for the sequence: ", end="")
			except (NameError, ValueError):
						print("\n********* Invalid input, goodbye! ************\n")

			import doctest

			doctest.testmod()



