
"""simple docstring"""







from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
lowerCamelCase__        =		0

lowerCamelCase__        =		[
    [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__        =		[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

lowerCamelCase__        =		tuple[int, int]




class 			A__	:

		def __init__(				self	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE	,		):
			__lowerCAmelCase      :						str						      =				pos_x
			__lowerCAmelCase      :						List[str]						      =				pos_y
			__lowerCAmelCase      :						Optional[int]						      =				(pos_y, pos_x)
			__lowerCAmelCase      :						List[Any]						      =				goal_x
			__lowerCAmelCase      :						Optional[Any]						      =				goal_y
			__lowerCAmelCase      :						Optional[int]						      =				g_cost
			__lowerCAmelCase      :						List[str]						      =				parent
			__lowerCAmelCase      :						Optional[Any]						      =				self.calculate_heuristic()
			__lowerCAmelCase      :						Optional[int]						      =				self.g_cost + self.h_cost

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







		def __lt__(				self	,		_SCREAMING_SNAKE_CASE			):
			return self.f_cost < other.f_cost




class 			A__	:

		def __init__(				self	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE			):
			__lowerCAmelCase      :						Optional[int]						      =				Node(start[1]	,		start[0]	,		goal[1]	,		goal[0]	,		0	,		_SCREAMING_SNAKE_CASE			)
			__lowerCAmelCase      :						Tuple						      =				Node(goal[1]	,		goal[0]	,		goal[1]	,		goal[0]	,		9_99_99	,		_SCREAMING_SNAKE_CASE			)

			__lowerCAmelCase      :						Dict						      =				[self.start]
			__lowerCAmelCase      :						list[Node]						      =				[]

			__lowerCAmelCase      :						int						      =				False

		def 							__lowerCamelCase							(				self			):
			while self.open_nodes:
				# Open Nodes are sorted using __lt__
				self.open_nodes.sort()
				__lowerCAmelCase      :						Dict						      =				self.open_nodes.pop(0			)

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

				self.closed_nodes.append(_SCREAMING_SNAKE_CASE			)
				__lowerCAmelCase      :						Union[str, Any]						      =				self.get_successors(_SCREAMING_SNAKE_CASE			)

				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(_SCREAMING_SNAKE_CASE			)
					else:
						# retrieve the best current path
						__lowerCAmelCase      :						Optional[Any]						      =				self.open_nodes.pop(self.open_nodes.index(_SCREAMING_SNAKE_CASE			)			)

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

			return [self.start.pos]

		def 							__lowerCamelCase							(				self	,		_SCREAMING_SNAKE_CASE			):
			__lowerCAmelCase      :						int						      =				[]
			for action in delta:
				__lowerCAmelCase      :						int						      =				parent.pos_x + action[1]
				__lowerCAmelCase      :						Any						      =				parent.pos_y + action[0]
				if not (0 <= pos_x <= len(grid[0]			) - 1 and 0 <= pos_y <= len(_SCREAMING_SNAKE_CASE			) - 1):
					continue

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

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







		def 							__lowerCamelCase							(				self	,		_SCREAMING_SNAKE_CASE			):
			__lowerCAmelCase      :						Union[str, Any]						      =				node
			__lowerCAmelCase      :						int						      =				[]
			while current_node is not None:
				path.append((current_node.pos_y, current_node.pos_x)			)
				__lowerCAmelCase      :						Dict						      =				current_node.parent
			path.reverse()
			return path




class 			A__	:

		def __init__(				self	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE			):
			__lowerCAmelCase      :						Optional[int]						      =				AStar(_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE			)
			__lowerCAmelCase      :						Tuple						      =				AStar(_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE			)
			__lowerCAmelCase      :						Optional[Any]						      =				False

		def 							__lowerCamelCase							(				self			):
			while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
				self.fwd_astar.open_nodes.sort()
				self.bwd_astar.open_nodes.sort()
				__lowerCAmelCase      :						Dict						      =				self.fwd_astar.open_nodes.pop(0			)
				__lowerCAmelCase      :						Dict						      =				self.bwd_astar.open_nodes.pop(0			)

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

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

				__lowerCAmelCase      :						int						      =				current_bwd_node
				__lowerCAmelCase      :						Dict						      =				current_fwd_node

				__lowerCAmelCase      :						List[str]						      =				{
				    self.fwd_astar: self.fwd_astar.get_successors(_SCREAMING_SNAKE_CASE			),
				    self.bwd_astar: self.bwd_astar.get_successors(_SCREAMING_SNAKE_CASE			),
				}

				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(_SCREAMING_SNAKE_CASE			)
						else:
							# retrieve the best current path
							__lowerCAmelCase      :						Optional[int]						      =				astar.open_nodes.pop(
							    astar.open_nodes.index(_SCREAMING_SNAKE_CASE			)			)

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

			return [self.fwd_astar.start.pos]







		def 							__lowerCamelCase							(				self	,		_SCREAMING_SNAKE_CASE	,		_SCREAMING_SNAKE_CASE			):
			__lowerCAmelCase      :						int						      =				self.fwd_astar.retrace_path(_SCREAMING_SNAKE_CASE			)
			__lowerCAmelCase      :						Tuple						      =				self.bwd_astar.retrace_path(_SCREAMING_SNAKE_CASE			)
			bwd_path.pop()
			bwd_path.reverse()
			__lowerCAmelCase      :						int						      =				fwd_path + bwd_path
			return path


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

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

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

"""simple docstring"""







import qiskit
def    __lowerCAmelCase    (_UpperCamelCase	,  _UpperCamelCase		):
	__lowerCAmelCase      :						Union[str, Any]						      =				qiskit.Aer.get_backend('aer_simulator'		)

	# Create a Quantum Circuit acting on the q register
	__lowerCAmelCase      :						str						      =				qiskit.QuantumCircuit(_UpperCamelCase	,  _UpperCamelCase		)

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

	# Execute the circuit on the simulator
	__lowerCAmelCase      :						Optional[int]						      =				qiskit.execute(_UpperCamelCase	,  _UpperCamelCase	,  shots=1000		)

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


if __name__ == "__main__":
							print(f'Total count for various states are: {single_qubit_measure(1, 1)}')