
def      lowerCamelCase__       (       __lowerCAmelCase						:						int       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			generate_pascal_triangle(__lowerCAmelCase       )
			for row_idx in range(__lowerCAmelCase       ):
						# Print left spaces
						for _ in range(num_rows - row_idx - 1       ):
									print(end=" "       )
						# Print row values
						for col_idx in range(row_idx + 1       ):
									if col_idx != row_idx:
												print(triangle[row_idx][col_idx]					,							end=" "       )
									else:
												print(triangle[row_idx][col_idx]					,							end=""       )
						print()






def      lowerCamelCase__       (       __lowerCAmelCase						:						int       ):




			"""simple docstring"""


			if not isinstance(__lowerCAmelCase					,							__lowerCAmelCase       ):
						raise TypeError("The input value of 'num_rows' should be 'int'"       )

			if num_rows == 0:
						return []
			elif num_rows < 0:
						raise ValueError(
						    "The input value of 'num_rows' should be greater than or equal to 0"       )

			lowerCAmelCase_      			=			[]
			for current_row_idx in range(__lowerCAmelCase       ):
						lowerCAmelCase_      			=			populate_current_row(__lowerCAmelCase					,							__lowerCAmelCase       )
						triangle.append(__lowerCAmelCase       )
			return triangle






def      lowerCamelCase__       (       __lowerCAmelCase						:						list[list[int]]					,							__lowerCAmelCase						:						int       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			[-1] * (current_row_idx + 1)
			# first and last elements of current row are equal to 1
			lowerCAmelCase_			,						lowerCAmelCase_      			=			1, 1
			for current_col_idx in range(1					,							__lowerCAmelCase       ):
						calculate_current_element(
						    __lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase       )
			return current_row






def      lowerCamelCase__       (       __lowerCAmelCase						:						list[list[int]]					,							__lowerCAmelCase						:						list[int]					,							__lowerCAmelCase						:						int					,							__lowerCAmelCase						:						int					,							):




			"""simple docstring"""


			lowerCAmelCase_      			=			triangle[current_row_idx - 1][current_col_idx - 1]
			lowerCAmelCase_      			=			triangle[current_row_idx - 1][current_col_idx]
			lowerCAmelCase_      			=			above_to_left_elt + above_to_right_elt






def      lowerCamelCase__       (       __lowerCAmelCase						:						int       ):




			"""simple docstring"""


			if not isinstance(__lowerCAmelCase					,							__lowerCAmelCase       ):
						raise TypeError("The input value of 'num_rows' should be 'int'"       )

			if num_rows == 0:
						return []
			elif num_rows < 0:
						raise ValueError(
						    "The input value of 'num_rows' should be greater than or equal to 0"       )

			lowerCAmelCase_      			=			[[1]]

			for row_index in range(1					,							__lowerCAmelCase       ):
						lowerCAmelCase_      			=			[0] + result[-1] + [0]
						lowerCAmelCase_      			=			row_index + 1
						# Calculate the number of distinct elements in a row
						lowerCAmelCase_      			=			sum(divmod(__lowerCAmelCase					,							2       )       )
						lowerCAmelCase_      			=			[
						    temp_row[i - 1] + temp_row[i] for i in range(1					,							distinct_elements + 1       )
						]
						lowerCAmelCase_      			=			row_first_half[: (row_index + 1) // 2]
						row_second_half.reverse()
						lowerCAmelCase_      			=			row_first_half + row_second_half
						result.append(__lowerCAmelCase       )

			return result






def      lowerCamelCase__       (       ):




			"""simple docstring"""


			from collections.abc import Callable
			from timeit import timeit

			def benchmark_a_function(__lowerCAmelCase						:						Callable					,							__lowerCAmelCase						:						int       ) -> None:
						lowerCAmelCase_      			=			F"""{func.__name__}({value})"""
						lowerCAmelCase_      			=			timeit(F"""__main__.{call}"""					,							setup="import __main__"       )
						# print(f"{call:38} = {func(value)} -- {timing:.4f} seconds")
						print(F"""{call:38} -- {timing:.4f} seconds"""       )

			for value in range(15       ):  # (1, 7, 14):
						for func in (generate_pascal_triangle, generate_pascal_triangle_optimized):
									benchmark_a_function(__lowerCAmelCase					,							__lowerCAmelCase       )
						print()


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			benchmark()





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



