'''simple docstring'''

from __future__ import annotations







def 					UpperCamelCase_						( snake_case_	:	str						,		snake_case_	:	dict[str, str]				) ->					str:






 '''simple docstring'''

 __lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase    							=						"""""", """""", """"""
 __lowerCAmelCase    							=						[]

 for character in message_part:
  tmp.append(character_to_number[character]				)

 for each in tmp:
  one += each[0]
  two += each[1]
  three += each[2]

 return one + two + three







def 					UpperCamelCase_						( snake_case_	:	str						,		snake_case_	:	dict[str, str]				) ->					tuple[str, str, str]:






 '''simple docstring'''

 __lowerCAmelCase							,	__lowerCAmelCase    							=						"""""", """"""
 __lowerCAmelCase    							=						[]

 for character in message_part:
  this_part += character_to_number[character]

 for digit in this_part:
  tmp += digit
  if len(snake_case_				) == len(snake_case_				):
   result.append(snake_case_				)
   __lowerCAmelCase    							=						""""""

 return result[0], result[1], result[2]







def 					UpperCamelCase_						( snake_case_	:	str						,		snake_case_	:	str				) ->					tuple[str, str, dict[str, str], dict[str, str]]:






 '''simple docstring'''

 __lowerCAmelCase    							=						alphabet.replace(""" """						,		""""""				).upper()
 __lowerCAmelCase    							=						message.replace(""" """						,		""""""				).upper()

 # Check length and characters
 if len(snake_case_				) != 27:
  raise KeyError("""Length of alphabet has to be 27."""				)
 for each in message:
  if each not in alphabet:
   raise ValueError("""Each message character has to be included in alphabet!"""				)

    # Generate dictionares
 __lowerCAmelCase    							=						(
     """111""",
     """112""",
     """113""",
     """121""",
     """122""",
     """123""",
     """131""",
     """132""",
     """133""",
     """211""",
     """212""",
     """213""",
     """221""",
     """222""",
     """223""",
     """231""",
     """232""",
     """233""",
     """311""",
     """312""",
     """313""",
     """321""",
     """322""",
     """323""",
     """331""",
     """332""",
     """333""",
 )
 __lowerCAmelCase    							=						{}
 __lowerCAmelCase    							=						{}
 for letter, number in zip(snake_case_						,		snake_case_				):
  __lowerCAmelCase    							=						number
  __lowerCAmelCase    							=						letter

 return message, alphabet, character_to_number, number_to_character







