



'''simple docstring'''




import numpy as np
from PIL import Image


def 				lowerCAmelCase_   (	_lowerCamelCase:   Optional[Any]       ,      _lowerCamelCase:   str       ,      _lowerCamelCase:   Optional[int]					):
		__SCREAMING_SNAKE_CASE       :		int           =		np.array(_lowerCamelCase					)
		if arr.shape[0] != arr.shape[1]:
				raise ValueError("""The input array is not a square matrix"""					)
		__SCREAMING_SNAKE_CASE       :		Optional[int]           =		0
		__SCREAMING_SNAKE_CASE       :		Any           =		0
		__SCREAMING_SNAKE_CASE       :		int           =		0
		__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		0

		# compute the shape of the output matrix
		__SCREAMING_SNAKE_CASE       :		Any           =		(arr.shape[0] - size) // stride + 1
		# initialize the output matrix with zeros of shape maxpool_shape
		__SCREAMING_SNAKE_CASE       :		Tuple           =		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
						__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		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
				__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		0
				__SCREAMING_SNAKE_CASE       :		List[str]           =		0

		return updated_arr


def 				lowerCAmelCase_   (	_lowerCamelCase:   int       ,      _lowerCamelCase:   List[Any]       ,      _lowerCamelCase:   Dict					):
		__SCREAMING_SNAKE_CASE       :		Optional[int]           =		np.array(_lowerCamelCase					)
		if arr.shape[0] != arr.shape[1]:
				raise ValueError("""The input array is not a square matrix"""					)
		__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		0
		__SCREAMING_SNAKE_CASE       :		Optional[int]           =		0
		__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		0
		__SCREAMING_SNAKE_CASE       :		Dict           =		0

		# compute the shape of the output matrix
		__SCREAMING_SNAKE_CASE       :		Optional[Any]           =		(arr.shape[0] - size) // stride + 1
		# initialize the output matrix with zeros of shape avgpool_shape
		__SCREAMING_SNAKE_CASE       :		int           =		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
						__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		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
				__SCREAMING_SNAKE_CASE       :		Dict           =		0
				__SCREAMING_SNAKE_CASE       :		Union[str, Any]           =		0

		return updated_arr


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

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

						# Loading the image
						UpperCamelCase__       :	Union[str, Any]    = 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()



__lowerCAmelCase		       =							{
    '''A''': ['''B''', '''C''', '''E'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F''', '''G'''],
    '''D''': ['''B'''],
    '''E''': ['''A''', '''B''', '''D'''],
    '''F''': ['''C'''],
    '''G''': ['''C'''],
}




def    snake_case_     (  snake_case			,							snake_case			,							snake_case     )  ->				list[str]:
       lowercase__:   int  			=   set()
       # keep track of all the paths to be checked
       lowercase__:   Optional[int]  			=   [[start]]

       # return path if start is goal
       if start == goal:
              return [start]

       # keeps looping until all possible paths have been checked
       while queue:
              # pop the first path from the queue
              lowercase__:   List[Any]  			=   queue.pop(0     )
              # get the last node from the path
              lowercase__:   Optional[int]  			=   path[-1]
              if node not in explored:
                     lowercase__:   Optional[Any]  			=   graph[node]
                     # go through all neighbour nodes, construct a new path and
                     # push it into the queue
                     for neighbour in neighbours:
                            lowercase__:   Tuple  			=   list(snake_case     )
                            new_path.append(snake_case     )
                            queue.append(snake_case     )
                            # return path if neighbour is goal
                            if neighbour == goal:
                                   return new_path

            # mark node as explored
                     explored.add(snake_case     )

    # in case there's no path between the 2 nodes
       return []




def    snake_case_     (  snake_case			,							snake_case			,							snake_case     )  ->				int:
       if not graph or start not in graph or target not in graph:
              return -1
       if start == target:
              return 0
       lowercase__:   Tuple  			=   [start]
       lowercase__:   List[Any]  			=   set(snake_case     )
       # Keep tab on distances from `start` node.
       lowercase__:   Tuple  			=   {start: 0, target: -1}
       while queue:
              lowercase__:   Dict  			=   queue.pop(0     )
              if node == target:
                     lowercase__:   str  			=   (
                         dist[node] if dist[target] == -1 else min(dist[target]			,							dist[node]     )
                     )
              for adjacent in graph[node]:
                     if adjacent not in visited:
                            visited.add(snake_case     )
                            queue.append(snake_case     )
                            lowercase__:   List[str]  			=   dist[node] + 1
       return dist[target]


if __name__ == "__main__":
 print(bfs_shortest_path(demo_graph, '''G''', '''D'''))  # returns ['G', 'C', 'A', 'B', 'D']
 print(bfs_shortest_path_distance(demo_graph, '''G''', '''D'''))  # returns 4


