


from typing import Any






def 	__lowerCamelCase						(							lowerCamelCase__		:						list  ,							lowerCamelCase__		:						list  ,							lowerCamelCase__		:						dict  ,							lowerCamelCase__		:						dict  ,							lowerCamelCase__		:						dict  ,							):





			'''simple docstring'''




			_validation(
			    lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							)
			# Creates data structures and fill initial step
			lowerCamelCase    		=  {}
			lowerCamelCase    		=  {}
			for state in states_space:
						lowerCamelCase    		=  observations_space[0]
						lowerCamelCase    		=  (
						    initial_probabilities[state] * emission_probabilities[state][observation]
						)
						lowerCamelCase    		=  None

			# Fills the data structure with the probabilities of
			# different transitions and pointers to previous states
			for o in range(1  ,							len(lowerCamelCase__      )      ):
						lowerCamelCase    		=  observations_space[o]
						lowerCamelCase    		=  observations_space[o - 1]
						for state in states_space:
									# Calculates the argmax for probability function
									lowerCamelCase    		=  """"""
									lowerCamelCase    		=  -1
									for k_state in states_space:
												lowerCamelCase    		=  (
												    probabilities[(k_state, prior_observation)]
												    * transition_probabilities[k_state][state]
												    * emission_probabilities[state][observation]
												)
												if probability > max_probability:
															lowerCamelCase    		=  probability
															lowerCamelCase    		=  k_state

            # Update probabilities and pointers dicts
									lowerCamelCase    		=  (
									    probabilities[(arg_max, prior_observation)]
									    * transition_probabilities[arg_max][state]
									    * emission_probabilities[state][observation]
									)

									lowerCamelCase    		=  arg_max

    # The final observation
			lowerCamelCase    		=  observations_space[len(lowerCamelCase__      ) - 1]

			# argmax for given final observation
			lowerCamelCase    		=  """"""
			lowerCamelCase    		=  -1
			for k_state in states_space:
						lowerCamelCase    		=  probabilities[(k_state, final_observation)]
						if probability > max_probability:
									lowerCamelCase    		=  probability
									lowerCamelCase    		=  k_state
			lowerCamelCase    		=  arg_max

			# Process pointers backwards
			lowerCamelCase    		=  last_state
			lowerCamelCase    		=  []
			for o in range(len(lowerCamelCase__      ) - 1  ,							-1  ,							-1      ):
						result.append(lowerCamelCase__      )
						lowerCamelCase    		=  pointers[previous, observations_space[o]]
			result.reverse()

			return result






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							):





			'''simple docstring'''




			_validate_not_empty(
			    lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							)
			_validate_lists(lowerCamelCase__  ,							lowerCamelCase__      )
			_validate_dicts(
			    lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__      )






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							):





			'''simple docstring'''




			if not all(
			    [
			        observations_space,
			        states_space,
			        initial_probabilities,
			        transition_probabilities,
			        emission_probabilities,
			    ]      ):
						raise ValueError("""There's an empty parameter"""      )






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any      ):





			'''simple docstring'''




			_validate_list(lowerCamelCase__  ,							"""observations_space"""      )
			_validate_list(lowerCamelCase__  ,							"""states_space"""      )






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						str      ):





			'''simple docstring'''




			if not isinstance(_object  ,							lowerCamelCase__      ):
						lowerCamelCase    		=  f'{var_name} must be a list'
						raise ValueError(lowerCamelCase__      )
			else:
						for x in _object:
									if not isinstance(lowerCamelCase__  ,							lowerCamelCase__      ):
												lowerCamelCase    		=  f'{var_name} must be a list of strings'
												raise ValueError(lowerCamelCase__      )






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						Any  ,							):





			'''simple docstring'''




			_validate_dict(lowerCamelCase__  ,							"""initial_probabilities"""  ,							lowerCamelCase__      )
			_validate_nested_dict(lowerCamelCase__  ,							"""transition_probabilities"""      )
			_validate_nested_dict(lowerCamelCase__  ,							"""emission_probabilities"""      )






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						str      ):





			'''simple docstring'''




			_validate_dict(_object  ,							lowerCamelCase__  ,							lowerCamelCase__      )
			for x in _object.values():
						_validate_dict(lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__  ,							lowerCamelCase__      )






def 	__lowerCamelCase						(							lowerCamelCase__		:						Any  ,							lowerCamelCase__		:						str  ,							lowerCamelCase__		:						type  ,							lowerCamelCase__		:						bool = False      ):





			'''simple docstring'''




			if not isinstance(_object  ,							lowerCamelCase__      ):
						lowerCamelCase    		=  f'{var_name} must be a dict'
						raise ValueError(lowerCamelCase__      )
			if not all(isinstance(lowerCamelCase__  ,							lowerCamelCase__      ) for x in _object      ):
						lowerCamelCase    		=  f'{var_name} all keys must be strings'
						raise ValueError(lowerCamelCase__      )
			if not all(isinstance(lowerCamelCase__  ,							lowerCamelCase__      ) for x in _object.values()      ):
						lowerCamelCase    		=  """nested dictionary """ if nested else """"""
						lowerCamelCase    		=  f'{var_name} {nested_text}all values must be {value_type.__name__}'
						raise ValueError(lowerCamelCase__      )


if __name__ == "__main__":
		from doctest import testmod

		testmod()





def 	__lowerCamelCase						(							lowerCamelCase__		:						int      ):





			'''simple docstring'''




			lowerCamelCase    		=  (1 + 24 * n) ** 0.5
			return ((1 + root) / 6) % 1 == 0






def 	__lowerCamelCase						(							lowerCamelCase__		:						int = 5000      ):





			'''simple docstring'''




			lowerCamelCase    		=  [(i * (3 * i - 1)) // 2 for i in range(1  ,							lowerCamelCase__      )]
			for i, pentagonal_i in enumerate(lowerCamelCase__      ):
						for j in range(lowerCamelCase__  ,							len(lowerCamelCase__      )      ):
									lowerCamelCase    		=  pentagonal_nums[j]
									lowerCamelCase    		=  pentagonal_i + pentagonal_j
									lowerCamelCase    		=  pentagonal_j - pentagonal_i
									if is_pentagonal(lowerCamelCase__      ) and is_pentagonal(lowerCamelCase__      ):
												return b

			return -1


if __name__ == "__main__":
		print(f"""{solution() = }""")

