from __future__ import annotations

lowerCamelCase_    :		Optional[Any]							=	list[tuple[int, int]]

lowerCamelCase_    :		int							=	[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

lowerCamelCase_    :		str							=	([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right


class 						a__							:



	def __init__(						self				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						)			->   Optional[Any]:
						__a		 =       pos_x
						__a		 =       pos_y
						__a		 =       (pos_y, pos_x)
						__a		 =       goal_x
						__a		 =       goal_y
						__a		 =       g_cost
						__a		 =       parent
						__a		 =       self.calculate_heuristic()



	def __SCREAMING_SNAKE_CASE							(						self   )			->   float:
						__a		 =       abs(self.pos_x - self.goal_x   )
						__a		 =       abs(self.pos_y - self.goal_y   )
						return dx + dy







	def __lt__(						self				,						UpperCAmelCase   )			->   bool:
						return self.f_cost < other.f_cost






class 						a__							:



	def __init__(						self				,						UpperCAmelCase				,						UpperCAmelCase   )			->   Dict:
						__a		 =       Node(start[1]				,						start[0]				,						goal[1]				,						goal[0]				,						0				,						UpperCAmelCase   )
						__a		 =       Node(goal[1]				,						goal[0]				,						goal[1]				,						goal[0]				,						9_9_9_9_9				,						UpperCAmelCase   )

						__a		 =       [self.start]
						__a		 =       []

						__a		 =       False



	def __SCREAMING_SNAKE_CASE							(						self   )			->   Path | None:
						while self.open_nodes:
											# Open Nodes are sorted using __lt__
											self.open_nodes.sort()
											__a		 =       self.open_nodes.pop(0   )

											if current_node.pos == self.target.pos:
																__a		 =       True
																return self.retrace_path(UpperCAmelCase   )

											self.closed_nodes.append(UpperCAmelCase   )
											__a		 =       self.get_successors(UpperCAmelCase   )

											for child_node in successors:
																if child_node in self.closed_nodes:
																					continue

																if child_node not in self.open_nodes:
																					self.open_nodes.append(UpperCAmelCase   )
																else:
																					# retrieve the best current path
																					__a		 =       self.open_nodes.pop(self.open_nodes.index(UpperCAmelCase   )   )

																					if child_node.g_cost < better_node.g_cost:
																										self.open_nodes.append(UpperCAmelCase   )
																					else:
																										self.open_nodes.append(UpperCAmelCase   )

						if not self.reached:
											return [self.start.pos]
						return None



	def __SCREAMING_SNAKE_CASE							(						self				,						UpperCAmelCase   )			->   list[Node]:
						__a		 =       []
						for action in delta:
											__a		 =       parent.pos_x + action[1]
											__a		 =       parent.pos_y + action[0]

											if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(UpperCAmelCase   ) - 1):
																continue

											if grid[pos_y][pos_x] != 0:
																continue

											successors.append(
											    Node(
											        UpperCAmelCase				,						UpperCAmelCase				,						self.target.pos_y				,						self.target.pos_x				,						parent.g_cost + 1				,						UpperCAmelCase				,						)   )
						return successors







	def __SCREAMING_SNAKE_CASE							(						self				,						UpperCAmelCase   )			->   Path:
						__a		 =       node
						__a		 =       []
						while current_node is not None:
											path.append((current_node.pos_y, current_node.pos_x)   )
											__a		 =       current_node.parent
						path.reverse()
						return path


if __name__ == "__main__":
	lowerCamelCase_    :		Any							=	(0, 0)
	lowerCamelCase_    :		Tuple							=	(len(grid) - 1, len(grid[0]) - 1)
	for elem in grid:
		print(elem)

	print("""------""")

	lowerCamelCase_    :		Optional[int]							=	GreedyBestFirst(init, goal)
	lowerCamelCase_    :		List[Any]							=	greedy_bf.search()
	if path:
		for pos_x, pos_y in path:
			lowerCamelCase_    :		str							=	2

		for elem in grid:
			print(elem)





def 							lowerCAmelCase(     __lowerCamelCase						):
					if not all(char in '01' for char in bin_string						):
										raise ValueError('Non-binary value was passed to the function'						)
					if not bin_string:
										raise ValueError('Empty string was passed to the function'						)
					__a		 =       ''
					while len(__lowerCamelCase						) % 3 != 0:
										__a		 =       '0' + bin_string
					__a		 =       [
					    bin_string[index : index + 3]
					    for index in range(len(__lowerCamelCase						)						)
					    if index % 3 == 0
					]
					for bin_group in bin_string_in_3_list:
										__a		 =       0
										for index, val in enumerate(__lowerCamelCase						):
															oct_val += int(2 ** (2 - index) * int(__lowerCamelCase						)						)
										oct_string += str(__lowerCamelCase						)
					return oct_string


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

	testmod()




