


"""simple docstring"""







def    UpperCAmelCase__       (lowerCAmelCase_   ):




					'''simple docstring'''


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

					__SCREAMING_SNAKE_CASE						   =				[0] * (upper_limit + 1)

					# Base case: C(0) = C(1) = 1
					__SCREAMING_SNAKE_CASE						   =				1
					if upper_limit > 0:
										__SCREAMING_SNAKE_CASE						   =				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__				:							List[str]						=     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()






import math
import time
from typing import Dict, List, Optional

from torch.utils.data import Dataset

from transformers import SeqaSeqTrainer, is_torch_tpu_available
from transformers.trainer_utils import PredictionOutput, speed_metrics


if is_torch_tpu_available(check_device=False):
					import torch_xla.core.xla_model as xm
					import torch_xla.debug.metrics as met
class 			a__    (					snake_case__      ):






						def __init__(   self		,			*_A		,			_A=None		,			_A=None		,			**_A			):




											"""simple docstring"""



											super().__init__(*_A		,			**_A			)
											__lowerCAmelCase				   =       eval_examples
											__lowerCAmelCase				   =       post_process_function






						def 				__SCREAMING_SNAKE_CASE(   self		,			_A = None		,			_A=None		,			_A = None		,			_A = "eval"		,			**_A		,			):




											"""simple docstring"""



											__lowerCAmelCase				   =       gen_kwargs.copy()
											__lowerCAmelCase				   =       (
											    gen_kwargs["max_length"] if gen_kwargs.get("max_length"			) is not None else self.args.generation_max_length
											)
											__lowerCAmelCase				   =       (
											    gen_kwargs["num_beams"] if gen_kwargs.get("num_beams"			) is not None else self.args.generation_num_beams
											)
											__lowerCAmelCase				   =       gen_kwargs

											__lowerCAmelCase				   =       self.eval_dataset if eval_dataset is None else eval_dataset
											__lowerCAmelCase				   =       self.get_eval_dataloader(_A			)
											__lowerCAmelCase				   =       self.eval_examples if eval_examples is None else eval_examples

											# Temporarily disable metric computation, we will do it in the loop here.
											__lowerCAmelCase				   =       self.compute_metrics
											__lowerCAmelCase				   =       None
											__lowerCAmelCase				   =       time.time()
											__lowerCAmelCase				   =       self.prediction_loop if self.args.use_legacy_prediction_loop else self.evaluation_loop
											try:
																__lowerCAmelCase				   =       eval_loop(
																    _A		,			description="Evaluation"		,			prediction_loss_only=True if compute_metrics is None else None		,			ignore_keys=_A		,			metric_key_prefix=_A		,			)
											finally:
																__lowerCAmelCase				   =       compute_metrics
											__lowerCAmelCase				   =       self.args.eval_batch_size * self.args.world_size
											if f"""{metric_key_prefix}_jit_compilation_time""" in output.metrics:
																start_time += output.metrics[f"""{metric_key_prefix}_jit_compilation_time"""]
											output.metrics.update(
											    speed_metrics(
											        _A		,			_A		,			num_samples=output.num_samples		,			num_steps=math.ceil(output.num_samples / total_batch_size			)		,			)			)

											if self.post_process_function is not None and self.compute_metrics is not None and self.args.should_save:
																# Only the main node write the results by default
																__lowerCAmelCase				   =       self.post_process_function(_A		,			_A		,			_A			)
																__lowerCAmelCase				   =       self.compute_metrics(_A			)

																# Prefix all keys with metric_key_prefix + '_'
																for key in list(metrics.keys()			):
																					if not key.startswith(f"""{metric_key_prefix}_"""			):
																										__lowerCAmelCase				   =       metrics.pop(_A			)

																metrics.update(output.metrics			)
											else:
																__lowerCAmelCase				   =       output.metrics

											if self.args.should_log:
																# Only the main node log the results by default
																self.log(_A			)

											if self.args.tpu_metrics_debug or self.args.debug:
																# tpu-comment: Logging debug metrics for PyTorch/XLA (compile, execute times, ops, etc.)
																xm.master_print(met.metrics_report()			)

											__lowerCAmelCase				   =       self.callback_handler.on_evaluate(self.args		,			self.state		,			self.control		,			_A			)
											return metrics






						def 				__SCREAMING_SNAKE_CASE(   self		,			_A		,			_A		,			_A=None		,			_A = "test"		,			**_A			):




											"""simple docstring"""



											__lowerCAmelCase				   =       gen_kwargs.copy()

											__lowerCAmelCase				   =       self.get_test_dataloader(_A			)

											# Temporarily disable metric computation, we will do it in the loop here.
											__lowerCAmelCase				   =       self.compute_metrics
											__lowerCAmelCase				   =       None
											__lowerCAmelCase				   =       time.time()
											__lowerCAmelCase				   =       self.prediction_loop if self.args.use_legacy_prediction_loop else self.evaluation_loop
											try:
																__lowerCAmelCase				   =       eval_loop(
																    _A		,			description="Prediction"		,			prediction_loss_only=True if compute_metrics is None else None		,			ignore_keys=_A		,			metric_key_prefix=_A		,			)
											finally:
																__lowerCAmelCase				   =       compute_metrics

											__lowerCAmelCase				   =       self.args.eval_batch_size * self.args.world_size
											if f"""{metric_key_prefix}_jit_compilation_time""" in output.metrics:
																start_time += output.metrics[f"""{metric_key_prefix}_jit_compilation_time"""]
											output.metrics.update(
											    speed_metrics(
											        _A		,			_A		,			num_samples=output.num_samples		,			num_steps=math.ceil(output.num_samples / total_batch_size			)		,			)			)
											if self.post_process_function is None or self.compute_metrics is None:
																return output

											__lowerCAmelCase				   =       self.post_process_function(_A		,			_A		,			_A		,			"predict"			)
											__lowerCAmelCase				   =       self.compute_metrics(_A			)

											# Prefix all keys with metric_key_prefix + '_'
											for key in list(metrics.keys()			):
																if not key.startswith(f"""{metric_key_prefix}_"""			):
																					__lowerCAmelCase				   =       metrics.pop(_A			)
											metrics.update(output.metrics			)
											return PredictionOutput(predictions=predictions.predictions		,			label_ids=predictions.label_ids		,			metrics=_A			)




