"""simple docstring"""




def   UpperCAmelCase					(	UpperCamelCase__       ,    UpperCamelCase__				):






							"""simple docstring"""





							A__	     =							0
							A__	     =							len(UpperCamelCase__				) - 1

							while left <= right:
														# avoid divided by 0 during interpolation
														if sorted_collection[left] == sorted_collection[right]:
																					if sorted_collection[left] == item:
																												return left
																					else:
																												return None

														A__	     =							left + ((item - sorted_collection[left]) * (right - left)) // (
														    sorted_collection[right] - sorted_collection[left]
														)

														# out of range check
														if point < 0 or point >= len(UpperCamelCase__				):
																					return None

														A__	     =							sorted_collection[point]
														if current_item == item:
																					return point
														else:
																					if point < left:
																												A__	     =							left
																												A__	     =							point
																					elif point > right:
																												A__	     =							right
																												A__	     =							point
																					else:
																												if item < current_item:
																																			A__	     =							point - 1
																												else:
																																			A__	     =							point + 1
							return None






def   UpperCAmelCase					(	UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__				):






							"""simple docstring"""





							if sorted_collection[left] == sorted_collection[right]:
														if sorted_collection[left] == item:
																					return left
														else:
																					return None

							A__	     =							left + ((item - sorted_collection[left]) * (right - left)) // (
							    sorted_collection[right] - sorted_collection[left]
							)

							# out of range check
							if point < 0 or point >= len(UpperCamelCase__				):
														return None

							if sorted_collection[point] == item:
														return point
							elif point < left:
														return interpolation_search_by_recursion(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__				)
							elif point > right:
														return interpolation_search_by_recursion(UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__				)
							else:
														if sorted_collection[point] > item:
																					return interpolation_search_by_recursion(
																					    UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__       ,    point - 1				)
														else:
																					return interpolation_search_by_recursion(
																					    UpperCamelCase__       ,    UpperCamelCase__       ,    point + 1       ,    UpperCamelCase__				)






def   UpperCAmelCase					(	UpperCamelCase__				):






							"""simple docstring"""





							if collection != sorted(UpperCamelCase__				):
														raise ValueError('Collection must be ascending sorted'				)
							return True


if __name__ == "__main__":
				import sys
				__lowerCamelCase											=  0
				if debug == 1:
								__lowerCamelCase											=  [10, 30, 40, 45, 50, 66, 77, 93]
								try:
												__assert_sorted(collection)
								except ValueError:
												sys.exit("Sequence must be ascending sorted to apply interpolation search")
								__lowerCamelCase											=  67

				__lowerCamelCase											=  interpolation_search(collection, target)
				if result is not None:
								print(F'''{target} found at positions: {result}''')
				else:
								print("Not found")






"""simple docstring"""




import numpy as np
from PIL import Image






def   UpperCAmelCase					(	UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__				):






							"""simple docstring"""





							A__	     =							np.array(UpperCamelCase__				)
							if arr.shape[0] != arr.shape[1]:
														raise ValueError('The input array is not a square matrix'				)
							A__	     =							0
							A__	     =							0
							A__	     =							0
							A__	     =							0

							# compute the shape of the output matrix
							A__	     =							(arr.shape[0] - size) // stride + 1
							# initialize the output matrix with zeros of shape maxpool_shape
							A__	     =							np.zeros((maxpool_shape, maxpool_shape)				)

							while i < arr.shape[0]:
														if i + size > arr.shape[0]:
																					# if the end of the matrix is reached, break
																					break
														while j < arr.shape[1]:
																					# if the end of the matrix is reached, break
																					if j + size > arr.shape[1]:
																												break
																					# compute the maximum of the pooling matrix
																					A__	     =							np.max(arr[i : i + size, j : j + size]				)
																					# shift the pooling matrix by stride of column pixels
																					j += stride
																					mat_j += 1

														# shift the pooling matrix by stride of row pixels
														i += stride
														mat_i += 1

														# reset the column index to 0
														A__	     =							0
														A__	     =							0

							return updated_arr






def   UpperCAmelCase					(	UpperCamelCase__       ,    UpperCamelCase__       ,    UpperCamelCase__				):






							"""simple docstring"""





							A__	     =							np.array(UpperCamelCase__				)
							if arr.shape[0] != arr.shape[1]:
														raise ValueError('The input array is not a square matrix'				)
							A__	     =							0
							A__	     =							0
							A__	     =							0
							A__	     =							0

							# compute the shape of the output matrix
							A__	     =							(arr.shape[0] - size) // stride + 1
							# initialize the output matrix with zeros of shape avgpool_shape
							A__	     =							np.zeros((avgpool_shape, avgpool_shape)				)

							while i < arr.shape[0]:
														# if the end of the matrix is reached, break
														if i + size > arr.shape[0]:
																					break
														while j < arr.shape[1]:
																					# if the end of the matrix is reached, break
																					if j + size > arr.shape[1]:
																												break
																					# compute the average of the pooling matrix
																					A__	     =							int(np.average(arr[i : i + size, j : j + size]				)				)
																					# shift the pooling matrix by stride of column pixels
																					j += stride
																					mat_j += 1

														# shift the pooling matrix by stride of row pixels
														i += stride
														mat_i += 1
														# reset the column index to 0
														A__	     =							0
														A__	     =							0

							return updated_arr


# Main Function
if __name__ == "__main__":
				from doctest import testmod

				testmod(name="avgpooling", verbose=True)

				# Loading the image
				__lowerCamelCase											=  Image.open("path_to_image")

				# Converting the image to numpy array and maxpooling, displaying the result
				# Ensure that the image is a square matrix

				Image.fromarray(maxpooling(np.array(image), size=3, stride=2)).show()

				# Converting the image to numpy array and averagepooling, displaying the result
				# Ensure that the image is a square matrix

				Image.fromarray(avgpooling(np.array(image), size=3, stride=2)).show()





