



from __future__ import annotations

import collections
import pprint
from pathlib import Path





def 							A     (					_UpperCAmelCase    :       str   )    ->			str:







			'''simple docstring'''
			return "".join(sorted(__snake_case   )   )





def 							A     (					_UpperCAmelCase    :       str   )    ->			list[str]:







			'''simple docstring'''
			return word_by_signature[signature(__snake_case   )]


UpperCAmelCase__       =	Path(__file__).parent.joinpath("words.txt").read_text(encoding="utf-8")
UpperCAmelCase__       =	sorted({word.strip().lower() for word in data.splitlines()})

UpperCAmelCase__       =	collections.defaultdict(list)
for word in word_list:
							word_by_signature[signature(word)].append(word)

if __name__ == "__main__":
							UpperCAmelCase__       =	{word: anagram(word) for word in word_list if len(anagram(word)) > 1}

							with open("anagrams.txt", "w") as file:
														file.write("all_anagrams = \n ")
														file.write(pprint.pformat(all_anagrams))





def 							A     (					_UpperCAmelCase    :       int   )    ->			"list[int]":







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

			_UpperCAmelCase			=       [0] * (upper_limit + 1)

			# Base case: C(0) = C(1) = 1
			_UpperCAmelCase			=       1
			if upper_limit > 0:
						_UpperCAmelCase			=       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(_UpperCAmelCase   ):
									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:
																					UpperCAmelCase__       =	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()
