



"""simple docstring"""
from __future__ import annotations

__SCREAMING_SNAKE_CASE  :						List[str]    							=      [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]



def        lowerCAmelCase_(   lowercase_     :							list[list[int]]						,   lowercase_     :							list[int]						,   lowercase_     :							list[int]						,   lowercase_     :							int						,   lowercase_     :							list[list[int]]						,   )	->       tuple[list[list[int]], list[list[int]]]:
				_lowerCamelCase        =				[
				    [0 for col in range(len(grid[0]							)							)] for row in range(len(lowercase_							)							)
				]  # the reference grid
				_lowerCamelCase        =				1
				_lowerCamelCase        =				[
				    [0 for col in range(len(grid[0]							)							)] for row in range(len(lowercase_							)							)
				]  # the action grid

				_lowerCamelCase        =				init[0]
				_lowerCamelCase        =				init[1]
				_lowerCamelCase        =				0
				_lowerCamelCase        =				g + heuristic[x][y]  # cost from starting cell to destination cell
				_lowerCamelCase        =				[[f, g, x, y]]

				_lowerCamelCase        =				False  # flag that is set when search is complete
				_lowerCamelCase        =				False  # flag set if we can't find expand

				while not found and not resign:
								if len(lowercase_							) == 0:
												raise ValueError('''Algorithm is unable to find solution'''							)
								else:  # to choose the least costliest action so as to move closer to the goal
												cell.sort()
												cell.reverse()
												_lowerCamelCase        =				cell.pop()
												_lowerCamelCase        =				next_cell[2]
												_lowerCamelCase        =				next_cell[3]
												_lowerCamelCase        =				next_cell[1]

												if x == goal[0] and y == goal[1]:
																_lowerCamelCase        =				True
												else:
																for i in range(len(lowercase_							)							):  # to try out different valid actions
																				_lowerCamelCase        =				x + DIRECTIONS[i][0]
																				_lowerCamelCase        =				y + DIRECTIONS[i][1]
																				if xa >= 0 and xa < len(lowercase_							) and ya >= 0 and ya < len(grid[0]							):
																								if closed[xa][ya] == 0 and grid[xa][ya] == 0:
																												_lowerCamelCase        =				g + cost
																												_lowerCamelCase        =				ga + heuristic[xa][ya]
																												cell.append([fa, ga, xa, ya]							)
																												_lowerCamelCase        =				1
																												_lowerCamelCase        =				i
				_lowerCamelCase        =				[]
				_lowerCamelCase        =				goal[0]
				_lowerCamelCase        =				goal[1]
				invpath.append([x, y]							)  # we get the reverse path from here
				while x != init[0] or y != init[1]:
								_lowerCamelCase        =				x - DIRECTIONS[action[x][y]][0]
								_lowerCamelCase        =				y - DIRECTIONS[action[x][y]][1]
								_lowerCamelCase        =				xa
								_lowerCamelCase        =				ya
								invpath.append([x, y]							)

				_lowerCamelCase        =				[]
				for i in range(len(lowercase_							)							):
								path.append(invpath[len(lowercase_							) - 1 - i]							)
				return path, action


if __name__ == "__main__":
			__SCREAMING_SNAKE_CASE  :						Union[str, Any]    							=      [
			    [0, 1, 0, 0, 0, 0],
			    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
			    [0, 1, 0, 0, 0, 0],
			    [0, 1, 0, 0, 1, 0],
			    [0, 0, 0, 0, 1, 0],
			]

			__SCREAMING_SNAKE_CASE  :						str    							=      [0, 0]
			# all coordinates are given in format [y,x]
			__SCREAMING_SNAKE_CASE  :						Dict    							=      [len(grid) - 1, len(grid[0]) - 1]
			__SCREAMING_SNAKE_CASE  :						int    							=      1

			# the cost map which pushes the path closer to the goal
			__SCREAMING_SNAKE_CASE  :						List[Any]    							=      [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
			for i in range(len(grid)):
						for j in range(len(grid[0])):
									__SCREAMING_SNAKE_CASE  :						Union[str, Any]    							=      abs(i - goal[0]) + abs(j - goal[1])
									if grid[i][j] == 1:
												# added extra penalty in the heuristic map
												__SCREAMING_SNAKE_CASE  :						List[str]    							=      9_9

			__SCREAMING_SNAKE_CASE							,					__SCREAMING_SNAKE_CASE  :						List[Any]    							=      search(grid, init, goal, cost, heuristic)

			print("""ACTION MAP""")
			for i in range(len(action)):
						print(action[i])

			for i in range(len(path)):
						print(path[i])





"""simple docstring"""
from __future__ import annotations

import matplotlib.pyplot as plt  # type: ignore
import numpy

# initial triangle of Koch snowflake
__SCREAMING_SNAKE_CASE  :						List[str]    							=      numpy.array([0, 0])
__SCREAMING_SNAKE_CASE  :						Optional[Any]    							=      numpy.array([0.5, 0.866_0254])
__SCREAMING_SNAKE_CASE  :						Tuple    							=      numpy.array([1, 0])
__SCREAMING_SNAKE_CASE  :						List[Any]    							=      [VECTOR_1, VECTOR_2, VECTOR_3, VECTOR_1]



def        lowerCAmelCase_(   lowercase_     :							list[numpy.ndarray]						,   lowercase_     :							int							)	->       list[numpy.ndarray]:
				_lowerCamelCase        =				initial_vectors
				for _ in range(lowercase_							):
								_lowerCamelCase        =				iteration_step(lowercase_							)
				return vectors



def        lowerCAmelCase_(   lowercase_     :							list[numpy.ndarray]							)	->       list[numpy.ndarray]:
				_lowerCamelCase        =				[]
				for i, start_vector in enumerate(vectors[:-1]							):
								_lowerCamelCase        =				vectors[i + 1]
								new_vectors.append(lowercase_							)
								_lowerCamelCase        =				end_vector - start_vector
								new_vectors.append(start_vector + difference_vector / 3							)
								new_vectors.append(
								    start_vector + difference_vector / 3 + rotate(difference_vector / 3						,   60							)							)
								new_vectors.append(start_vector + difference_vector * 2 / 3							)
				new_vectors.append(vectors[-1]							)
				return new_vectors



def        lowerCAmelCase_(   lowercase_     :							numpy.ndarray						,   lowercase_     :							float							)	->       numpy.ndarray:
				_lowerCamelCase        =				numpy.radians(lowercase_							)
				_lowerCamelCase  ,     _lowerCamelCase        =				numpy.cos(lowercase_							), numpy.sin(lowercase_							)
				_lowerCamelCase        =				numpy.array(((c, -s), (s, c))							)
				return numpy.dot(lowercase_						,   lowercase_							)



def        lowerCAmelCase_(   lowercase_     :							list[numpy.ndarray]							)	->       None:
				_lowerCamelCase        =				plt.gca()
				axes.set_aspect('''equal'''							)

				# matplotlib.pyplot.plot takes a list of all x-coordinates and a list of all
				# y-coordinates as inputs, which are constructed from the vector-list using
				# zip()
				_lowerCamelCase  ,     _lowerCamelCase        =				zip(*lowercase_							)
				plt.plot(lowercase_						,   lowercase_							)
				plt.show()


if __name__ == "__main__":
			import doctest

			doctest.testmod()

			__SCREAMING_SNAKE_CASE  :						str    							=      iterate(INITIAL_VECTORS, 5)
			plot(processed_vectors)
