



'''simple docstring'''



import builtins
import sys

from ...utils.imports import _is_package_available
from . import cursor, input
from .helpers import Direction, clear_line, forceWrite, linebreak, move_cursor, reset_cursor, writeColor
from .keymap import KEYMAP


lowerCAmelCase	:		str				=   False
try:
	lowerCAmelCase	:		int				=   _is_package_available('''google.colab''')
except ModuleNotFoundError:
	pass






@input.register
class 					UpperCAmelCase__	:



					def __init__(    self			,				UpperCamelCase = None			,				UpperCamelCase = []     )     ->			Optional[int]:
						__lowerCAmelCase												=  0
						__lowerCAmelCase												=  choices
						__lowerCAmelCase												=  prompt
						if sys.platform == "win32":
							__lowerCAmelCase												=  "*"
						else:
							__lowerCAmelCase												=  "➔ "



					def        UpperCAmelCase_ (    self			,				UpperCamelCase			,				UpperCamelCase = ""     )     ->			Union[str, Any]:
						if sys.platform != "win32":
							writeColor(self.choices[index]			,				32			,				UpperCamelCase     )
						else:
							forceWrite(self.choices[index]			,				UpperCamelCase     )



					def        UpperCAmelCase_ (    self			,				UpperCamelCase     )     ->			Any:
						if index == self.position:
							forceWrite(F''' {self.arrow_char} '''     )
							self.write_choice(UpperCamelCase     )
						else:
							forceWrite(F'''    {self.choices[index]}'''     )
						reset_cursor()



					def        UpperCAmelCase_ (    self			,				UpperCamelCase			,				UpperCamelCase = 1     )     ->			Union[str, Any]:
						__lowerCAmelCase												=  self.position
						if direction == Direction.DOWN:
							if self.position + 1 >= len(self.choices     ):
								return
							self.position += num_spaces
						else:
							if self.position - 1 < 0:
								return
							self.position -= num_spaces
						clear_line()
						self.print_choice(UpperCamelCase     )
						move_cursor(UpperCamelCase			,				direction.name     )
						self.print_choice(self.position     )



					@input.mark(KEYMAP["up"]     )
					def        UpperCAmelCase_ (    self     )     ->			Tuple:
						self.move_direction(Direction.UP     )



					@input.mark(KEYMAP["down"]     )
					def        UpperCAmelCase_ (    self     )     ->			Tuple:
						self.move_direction(Direction.DOWN     )



					@input.mark(KEYMAP["newline"]     )
					def        UpperCAmelCase_ (    self     )     ->			Any:
						move_cursor(len(self.choices     ) - self.position			,				"DOWN"     )
						return self.position



					@input.mark(KEYMAP["interrupt"]     )
					def        UpperCAmelCase_ (    self     )     ->			Optional[Any]:
						move_cursor(len(self.choices     ) - self.position			,				"DOWN"     )
						raise KeyboardInterrupt



					@input.mark_multiple(*[KEYMAP[str(UpperCamelCase     )] for number in range(10     )]     )
					def        UpperCAmelCase_ (    self     )     ->			Dict:
						__lowerCAmelCase												=  int(chr(self.current_selection     )     )
						__lowerCAmelCase												=  index - self.position
						if index == self.position:
							return
						if index < len(self.choices     ):
							if self.position > index:
								self.move_direction(Direction.UP			,				-movement     )
							elif self.position < index:
								self.move_direction(Direction.DOWN			,				UpperCamelCase     )
							else:
								return
						else:
							return



					def        UpperCAmelCase_ (    self			,				UpperCamelCase = 0     )     ->			str:
						if self.prompt:
							linebreak()
							forceWrite(self.prompt			,				"\n"     )
							if in_colab:
								forceWrite("Please input a choice index (starting from 0), and press enter"			,				"\n"     )
							else:
								forceWrite("Please select a choice using the arrow or number keys, and selecting with enter"			,				"\n"     )
						__lowerCAmelCase												=  default_choice
						for i in range(len(self.choices     )     ):
							self.print_choice(UpperCamelCase     )
							forceWrite("\n"     )
						move_cursor(len(self.choices     ) - self.position			,				"UP"     )
						with cursor.hide():
							while True:
								if in_colab:
									try:
										__lowerCAmelCase												=  int(builtins.input()     )
									except ValueError:
										__lowerCAmelCase												=  default_choice
								else:
									__lowerCAmelCase												=  self.handle_input()
								if choice is not None:
									reset_cursor()
									for _ in range(len(self.choices     ) + 1     ):
										move_cursor(1			,				"UP"     )
										clear_line()
									self.write_choice(UpperCamelCase			,				"\n"     )
									return choice




'''simple docstring'''



from __future__ import annotations

import math



def   __lowerCAmelCase					(							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"					)
	__lowerCAmelCase												=  [
	    [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					(							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   __lowerCAmelCase					(							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   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




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

	__lowerCAmelCase												=  len(lowerCamelCase					)
	__lowerCAmelCase												=  matrix_length // 2

	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase				,		lowerCamelCase					)] for i in range(lowerCamelCase					)]
	__lowerCAmelCase												=  [
	    [a[i][j] for j in range(lowerCamelCase				,		lowerCamelCase					)] for i in range(lowerCamelCase				,		lowerCamelCase					)
	]

	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase					)] for i in range(lowerCamelCase					)]
	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase					)] for i in range(lowerCamelCase				,		lowerCamelCase					)]

	return top_left, top_right, bot_left, bot_right



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




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



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




	print("\n".join(str(lowerCamelCase					) for line in matrix					)					)



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




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

	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  split_matrix(lowerCamelCase					)
	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  split_matrix(lowerCamelCase					)

	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)

	__lowerCAmelCase												=  matrix_addition(matrix_subtraction(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_addition(lowerCamelCase				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_addition(lowerCamelCase				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_subtraction(matrix_subtraction(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)				,		lowerCamelCase					)

	# construct the new matrix from our 4 quadrants
	__lowerCAmelCase												=  []
	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   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




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

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

	__lowerCAmelCase												=  max(*lowerCamelCase				,		*lowerCamelCase					)
	__lowerCAmelCase												=  int(math.pow(2				,		math.ceil(math.loga(lowerCamelCase					)					)					)					)
	__lowerCAmelCase												=  matrixa
	__lowerCAmelCase												=  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					)

	__lowerCAmelCase												=  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__":
	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	:		Any				=   [[0, 2, 1, 1], [1_6, 2, 3, 3], [2, 2, 7, 7], [1_3, 1_1, 2_2, 4]]
	print(strassen(matrixa, matrixa))