

from __future__ import annotations






def        lowerCamelCase_  (				UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int						)    ->					int:




	'''simple docstring'''




	assert n > 1 and a > 0 and greatest_common_divisor(UpperCAmelCase_				,							UpperCAmelCase_						) == 1
	((_UpperCamelCase)						,		(_UpperCamelCase)						,		(_UpperCamelCase)) :		Tuple								=    extended_gcd(UpperCAmelCase_				,							UpperCAmelCase_						)  # Implemented below
	_UpperCamelCase :		str								=    (b * s) % n
	return x






def        lowerCamelCase_  (				UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int						)    ->					int:




	'''simple docstring'''




	((_UpperCamelCase)						,		(_UpperCamelCase)) :		Dict								=    extended_euclid(UpperCAmelCase_				,							UpperCAmelCase_						)  # Implemented below
	if b < 0:
		_UpperCamelCase :		int								=    (b % n + n) % n
	return b






def        lowerCamelCase_  (				UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int						)    ->					int:




	'''simple docstring'''




	_UpperCamelCase :		Any								=    invert_modulo(UpperCAmelCase_				,							UpperCAmelCase_						)
	_UpperCamelCase :		int								=    (b * s) % n
	return x






def        lowerCamelCase_  (				UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int						)    ->					tuple[int, int, int]:




	'''simple docstring'''




	assert a >= 0 and b >= 0

	if b == 0:
		_UpperCamelCase						,		_UpperCamelCase						,		_UpperCamelCase :		Tuple								=    a, 1, 0
	else:
		((_UpperCamelCase)						,		(_UpperCamelCase)						,		(_UpperCamelCase)) :		str								=    extended_gcd(UpperCAmelCase_				,							a % b						)
		_UpperCamelCase :		int								=    q
		_UpperCamelCase :		Optional[int]								=    p - q * (a // b)

	assert a % d == 0 and b % d == 0
	assert d == a * x + b * y

	return (d, x, y)






def        lowerCamelCase_  (				UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int						)    ->					tuple[int, int]:




	'''simple docstring'''




	if b == 0:
		return (1, 0)
	((_UpperCamelCase)						,		(_UpperCamelCase)) :		Any								=    extended_euclid(UpperCAmelCase_				,							a % b						)
	_UpperCamelCase :		Optional[int]								=    a // b
	return (y, x - k * y)






def        lowerCamelCase_  (				UpperCAmelCase_				:  int				,							UpperCAmelCase_				:  int						)    ->					int:




	'''simple docstring'''




	if a < b:
		_UpperCamelCase						,		_UpperCamelCase :		Optional[int]								=    b, a

	while a % b != 0:
		_UpperCamelCase						,		_UpperCamelCase :		Tuple								=    b, a % b

	return b


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

							testmod(name="""modular_division""", verbose=True)
							testmod(name="""modular_division2""", verbose=True)
							testmod(name="""invert_modulo""", verbose=True)
							testmod(name="""extended_gcd""", verbose=True)
							testmod(name="""extended_euclid""", verbose=True)
							testmod(name="""greatest_common_divisor""", verbose=True)







import unittest

from cer import CER


lowerCAmelCase__             =		CER()







class 						lowercase     (					unittest.TestCase				):


		"""simple docstring"""




		def 		A__       (					self):
			_UpperCamelCase :		Any								=    ['White House']
			_UpperCamelCase :		Tuple								=    ['white house']
			# S = 2, D = 0, I = 0, N = 11, CER = 2 / 11
			_UpperCamelCase :		Tuple								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.1_8_1_8_1_8_1_8_1_8) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		Union[str, Any]								=    ['were wolf']
			_UpperCamelCase :		List[Any]								=    ['werewolf']
			# S = 0, D = 0, I = 1, N = 9, CER = 1 / 9
			_UpperCamelCase :		Dict								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.1_1_1_1_1_1_1) < 1e-6)

			_UpperCamelCase :		int								=    ['werewolf']
			_UpperCamelCase :		Optional[Any]								=    ['weae     wolf']
			# S = 1, D = 1, I = 0, N = 8, CER = 0.25
			_UpperCamelCase :		str								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.2_5) < 1e-6)

			# consecutive whitespaces case 1
			_UpperCamelCase :		Tuple								=    ['were wolf']
			_UpperCamelCase :		Dict								=    ['were               wolf']
			# S = 0, D = 0, I = 0, N = 9, CER = 0
			_UpperCamelCase :		List[str]								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.0) < 1e-6)

			# consecutive whitespaces case 2
			_UpperCamelCase :		Dict								=    ['were   wolf']
			_UpperCamelCase :		Dict								=    ['were               wolf']
			# S = 0, D = 0, I = 0, N = 9, CER = 0
			_UpperCamelCase :		Dict								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.0) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		Tuple								=    ['werewolf']
			_UpperCamelCase :		Optional[Any]								=    ['weaewolf']
			# S = 1, D = 0, I = 0, N = 8, CER = 0.125
			_UpperCamelCase :		List[str]								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.1_2_5) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		int								=    ['werewolf']
			_UpperCamelCase :		Any								=    ['wereawolf']
			# S = 0, D = 1, I = 0, N = 8, CER = 0.125
			_UpperCamelCase :		Optional[int]								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.1_2_5) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		str								=    ['werewolf']
			_UpperCamelCase :		Optional[Any]								=    ['wereolf']
			# S = 0, D = 0, I = 1, N = 8, CER = 0.125
			_UpperCamelCase :		List[Any]								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.1_2_5) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		Optional[Any]								=    ['werewolf']
			_UpperCamelCase :		Optional[Any]								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertEqual(__snake_case						,							0.0)


		def 		A__       (					self):
			_UpperCamelCase :		Union[str, Any]								=    ['werewolf', 'I am your father']
			_UpperCamelCase :		Dict								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertEqual(__snake_case						,							0.0)

			_UpperCamelCase :		List[Any]								=    ['werewolf', 'I am your father', 'doge']
			_UpperCamelCase :		Optional[int]								=    ['werxwolf', 'I       am your father', 'doge']
			# S = 1, D = 0, I = 0, N = 28, CER = 1 / 28
			_UpperCamelCase :		Any								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.0_3_5_7_1_4_2_8) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		Tuple								=    ['My hovercraft', 'is full of eels']
			_UpperCamelCase :		List[Any]								=    ['My hovercraft is full', ' of eels']
			# S = 0, D = 0, I = 2, N = 28, CER = 2 / 28
			# whitespace at the front of " of eels" will be strip during preporcessing
			# so need to insert 2 whitespaces
			_UpperCamelCase :		Dict								=    cer.compute(predictions=__snake_case						,							references=__snake_case						,							concatenate_texts=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.0_7_1_4_2_8) < 1e-6)


		def 		A__       (					self):
			_UpperCamelCase :		Union[str, Any]								=    ['我能吞下玻璃而不伤身体']
			_UpperCamelCase :		Optional[Any]								=    [' 能吞虾玻璃而 不霜身体啦']
			# S = 3, D = 2, I = 0, N = 11, CER = 5 / 11
			_UpperCamelCase :		Any								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.4_5_4_5_4_5_4_5_4_5) < 1e-6)

			_UpperCamelCase :		Union[str, Any]								=    ['我能吞下玻璃', '而不伤身体']
			_UpperCamelCase :		List[str]								=    ['我    能 吞 下 玻 璃', '而不伤身体']
			# S = 0, D = 5, I = 0, N = 11, CER = 5 / 11
			_UpperCamelCase :		Union[str, Any]								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertTrue(abs(char_error_rate - 0.4_5_4_5_4_5_4_5_4_5_4_5) < 1e-6)

			_UpperCamelCase :		Optional[int]								=    ['我能吞下玻璃而不伤身体']
			_UpperCamelCase :		int								=    cer.compute(predictions=__snake_case						,							references=__snake_case)
			self.assertFalse(__snake_case						,							0.0)






		def 		A__       (					self):
			_UpperCamelCase :		Tuple								=    ['']
			_UpperCamelCase :		Dict								=    ['Hypothesis']
			with self.assertRaises(__snake_case):
				cer.compute(predictions=__snake_case						,							references=__snake_case)


if __name__ == "__main__":
							unittest.main()




