


from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
SCREAMING_SNAKE_CASE__     					=			0

SCREAMING_SNAKE_CASE__     					=			[
    [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],
]

SCREAMING_SNAKE_CASE__     					=			[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

SCREAMING_SNAKE_CASE__     					=			tuple[int, int]



class 						_UpperCAmelCase      :






		def __init__(						self				:     Optional[Any]   ,  UpperCAmelCase				:     int   ,  UpperCAmelCase				:     int   ,  UpperCAmelCase				:     int   ,  UpperCAmelCase				:     int   ,  UpperCAmelCase				:     int   ,  UpperCAmelCase				:     Node | None   ,  ):
				SCREAMING_SNAKE_CASE_				:Any				     =						pos_x
				SCREAMING_SNAKE_CASE_				:Optional[Any]				     =						pos_y
				SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						(pos_y, pos_x)
				SCREAMING_SNAKE_CASE_				:int				     =						goal_x
				SCREAMING_SNAKE_CASE_				:Dict				     =						goal_y
				SCREAMING_SNAKE_CASE_				:Optional[int]				     =						g_cost
				SCREAMING_SNAKE_CASE_				:List[str]				     =						parent
				SCREAMING_SNAKE_CASE_				:List[Any]				     =						self.calculate_heuristic()
				SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						self.g_cost + self.h_cost






		def _snake_case		(						self				:     Optional[Any]):
				SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						self.pos_x - self.goal_x
				SCREAMING_SNAKE_CASE_				:str				     =						self.pos_y - self.goal_y
				if HEURISTIC == 1:
						return abs(UpperCAmelCase) + abs(UpperCAmelCase)
				else:
						return sqrt(dy**2 + dx**2)







		def __lt__(						self				:     List[str]   ,  UpperCAmelCase				:     Node):
				return self.f_cost < other.f_cost




class 						_UpperCAmelCase      :






		def __init__(						self				:     Tuple   ,  UpperCAmelCase				:     TPosition   ,  UpperCAmelCase				:     TPosition):
				SCREAMING_SNAKE_CASE_				:int				     =						Node(start[1]   ,  start[0]   ,  goal[1]   ,  goal[0]   ,  0   ,  UpperCAmelCase)
				SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						Node(goal[1]   ,  goal[0]   ,  goal[1]   ,  goal[0]   ,  9_99_99   ,  UpperCAmelCase)

				SCREAMING_SNAKE_CASE_				:Tuple				     =						[self.start]
				SCREAMING_SNAKE_CASE_				:list[Node]				     =						[]

				SCREAMING_SNAKE_CASE_				:Optional[Any]				     =						False






		def _snake_case		(						self				:     List[Any]):
				while self.open_nodes:
						# Open Nodes are sorted using __lt__
						self.open_nodes.sort()
						SCREAMING_SNAKE_CASE_				:str				     =						self.open_nodes.pop(0)

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

						self.closed_nodes.append(UpperCAmelCase)
						SCREAMING_SNAKE_CASE_				:Dict				     =						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
										SCREAMING_SNAKE_CASE_				:List[Any]				     =						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)

				return [self.start.pos]






		def _snake_case		(						self				:     str   ,  UpperCAmelCase				:     Node):
				SCREAMING_SNAKE_CASE_				:Dict				     =						[]
				for action in delta:
						SCREAMING_SNAKE_CASE_				:List[Any]				     =						parent.pos_x + action[1]
						SCREAMING_SNAKE_CASE_				:List[str]				     =						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 _snake_case		(						self				:     Optional[Any]   ,  UpperCAmelCase				:     Node | None):
				SCREAMING_SNAKE_CASE_				:List[str]				     =						node
				SCREAMING_SNAKE_CASE_				:Dict				     =						[]
				while current_node is not None:
						path.append((current_node.pos_y, current_node.pos_x))
						SCREAMING_SNAKE_CASE_				:int				     =						current_node.parent
				path.reverse()
				return path




