




from typing import Any




def 							_UpperCAmelCase  (UpperCamelCase_ : list      ,    UpperCamelCase_ : list      ,    UpperCamelCase_ : dict      ,    UpperCamelCase_ : dict      ,    UpperCamelCase_ : dict      ,    ):
				'''simple docstring'''
				_validation(
				    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    )
				# Creates data structures and fill initial step
				_lowerCAmelCase    :    dict										=      {}
				_lowerCAmelCase    :    dict										=      {}
				for state in states_space:
								_lowerCAmelCase    :    Union[str, Any]										=      observations_space[0]
								_lowerCAmelCase    :    Any										=      (
								    initial_probabilities[state] * emission_probabilities[state][observation]
								)
								_lowerCAmelCase    :    Optional[Any]										=      None

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

            # Update probabilities and pointers dicts
												_lowerCAmelCase    :    Union[str, Any]										=      (
												    probabilities[(arg_max, prior_observation)]
												    * transition_probabilities[arg_max][state]
												    * emission_probabilities[state][observation]
												)

												_lowerCAmelCase    :    Optional[Any]										=      arg_max

    # The final observation
				_lowerCAmelCase    :    str										=      observations_space[len(UpperCamelCase_       ) - 1]

				# argmax for given final observation
				_lowerCAmelCase    :    int										=      """"""
				_lowerCAmelCase    :    List[str]										=      -1
				for k_state in states_space:
								_lowerCAmelCase    :    Optional[int]										=      probabilities[(k_state, final_observation)]
								if probability > max_probability:
												_lowerCAmelCase    :    List[Any]										=      probability
												_lowerCAmelCase    :    Union[str, Any]										=      k_state
				_lowerCAmelCase    :    Dict										=      arg_max

				# Process pointers backwards
				_lowerCAmelCase    :    Dict										=      last_state
				_lowerCAmelCase    :    int										=      []
				for o in range(len(UpperCamelCase_       ) - 1      ,    -1      ,    -1       ):
								result.append(UpperCamelCase_       )
								_lowerCAmelCase    :    Optional[Any]										=      pointers[previous, observations_space[o]]
				result.reverse()

				return result




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    ):
				'''simple docstring'''
				_validate_not_empty(
				    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    )
				_validate_lists(UpperCamelCase_      ,    UpperCamelCase_       )
				_validate_dicts(
				    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_       )




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    ):
				'''simple docstring'''
				if not all(
				    [
				        observations_space,
				        states_space,
				        initial_probabilities,
				        transition_probabilities,
				        emission_probabilities,
				    ]       ):
								raise ValueError("""There's an empty parameter"""       )




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any       ):
				'''simple docstring'''
				_validate_list(UpperCamelCase_      ,    """observations_space"""       )
				_validate_list(UpperCamelCase_      ,    """states_space"""       )




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : str       ):
				'''simple docstring'''
				if not isinstance(_object      ,    UpperCamelCase_       ):
								_lowerCAmelCase    :    List[Any]										=      F"{var_name} must be a list"
								raise ValueError(UpperCamelCase_       )
				else:
								for x in _object:
												if not isinstance(UpperCamelCase_      ,    UpperCamelCase_       ):
																_lowerCAmelCase    :    int										=      F"{var_name} must be a list of strings"
																raise ValueError(UpperCamelCase_       )




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    UpperCamelCase_ : Any      ,    ):
				'''simple docstring'''
				_validate_dict(UpperCamelCase_      ,    """initial_probabilities"""      ,    UpperCamelCase_       )
				_validate_nested_dict(UpperCamelCase_      ,    """transition_probabilities"""       )
				_validate_nested_dict(UpperCamelCase_      ,    """emission_probabilities"""       )




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : str       ):
				'''simple docstring'''
				_validate_dict(_object      ,    UpperCamelCase_      ,    UpperCamelCase_       )
				for x in _object.values():
								_validate_dict(UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_       )




def 							_UpperCAmelCase  (UpperCamelCase_ : Any      ,    UpperCamelCase_ : str      ,    UpperCamelCase_ : type      ,    UpperCamelCase_ : bool = False       ):
				'''simple docstring'''
				if not isinstance(_object      ,    UpperCamelCase_       ):
								_lowerCAmelCase    :    str										=      F"{var_name} must be a dict"
								raise ValueError(UpperCamelCase_       )
				if not all(isinstance(UpperCamelCase_      ,    UpperCamelCase_       ) for x in _object       ):
								_lowerCAmelCase    :    Tuple										=      F"{var_name} all keys must be strings"
								raise ValueError(UpperCamelCase_       )
				if not all(isinstance(UpperCamelCase_      ,    UpperCamelCase_       ) for x in _object.values()       ):
								_lowerCAmelCase    :    Tuple										=      """nested dictionary """ if nested else """"""
								_lowerCAmelCase    :    List[Any]										=      F"{var_name} {nested_text}all values must be {value_type.__name__}"
								raise ValueError(UpperCamelCase_       )


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

	testmod()







def 							_UpperCAmelCase  (UpperCamelCase_ : str      ,    UpperCamelCase_ : bool = False       ):
				'''simple docstring'''

				if not isinstance(UpperCamelCase_      ,    UpperCamelCase_       ):
								_lowerCAmelCase    :    Tuple										=      F"Expected string as input, found {type(UpperCamelCase_       )}"
								raise ValueError(UpperCamelCase_       )
				if not isinstance(UpperCamelCase_      ,    UpperCamelCase_       ):
								_lowerCAmelCase    :    Optional[Any]										=      F"Expected boolean as use_pascal parameter, found {type(UpperCamelCase_       )}"
								raise ValueError(UpperCamelCase_       )

				_lowerCAmelCase    :    Any										=      input_str.split("""_"""       )

				_lowerCAmelCase    :    str										=      0 if use_pascal else 1

				_lowerCAmelCase    :    Any										=      words[start_index:]

				_lowerCAmelCase    :    List[str]										=      [word[0].upper() + word[1:] for word in words_to_capitalize]

				_lowerCAmelCase    :    Any										=      """""" if use_pascal else words[0]

				return "".join([initial_word, *capitalized_words]       )


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

	testmod()