def 					UpperCamelCase_						( snake_case_	:	str						,		snake_case_	:	str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ."						,		snake_case_	:	int = 5				) ->					str:






 '''simple docstring'''

 __lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase    							=						__prepare(
     snake_case_						,		snake_case_				)
 __lowerCAmelCase							,	__lowerCAmelCase    							=						"""""", """"""

 for i in range(0						,		len(snake_case_				) + 1						,		snake_case_				):
  encrypted_numeric += __encrypt_part(
      message[i : i + period]						,		snake_case_				)

 for i in range(0						,		len(snake_case_				)						,		3				):
  encrypted += number_to_character[encrypted_numeric[i : i + 3]]

 return encrypted







def 					UpperCamelCase_						( snake_case_	:	str						,		snake_case_	:	str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ."						,		snake_case_	:	int = 5				) ->					str:






 '''simple docstring'''

 __lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase    							=						__prepare(
     snake_case_						,		snake_case_				)
 __lowerCAmelCase    							=						[]
 __lowerCAmelCase    							=						""""""

 for i in range(0						,		len(snake_case_				) + 1						,		snake_case_				):
  __lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase    							=						__decrypt_part(message[i : i + period]						,		snake_case_				)

  for j in range(0						,		len(snake_case_				)				):
   decrypted_numeric.append(a[j] + b[j] + c[j]				)

 for each in decrypted_numeric:
  decrypted += number_to_character[each]

 return decrypted


if __name__ == "__main__":
 _A      :				Optional[int] 				=    '''DEFEND THE EAST WALL OF THE CASTLE.'''
 _A      :				List[str] 				=    encrypt_message(msg, '''EPSDUCVWYM.ZLKXNBTFGORIJHAQ''')
 _A      :				str 				=    decrypt_message(encrypted, '''EPSDUCVWYM.ZLKXNBTFGORIJHAQ''')
 print(f'Encrypted: {encrypted}\nDecrypted: {decrypted}')







'''simple docstring'''

import functools
from math import sqrt
from time import time







def 					UpperCamelCase_						( snake_case_	:	Dict						,		*snake_case_	:	Union[str, Any]						,		**snake_case_	:	List[str]				) ->					List[str]:






 '''simple docstring'''

 __lowerCAmelCase    							=						time()
 __lowerCAmelCase    							=						func(*snake_case_						,		**snake_case_				)
 __lowerCAmelCase    							=						time()
 if int(end - start				) > 0:
  print(f"""{func.__name__} runtime: {(end - start):0.4f} s"""				)
 else:
  print(f"""{func.__name__} runtime: {(end - start) * 10_00:0.4f} ms"""				)
 return output







def 					UpperCamelCase_						( snake_case_	:	int				) ->					list[int]:






 '''simple docstring'''

 if n < 0:
  raise Exception("""n is negative"""				)
 if n == 0:
  return [0]
 __lowerCAmelCase    							=						[0, 1]
 for _ in range(n - 1				):
  fib.append(fib[-1] + fib[-2]				)
 return fib







def 					UpperCamelCase_						( snake_case_	:	int				) ->					list[int]:






 '''simple docstring'''

 def fib_recursive_term(snake_case_	:	int				) -> int:
  if i < 0:
   raise Exception("""n is negative"""				)
  if i < 2:
   return i
  return fib_recursive_term(i - 1				) + fib_recursive_term(i - 2				)

 if n < 0:
  raise Exception("""n is negative"""				)
 return [fib_recursive_term(snake_case_				) for i in range(n + 1				)]







def 					UpperCamelCase_						( snake_case_	:	int				) ->					list[int]:






 '''simple docstring'''

 @functools.cache
 def fib_recursive_term(snake_case_	:	int				) -> int:
  if i < 0:
   raise Exception("""n is negative"""				)
  if i < 2:
   return i
  return fib_recursive_term(i - 1				) + fib_recursive_term(i - 2				)

 if n < 0:
  raise Exception("""n is negative"""				)
 return [fib_recursive_term(snake_case_				) for i in range(n + 1				)]







def 					UpperCamelCase_						( snake_case_	:	int				) ->					list[int]:






 '''simple docstring'''

 if n < 0:
  raise Exception("""n is negative"""				)
 # Cache must be outside recursuive function
 # other it will reset every time it calls itself.
 __lowerCAmelCase    							=						{0: 0, 1: 1, 2: 1}  # Prefilled cache

 def rec_fn_memoized(snake_case_	:	int				) -> int:
  if num in cache:
   return cache[num]

  __lowerCAmelCase    							=						rec_fn_memoized(num - 1				) + rec_fn_memoized(num - 2				)
  __lowerCAmelCase    							=						value
  return value

 return [rec_fn_memoized(snake_case_				) for i in range(n + 1				)]







def 					UpperCamelCase_						( snake_case_	:	int				) ->					list[int]:






 '''simple docstring'''

 if n < 0:
  raise Exception("""n is negative"""				)
 if n >= 14_75:
  raise Exception("""n is too large"""				)
 __lowerCAmelCase    							=						sqrt(5				)
 __lowerCAmelCase    							=						(1 + sqrt_a) / 2
 return [round(phi**i / sqrt_a				) for i in range(n + 1				)]


if __name__ == "__main__":
 _A      :				Optional[Any] 				=    30
 time_func(fib_iterative, num)
 time_func(fib_recursive, num)  # Around 3s runtime
 time_func(fib_recursive_cached, num)  # Around 0ms runtime
 time_func(fib_memoization, num)
 time_func(fib_binet, num)






