


'''simple docstring'''






import argparse
from collections import defaultdict





def      UpperCAmelCase      (		lowerCamelCase_  :List[str]				,      lowerCamelCase_  :Any				,      lowerCamelCase_  :int				,      lowerCamelCase_  :Any				,      lowerCamelCase_  :Optional[int] ):







		'''simple docstring'''
		snake_case_		:							Any			       =						F'''{file}_{class_name}_{test_name}'''
		done_test[_id] += 1

		with open(lowerCamelCase_				,      """r""" ) as f:
				snake_case_		:							Optional[Any]			       =						f.readlines()

		snake_case_		:							int			       =						F'''class {class_name}('''
		snake_case_		:							Dict			       =						F'''{4 * " "}def {test_name}('''
		snake_case_		:							Dict			       =						F'''{8 * " "}{correct_line.split()[0]}'''
		snake_case_		:							Optional[int]			       =						F'''{16 * " "}{correct_line.split()[0]}'''
		snake_case_		:							int			       =						False
		snake_case_		:							Optional[Any]			       =						False
		snake_case_		:							Dict			       =						False
		snake_case_		:							List[str]			       =						False
		snake_case_		:							Optional[Any]			       =						0
		snake_case_		:							Dict			       =						0

		snake_case_		:							Any			       =						[]
		for line in lines:
				if line.startswith(lowerCamelCase_ ):
						snake_case_		:							str			       =						True
				elif in_class and line.startswith(lowerCamelCase_ ):
						snake_case_		:							str			       =						True
				elif in_class and in_func and (line.startswith(lowerCamelCase_ ) or line.startswith(lowerCamelCase_ )):
						snake_case_		:							Tuple			       =						len(line.split(correct_line.split()[0] )[0] )
						count += 1

						if count == done_test[_id]:
								snake_case_		:							Optional[int]			       =						True

				if in_class and in_func and in_line:
						if ")" not in line:
								continue
						else:
								snake_case_		:							Union[str, Any]			       =						True

				if in_class and in_func and in_line and insert_line:
						new_lines.append(F'''{spaces * " "}{correct_line}''' )
						snake_case_		:							Any			       =						False
				else:
						new_lines.append(lowerCamelCase_ )

		with open(lowerCamelCase_				,      """w""" ) as f:
				for line in new_lines:
						f.write(lowerCamelCase_ )





def      UpperCAmelCase      (		lowerCamelCase_  :List[Any]				,      lowerCamelCase_  :str=None ):







		'''simple docstring'''
		if fail is not None:
				with open(lowerCamelCase_				,      """r""" ) as f:
						snake_case_		:							Tuple			       =						{l.strip() for l in f.readlines()}
		else:
				snake_case_		:							List[Any]			       =						None

		with open(lowerCamelCase_				,      """r""" ) as f:
				snake_case_		:							int			       =						f.readlines()

		snake_case_		:							int			       =						defaultdict(lowerCamelCase_ )
		for line in correct_lines:
				snake_case_		:							Any			       =						line.split(""";""" )
				if test_failures is None or "::".join([file, class_name, test_name] ) in test_failures:
						overwrite_file(lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_				,      lowerCamelCase_ )


if __name__ == "__main__":
							__A	:	Optional[Any]     =     argparse.ArgumentParser()
							parser.add_argument('--correct_filename', help='filename of tests with expected result')
							parser.add_argument('--fail_filename', help='filename of test failures', type=str, default=None)
							__A	:	int     =     parser.parse_args()

							main(args.correct_filename, args.fail_filename)



'''simple docstring'''






from __future__ import annotations

