
from __future__ import annotations




def        __UpperCamelCase					(    lowerCAmelCase__							:    str  ,       lowerCAmelCase__							:    list[str] | None = None  ,       lowerCAmelCase__							:    dict[str, float] | None = None  ,       lowerCAmelCase__							:    bool = False  ,       ):
 __a			:  Tuple		    =  cipher_alphabet or [chr(lowerCAmelCase__  ) for i in range(9_7  ,       1_2_3  )]

 # If the argument is None or the user provided an empty dictionary
 if not frequencies_dict:
  # Frequencies of letters in the english language (how much they show up)
  __a			:  int		    =  {
      '''a''': 0.0_84_97,
      '''b''': 0.0_14_92,
      '''c''': 0.0_22_02,
      '''d''': 0.0_42_53,
      '''e''': 0.1_11_62,
      '''f''': 0.0_22_28,
      '''g''': 0.0_20_15,
      '''h''': 0.0_60_94,
      '''i''': 0.0_75_46,
      '''j''': 0.0_01_53,
      '''k''': 0.0_12_92,
      '''l''': 0.0_40_25,
      '''m''': 0.0_24_06,
      '''n''': 0.0_67_49,
      '''o''': 0.0_75_07,
      '''p''': 0.0_19_29,
      '''q''': 0.0_00_95,
      '''r''': 0.0_75_87,
      '''s''': 0.0_63_27,
      '''t''': 0.0_93_56,
      '''u''': 0.0_27_58,
      '''v''': 0.0_09_78,
      '''w''': 0.0_25_60,
      '''x''': 0.0_01_50,
      '''y''': 0.0_19_94,
      '''z''': 0.0_00_77,
  }
 else:
  # Custom frequencies dictionary
  __a			:  Union[str, Any]		    =  frequencies_dict

 if not case_sensitive:
  __a			:  Any		    =  ciphertext.lower()

 # Chi squared statistic values
 __a			:  dict[int, tuple[float, str]]		    =  {}

 # cycle through all of the shifts
 for shift in range(len(lowerCAmelCase__  )  ):
  __a			:  Tuple		    =  ''''''

  # decrypt the message with the shift
  for letter in ciphertext:
   try:
    # Try to index the letter in the alphabet
    __a			:  Optional[int]		    =  (alphabet_letters.index(letter.lower()  ) - shift) % len(
        lowerCAmelCase__  )
    decrypted_with_shift += (
        alphabet_letters[new_key].upper()
        if case_sensitive and letter.isupper()
        else alphabet_letters[new_key]
    )
   except ValueError:
    # Append the character if it isn't in the alphabet
    decrypted_with_shift += letter

  __a			:  str		    =  0.0

  # Loop through each letter in the decoded message with the shift
  for letter in decrypted_with_shift:
   if case_sensitive:
    __a			:  Optional[int]		    =  letter.lower()
    if letter in frequencies:
     # Get the amount of times the letter occurs in the message
     __a			:  Tuple		    =  decrypted_with_shift.lower().count(lowerCAmelCase__  )

     # Get the excepcted amount of times the letter should appear based
     # on letter frequencies
     __a			:  Any		    =  frequencies[letter] * occurrences

     # Complete the chi squared statistic formula
     __a			:  Optional[int]		    =  ((occurrences - expected) ** 2) / expected

     # Add the margin of error to the total chi squared statistic
     chi_squared_statistic += chi_letter_value
   else:
    if letter.lower() in frequencies:
     # Get the amount of times the letter occurs in the message
     __a			:  Optional[Any]		    =  decrypted_with_shift.count(lowerCAmelCase__  )

     # Get the excepcted amount of times the letter should appear based
     # on letter frequencies
     __a			:  Dict		    =  frequencies[letter] * occurrences

     # Complete the chi squared statistic formula
     __a			:  int		    =  ((occurrences - expected) ** 2) / expected

     # Add the margin of error to the total chi squared statistic
     chi_squared_statistic += chi_letter_value

        # Add the data to the chi_squared_statistic_values dictionary
  __a			:  Optional[int]		    =  (
      chi_squared_statistic,
      decrypted_with_shift,
  )

 # Get the most likely cipher by finding the cipher with the smallest chi squared
 # statistic
 def chi_squared_statistic_values_sorting_key(lowerCAmelCase__							:    int  ) -> tuple[float, str]:
  return chi_squared_statistic_values[key]

 __a			:  int		    =  min(
     lowerCAmelCase__  ,       key=lowerCAmelCase__  ,       )

 # Get all the data from the most likely cipher (key, decoded message)
 (
     __a	
 )			:  int		    =  chi_squared_statistic_values[most_likely_cipher]

 # Return the data on the most likely shift
 return (
     most_likely_cipher,
     most_likely_cipher_chi_squared_value,
     decoded_most_likely_cipher,
 )


def        __UpperCamelCase					(    lowerCAmelCase__							:    list[list[int | float]]  ):
 __a			:  int		    =  len(lowerCAmelCase__  )
 __a			:  Dict		    =  len(matrix[0]  )
 __a			:  Union[str, Any]		    =  min(lowerCAmelCase__  ,       lowerCAmelCase__  )

 for row in range(lowerCAmelCase__  ):
  # Check if diagonal element is not zero
  if matrix[row][row] != 0:
   # Eliminate all the elements below the diagonal
   for col in range(row + 1  ,       lowerCAmelCase__  ):
    __a			:  Dict		    =  matrix[col][row] / matrix[row][row]
    for i in range(lowerCAmelCase__  ,       lowerCAmelCase__  ):
     matrix[col][i] -= multiplier * matrix[row][i]
  else:
   # Find a non-zero diagonal element to swap rows
   __a			:  Optional[int]		    =  True
   for i in range(row + 1  ,       lowerCAmelCase__  ):
    if matrix[i][row] != 0:
     __a    ,	__a			:  Any		    =  matrix[i], matrix[row]
     __a			:  Union[str, Any]		    =  False
     break
   if reduce:
    rank -= 1
    for i in range(lowerCAmelCase__  ):
     __a			:  Optional[Any]		    =  matrix[i][rank]

            # Reduce the row pointer by one to stay on the same row
   row -= 1

 return rank


if __name__ == "__main__":
      import doctest

      doctest.testmod()