class 						_UpperCAmelCase      :






		def __init__(						self				:     Dict   ,  UpperCAmelCase				:     TPosition   ,  UpperCAmelCase				:     TPosition):
				SCREAMING_SNAKE_CASE_				:List[Any]				     =						AStar(UpperCAmelCase   ,  UpperCAmelCase)
				SCREAMING_SNAKE_CASE_				:Tuple				     =						AStar(UpperCAmelCase   ,  UpperCAmelCase)
				SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						False






		def _snake_case		(						self				:     int):
				while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
						self.fwd_astar.open_nodes.sort()
						self.bwd_astar.open_nodes.sort()
						SCREAMING_SNAKE_CASE_				:List[str]				     =						self.fwd_astar.open_nodes.pop(0)
						SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						self.bwd_astar.open_nodes.pop(0)

						if current_bwd_node.pos == current_fwd_node.pos:
								return self.retrace_bidirectional_path(
								    UpperCAmelCase   ,  UpperCAmelCase)

						self.fwd_astar.closed_nodes.append(UpperCAmelCase)
						self.bwd_astar.closed_nodes.append(UpperCAmelCase)

						SCREAMING_SNAKE_CASE_				:List[Any]				     =						current_bwd_node
						SCREAMING_SNAKE_CASE_				:Optional[Any]				     =						current_fwd_node

						SCREAMING_SNAKE_CASE_				:Dict				     =						{
						    self.fwd_astar: self.fwd_astar.get_successors(UpperCAmelCase),
						    self.bwd_astar: self.bwd_astar.get_successors(UpperCAmelCase),
						}

						for astar in [self.fwd_astar, self.bwd_astar]:
								for child_node in successors[astar]:
										if child_node in astar.closed_nodes:
												continue

										if child_node not in astar.open_nodes:
												astar.open_nodes.append(UpperCAmelCase)
										else:
												# retrieve the best current path
												SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						astar.open_nodes.pop(
												    astar.open_nodes.index(UpperCAmelCase))

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

				return [self.fwd_astar.start.pos]







		def _snake_case		(						self				:     Union[str, Any]   ,  UpperCAmelCase				:     Node   ,  UpperCAmelCase				:     Node):
				SCREAMING_SNAKE_CASE_				:int				     =						self.fwd_astar.retrace_path(UpperCAmelCase)
				SCREAMING_SNAKE_CASE_				:Optional[Any]				     =						self.bwd_astar.retrace_path(UpperCAmelCase)
				bwd_path.pop()
				bwd_path.reverse()
				SCREAMING_SNAKE_CASE_				:List[Any]				     =						fwd_path + bwd_path
				return path


if __name__ == "__main__":
		# all coordinates are given in format [y,x]
		SCREAMING_SNAKE_CASE__     					=			(0, 0)
		SCREAMING_SNAKE_CASE__     					=			(len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

		SCREAMING_SNAKE_CASE__     					=			time.time()
		SCREAMING_SNAKE_CASE__     					=			AStar(init, goal)
		SCREAMING_SNAKE_CASE__     					=			a_star.search()
		SCREAMING_SNAKE_CASE__     					=			time.time() - start_time
		print(F'''AStar execution time = {end_time:f} seconds''')

		SCREAMING_SNAKE_CASE__     					=			time.time()
		SCREAMING_SNAKE_CASE__     					=			BidirectionalAStar(init, goal)
		SCREAMING_SNAKE_CASE__     					=			time.time() - bd_start_time
		print(F'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')










import qiskit


def     lowercase	(    a     , a ):



		'''simple docstring'''




		SCREAMING_SNAKE_CASE_				:int				     =						qiskit.Aer.get_backend("aer_simulator" )

		# Create a Quantum Circuit acting on the q register
		SCREAMING_SNAKE_CASE_				:Union[str, Any]				     =						qiskit.QuantumCircuit(a     , a )

		# Apply X (NOT) Gate to Qubits 0 & 1
		circuit.x(0 )
		circuit.x(1 )

		# Map the quantum measurement to the classical bits
		circuit.measure([0, 1]     , [0, 1] )

		# Execute the circuit on the qasm simulator
		SCREAMING_SNAKE_CASE_				:Any				     =						qiskit.execute(a     , a     , shots=1000 )

		# Return the histogram data of the results of the experiment.
		return job.result().get_counts(a )


if __name__ == "__main__":
		SCREAMING_SNAKE_CASE__     					=			single_qubit_measure(2, 2)
		print(F'''Total count for various states are: {counts}''')






