






from __future__ import annotations

import math




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						list:
       if len(__snake_case ) != 2 or len(a[0] ) != 2 or len(__snake_case ) != 2 or len(b[0] ) != 2:
              raise Exception("""Matrices are not 2x2""" )
       _UpperCAmelCase							=    [
           [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
           [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
       ]
       return new_matrix




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						Optional[int]:
       return [
           [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
           for row in range(len(__snake_case ) )
       ]




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						Any:
       return [
           [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
           for row in range(len(__snake_case ) )
       ]




def       _SCREAMING_SNAKE_CASE (							__snake_case )				->						tuple[list, list, list, list]:
       if len(__snake_case ) % 2 != 0 or len(a[0] ) % 2 != 0:
              raise Exception("""Odd matrices are not supported!""" )

       _UpperCAmelCase							=    len(__snake_case )
       _UpperCAmelCase							=    matrix_length // 2

       _UpperCAmelCase							=    [[a[i][j] for j in range(__snake_case   ,      __snake_case )] for i in range(__snake_case )]
       _UpperCAmelCase							=    [
           [a[i][j] for j in range(__snake_case   ,      __snake_case )] for i in range(__snake_case   ,      __snake_case )
       ]

       _UpperCAmelCase							=    [[a[i][j] for j in range(__snake_case )] for i in range(__snake_case )]
       _UpperCAmelCase							=    [[a[i][j] for j in range(__snake_case )] for i in range(__snake_case   ,      __snake_case )]

       return top_left, top_right, bot_left, bot_right




def       _SCREAMING_SNAKE_CASE (							__snake_case )				->						tuple[int, int]:
       return len(__snake_case ), len(matrix[0] )




def       _SCREAMING_SNAKE_CASE (							__snake_case )				->						None:
       print("""\n""".join(str(__snake_case ) for line in matrix ) )




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						list:
       if matrix_dimensions(__snake_case ) == (2, 2):
              return default_matrix_multiplication(__snake_case   ,      __snake_case )

       _UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase							=    split_matrix(__snake_case )
       _UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase							=    split_matrix(__snake_case )

       _UpperCAmelCase							=    actual_strassen(__snake_case   ,      matrix_subtraction(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )
       _UpperCAmelCase							=    actual_strassen(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )
       _UpperCAmelCase							=    actual_strassen(__snake_case   ,      matrix_subtraction(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_addition(__snake_case   ,      __snake_case )   ,      matrix_addition(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_subtraction(__snake_case   ,      __snake_case )   ,      matrix_addition(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_subtraction(__snake_case   ,      __snake_case )   ,      matrix_addition(__snake_case   ,      __snake_case ) )

       _UpperCAmelCase							=    matrix_addition(matrix_subtraction(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )   ,      __snake_case )
       _UpperCAmelCase							=    matrix_addition(__snake_case   ,      __snake_case )
       _UpperCAmelCase							=    matrix_addition(__snake_case   ,      __snake_case )
       _UpperCAmelCase							=    matrix_subtraction(matrix_subtraction(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )   ,      __snake_case )

       # construct the new matrix from our 4 quadrants
       _UpperCAmelCase							=    []
       for i in range(len(__snake_case ) ):
              new_matrix.append(top_left[i] + top_right[i] )
       for i in range(len(__snake_case ) ):
              new_matrix.append(bot_left[i] + bot_right[i] )
       return new_matrix




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						list:
       if matrix_dimensions(__snake_case )[1] != matrix_dimensions(__snake_case )[0]:
              _UpperCAmelCase							=    (
                  """Unable to multiply these matrices, please check the dimensions.\n"""
                  f"""Matrix A: {matrixa}\n"""
                  f"""Matrix B: {matrixa}"""
              )
              raise Exception(__snake_case )
       _UpperCAmelCase							=    matrix_dimensions(__snake_case )
       _UpperCAmelCase							=    matrix_dimensions(__snake_case )

       if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
              return [matrixa, matrixa]

       _UpperCAmelCase							=    max(*__snake_case   ,      *__snake_case )
       _UpperCAmelCase							=    int(math.pow(2   ,      math.ceil(math.loga(__snake_case ) ) ) )
       _UpperCAmelCase							=    matrixa
       _UpperCAmelCase							=    matrixa

       # Adding zeros to the matrices so that the arrays dimensions are the same and also
       # power of 2
       for i in range(0   ,      __snake_case ):
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]   ,      __snake_case ):
                            new_matrixa[i].append(0 )
              else:
                     new_matrixa.append([0] * maxim )
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]   ,      __snake_case ):
                            new_matrixa[i].append(0 )
              else:
                     new_matrixa.append([0] * maxim )

       _UpperCAmelCase							=    actual_strassen(__snake_case   ,      __snake_case )

       # Removing the additional zeros
       for i in range(0   ,      __snake_case ):
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]   ,      __snake_case ):
                            final_matrix[i].pop()
              else:
                     final_matrix.pop()
       return final_matrix


if __name__ == "__main__":
  __a:     Any   					=					[
      [2, 3, 4, 5],
      [6, 4, 3, 1],
      [2, 3, 6, 7],
      [3, 1, 2, 4],
      [2, 3, 4, 5],
      [6, 4, 3, 1],
      [2, 3, 6, 7],
      [3, 1, 2, 4],
      [2, 3, 4, 5],
      [6, 2, 3, 1],
  ]
  __a:     Any   					=					[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
  print(strassen(matrixa, matrixa))



def    __lowerCamelCase   (      A__						: int						,						A__						: int					)     ->    int:
   return int((input_a, input_a).count(0					) == 0					)


def    __lowerCamelCase   (      )     ->    None:
   assert and_gate(0						,						0					) == 0
   assert and_gate(0						,						1					) == 0
   assert and_gate(1						,						0					) == 0
   assert and_gate(1						,						1					) == 1


if __name__ == "__main__":
      test_and_gate()
      print(and_gate(1, 0))
      print(and_gate(0, 0))
      print(and_gate(0, 1))
      print(and_gate(1, 1))