import math





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		if len(lowerCamelCase_ ) != 2 or len(a[0] ) != 2 or len(lowerCamelCase_ ) != 2 or len(b[0] ) != 2:
				raise Exception("""Matrices are not 2x2""" )
		snake_case_		:							Tuple			       =						[
		    [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      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		return [
		    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
		    for row in range(len(lowerCamelCase_ ) )
		]





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		return [
		    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
		    for row in range(len(lowerCamelCase_ ) )
		]





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







		'''simple docstring'''
		if len(lowerCamelCase_ ) % 2 != 0 or len(a[0] ) % 2 != 0:
				raise Exception("""Odd matrices are not supported!""" )

		snake_case_		:							Optional[int]			       =						len(lowerCamelCase_ )
		snake_case_		:							List[str]			       =						matrix_length // 2

		snake_case_		:							Union[str, Any]			       =						[[a[i][j] for j in range(lowerCamelCase_				,      lowerCamelCase_ )] for i in range(lowerCamelCase_ )]
		snake_case_		:							Dict			       =						[
		    [a[i][j] for j in range(lowerCamelCase_				,      lowerCamelCase_ )] for i in range(lowerCamelCase_				,      lowerCamelCase_ )
		]

		snake_case_		:							str			       =						[[a[i][j] for j in range(lowerCamelCase_ )] for i in range(lowerCamelCase_ )]
		snake_case_		:							Dict			       =						[[a[i][j] for j in range(lowerCamelCase_ )] for i in range(lowerCamelCase_				,      lowerCamelCase_ )]

		return top_left, top_right, bot_left, bot_right





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







		'''simple docstring'''
		return len(lowerCamelCase_ ), len(matrix[0] )





def      UpperCAmelCase      (		lowerCamelCase_  :list ):







		'''simple docstring'''
		print("""\n""".join(str(lowerCamelCase_ ) for line in matrix ) )





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		if matrix_dimensions(lowerCamelCase_ ) == (2, 2):
				return default_matrix_multiplication(lowerCamelCase_				,      lowerCamelCase_ )

		snake_case_       ,      snake_case_       ,      snake_case_       ,      snake_case_		:							Any			       =						split_matrix(lowerCamelCase_ )
		snake_case_       ,      snake_case_       ,      snake_case_       ,      snake_case_		:							List[Any]			       =						split_matrix(lowerCamelCase_ )

		snake_case_		:							Any			       =						actual_strassen(lowerCamelCase_				,      matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							str			       =						actual_strassen(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )
		snake_case_		:							str			       =						actual_strassen(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )
		snake_case_		:							List[str]			       =						actual_strassen(lowerCamelCase_				,      matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							Optional[int]			       =						actual_strassen(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      matrix_addition(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							Dict			       =						actual_strassen(matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ )				,      matrix_addition(lowerCamelCase_				,      lowerCamelCase_ ) )
		snake_case_		:							int			       =						actual_strassen(matrix_subtraction(lowerCamelCase_				,      lowerCamelCase_ )				,      matrix_addition(lowerCamelCase_				,      lowerCamelCase_ ) )

		snake_case_		:							List[Any]			       =						matrix_addition(matrix_subtraction(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )				,      lowerCamelCase_ )
		snake_case_		:							List[Any]			       =						matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )
		snake_case_		:							str			       =						matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )
		snake_case_		:							Any			       =						matrix_subtraction(matrix_subtraction(matrix_addition(lowerCamelCase_				,      lowerCamelCase_ )				,      lowerCamelCase_ )				,      lowerCamelCase_ )

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





def      UpperCAmelCase      (		lowerCamelCase_  :list				,      lowerCamelCase_  :list ):







		'''simple docstring'''
		if matrix_dimensions(lowerCamelCase_ )[1] != matrix_dimensions(lowerCamelCase_ )[0]:
				snake_case_		:							Optional[int]			       =						(
				    """Unable to multiply these matrices, please check the dimensions.\n"""
				    F'''Matrix A: {matrixa}\n'''
				    F'''Matrix B: {matrixa}'''
				)
				raise Exception(lowerCamelCase_ )
		snake_case_		:							Tuple			       =						matrix_dimensions(lowerCamelCase_ )
		snake_case_		:							Union[str, Any]			       =						matrix_dimensions(lowerCamelCase_ )

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

		snake_case_		:							int			       =						max(*lowerCamelCase_				,      *lowerCamelCase_ )
		snake_case_		:							Union[str, Any]			       =						int(math.pow(2				,      math.ceil(math.loga(lowerCamelCase_ ) ) ) )
		snake_case_		:							Dict			       =						matrixa
		snake_case_		:							Optional[int]			       =						matrixa

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

		snake_case_		:							Dict			       =						actual_strassen(lowerCamelCase_				,      lowerCamelCase_ )

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


if __name__ == "__main__":
							__A	:	Optional[int]     =     [
							    [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	:	List[str]     =     [[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
							print(strassen(matrixa, matrixa))