






from __future__ import annotations

import math

def 	lowerCAmelCase__			(      a__:		list      ,  a__:		list	)  ->		list:


							'''simple docstring'''





							if len(a__	) != 2 or len(a[0]	) != 2 or len(a__	) != 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 	lowerCAmelCase__			(      a__:		list      ,  a__:		list	)  ->		int:


							'''simple docstring'''





							return [
							    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]	)	)]
							    for row in range(len(a__	)	)
							]

def 	lowerCAmelCase__			(      a__:		list      ,  a__:		list	)  ->		Union[str, Any]:


							'''simple docstring'''





							return [
							    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]	)	)]
							    for row in range(len(a__	)	)
							]

def 	lowerCAmelCase__			(      a__:		list	)  ->		tuple[list, list, list, list]:


							'''simple docstring'''





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

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

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

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

							return top_left, top_right, bot_left, bot_right

def 	lowerCAmelCase__			(      a__:		list	)  ->		tuple[int, int]:


							'''simple docstring'''





							return len(a__	), len(matrix[0]	)

def 	lowerCAmelCase__			(      a__:		list	)  ->		None:


							'''simple docstring'''





							print('\n'.join(str(a__	) for line in matrix	)	)

def 	lowerCAmelCase__			(      a__:		list      ,  a__:		list	)  ->		list:


							'''simple docstring'''





							if matrix_dimensions(a__	) == (2, 2):
														return default_matrix_multiplication(a__      ,  a__	)

							_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase					=      split_matrix(a__	)
							_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase					=      split_matrix(a__	)

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

							_UpperCAmelCase					=      matrix_addition(matrix_subtraction(matrix_addition(a__      ,  a__	)      ,  a__	)      ,  a__	)
							_UpperCAmelCase					=      matrix_addition(a__      ,  a__	)
							_UpperCAmelCase					=      matrix_addition(a__      ,  a__	)
							_UpperCAmelCase					=      matrix_subtraction(matrix_subtraction(matrix_addition(a__      ,  a__	)      ,  a__	)      ,  a__	)

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

def 	lowerCAmelCase__			(      a__:		list      ,  a__:		list	)  ->		list:


							'''simple docstring'''





							if matrix_dimensions(a__	)[1] != matrix_dimensions(a__	)[0]:
														_UpperCAmelCase					=      (
														    'Unable to multiply these matrices, please check the dimensions.\n'
														    F'''Matrix A: {matrixa}\n'''
														    F'''Matrix B: {matrixa}'''
														)
														raise Exception(a__	)
							_UpperCAmelCase					=      matrix_dimensions(a__	)
							_UpperCAmelCase					=      matrix_dimensions(a__	)

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

							_UpperCAmelCase					=      max(*a__      ,  *a__	)
							_UpperCAmelCase					=      int(math.pow(2      ,  math.ceil(math.loga(a__	)	)	)	)
							_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      ,  a__	):
														if i < dimensiona[0]:
																					for _ in range(dimensiona[1]      ,  a__	):
																												new_matrixa[i].append(0	)
														else:
																					new_matrixa.append([0] * maxim	)
														if i < dimensiona[0]:
																					for _ in range(dimensiona[1]      ,  a__	):
																												new_matrixa[i].append(0	)
														else:
																					new_matrixa.append([0] * maxim	)

							_UpperCAmelCase					=      actual_strassen(a__      ,  a__	)

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


if __name__ == "__main__":
		lowerCAmelCase__  :Tuple             =							[
		    [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],
		]
		lowerCAmelCase__  :str             =							[[0, 2, 1, 1], [1_6, 2, 3, 3], [2, 2, 7, 7], [1_3, 1_1, 2_2, 4]]
		print(strassen(matrixa, matrixa))




from __future__ import annotations

import time
from collections.abc import Sequence
from random import randint

from matplotlib import pyplot as plt

def 	lowerCAmelCase__			(      a__:		Sequence[float]      ,  a__:		int      ,  a__:		int	)  ->		tuple[int | None, int | None, float]:


							'''simple docstring'''





							if not arr:
														return None, None, 0
							if low == high:
														return low, high, arr[low]

							_UpperCAmelCase					=      (low + high) // 2
							_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase					=      max_subarray(a__      ,  a__      ,  a__	)
							_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase					=      max_subarray(a__      ,  mid + 1      ,  a__	)
							_UpperCAmelCase		,	_UpperCAmelCase		,	_UpperCAmelCase					=      max_cross_sum(a__      ,  a__      ,  a__      ,  a__	)
							if left_sum >= right_sum and left_sum >= cross_sum:
														return left_low, left_high, left_sum
							elif right_sum >= left_sum and right_sum >= cross_sum:
														return right_low, right_high, right_sum
							return cross_left, cross_right, cross_sum

def 	lowerCAmelCase__			(      a__:		Sequence[float]      ,  a__:		int      ,  a__:		int      ,  a__:		int	)  ->		tuple[int, int, float]:


							'''simple docstring'''





							_UpperCAmelCase		,	_UpperCAmelCase					=      float('-inf'	), -1
							_UpperCAmelCase		,	_UpperCAmelCase					=      float('-inf'	), -1

							_UpperCAmelCase					=      0
							for i in range(a__      ,  low - 1      ,  -1	):
														summ += arr[i]
														if summ > left_sum:
																					_UpperCAmelCase					=      summ
																					_UpperCAmelCase					=      i

							_UpperCAmelCase					=      0
							for i in range(mid + 1      ,  high + 1	):
														summ += arr[i]
														if summ > right_sum:
																					_UpperCAmelCase					=      summ
																					_UpperCAmelCase					=      i

							return max_left, max_right, (left_sum + right_sum)

def 	lowerCAmelCase__			(      a__:		int	)  ->		float:


							'''simple docstring'''





							_UpperCAmelCase					=      [randint(1      ,  a__	) for _ in range(a__	)]
							_UpperCAmelCase					=      time.time()
							max_subarray(a__      ,  0      ,  input_size - 1	)
							_UpperCAmelCase					=      time.time()
							return end - start

def 	lowerCAmelCase__			(      )  ->		None:


							'''simple docstring'''





							_UpperCAmelCase					=      [1_0, 1_0_0, 1_0_0_0, 1_0_0_0_0, 5_0_0_0_0, 1_0_0_0_0_0, 2_0_0_0_0_0, 3_0_0_0_0_0, 4_0_0_0_0_0, 5_0_0_0_0_0]
							_UpperCAmelCase					=      [time_max_subarray(a__	) for input_size in input_sizes]
							print('No of Inputs\t\tTime Taken'	)
							for input_size, runtime in zip(a__      ,  a__	):
														print(a__      ,  '\t\t'      ,  a__	)
							plt.plot(a__      ,  a__	)
							plt.xlabel('Number of Inputs'	)
							plt.ylabel('Time taken in seconds'	)
							plt.show()


if __name__ == "__main__":
		from doctest import testmod

		testmod()
