import unittest

from cer import CER


lowerCAmelCase__ :			Dict         =CER()







class   __lowercase						(unittest.TestCase     ):





							"""simple docstring"""







							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    List[str] 		=				['White House']
										SCREAMING_SNAKE_CASE_		:    Any 		=				['white house']
										# S = 2, D = 0, I = 0, N = 11, CER = 2 / 11
										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.1_818_181_818					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    int 		=				['were wolf']
										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				['werewolf']
										# S = 0, D = 0, I = 1, N = 9, CER = 1 / 9
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.1_111_111					) < 1E-6					)

										SCREAMING_SNAKE_CASE_		:    Any 		=				['werewolf']
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				['weae     wolf']
										# S = 1, D = 1, I = 0, N = 8, CER = 0.25
										SCREAMING_SNAKE_CASE_		:    str 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.25					) < 1E-6					)

										# consecutive whitespaces case 1
										SCREAMING_SNAKE_CASE_		:    int 		=				['were wolf']
										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				['were               wolf']
										# S = 0, D = 0, I = 0, N = 9, CER = 0
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.0					) < 1E-6					)

										# consecutive whitespaces case 2
										SCREAMING_SNAKE_CASE_		:    Any 		=				['were   wolf']
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				['were               wolf']
										# S = 0, D = 0, I = 0, N = 9, CER = 0
										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.0					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    str 		=				['werewolf']
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				['weaewolf']
										# S = 1, D = 0, I = 0, N = 8, CER = 0.125
										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.125					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Tuple 		=				['werewolf']
										SCREAMING_SNAKE_CASE_		:    str 		=				['wereawolf']
										# S = 0, D = 1, I = 0, N = 8, CER = 0.125
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.125					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    int 		=				['werewolf']
										SCREAMING_SNAKE_CASE_		:    str 		=				['wereolf']
										# S = 0, D = 0, I = 1, N = 8, CER = 0.125
										SCREAMING_SNAKE_CASE_		:    Any 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.125					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Tuple 		=				['werewolf']
										SCREAMING_SNAKE_CASE_		:    str 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertEqual(lowerCAmelCase__ ,	0.0					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    int 		=				['werewolf', 'I am your father']
										SCREAMING_SNAKE_CASE_		:    int 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertEqual(lowerCAmelCase__ ,	0.0					)

										SCREAMING_SNAKE_CASE_		:    str 		=				['werewolf', 'I am your father', 'doge']
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				['werxwolf', 'I       am your father', 'doge']
										# S = 1, D = 0, I = 0, N = 28, CER = 1 / 28
										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.03_571_428					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Tuple 		=				['My hovercraft', 'is full of eels']
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				['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
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__ ,	concatenate_texts=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.071_428					) < 1E-6					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				['我能吞下玻璃而不伤身体']
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				[' 能吞虾玻璃而 不霜身体啦']
										# S = 3, D = 2, I = 0, N = 11, CER = 5 / 11
										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.4_545_454_545					) < 1E-6					)

										SCREAMING_SNAKE_CASE_		:    str 		=				['我能吞下玻璃', '而不伤身体']
										SCREAMING_SNAKE_CASE_		:    Dict 		=				['我    能 吞 下 玻 璃', '而不伤身体']
										# S = 0, D = 5, I = 0, N = 11, CER = 5 / 11
										SCREAMING_SNAKE_CASE_		:    Any 		=				cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)
										self.assertTrue(abs(char_error_rate - 0.454_545_454_545					) < 1E-6					)

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






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Any 		=				['']
										SCREAMING_SNAKE_CASE_		:    Any 		=				['Hypothesis']
										with self.assertRaises(lowerCAmelCase__					):
													cer.compute(predictions=lowerCAmelCase__ ,	references=lowerCAmelCase__					)


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









from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

lowerCAmelCase__ :			str         ={
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				{start}
			SCREAMING_SNAKE_CASE_		:    int 		=				[start]
			SCREAMING_SNAKE_CASE_		:    Queue 		=				Queue()
			queue.put(A__							)
			while not queue.empty():
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.get()
						for w in graph[v]:
									if w not in explored:
												explored.add(A__							)
												result.append(A__							)
												queue.put(A__							)
			return result






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Any 		=				{start}
			SCREAMING_SNAKE_CASE_		:    str 		=				[start]
			SCREAMING_SNAKE_CASE_		:    List[Any] 		=				deque([start]							)
			while queue:
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.popleft()
						for child in graph[v]:
									if child not in visited:
												visited.add(A__							)
												result.append(A__							)
												queue.append(A__							)
			return result






def 	a__ (							A__							):
			SCREAMING_SNAKE_CASE_		:    List[str] 		=				F'''from __main__ import G, {name}'''
			SCREAMING_SNAKE_CASE_		:    Tuple 		=				1_0_0_0_0
			SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				timeit(F'''{name}(G, \'A\')''',			setup=A__,			number=A__							)
			print(F'''{name:<35} finished {number} runs in {res:.5f} seconds'''							)


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				benchmark_function('breadth_first_search')
				benchmark_function('breadth_first_search_with_deque')
				# breadth_first_search                finished 10000 runs in 0.20999 seconds
				# breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds





