


'''simple docstring'''






from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__UpperCAmelCase					       =							0

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

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

__UpperCAmelCase					       =							tuple[int, int]




class 	a__       :





							'''simple docstring'''






							def __init__(	self      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					) ->							None:
														lowerCAmelCase__      =			pos_x
														lowerCAmelCase__      =			pos_y
														lowerCAmelCase__      =			(pos_y, pos_x)
														lowerCAmelCase__      =			goal_x
														lowerCAmelCase__      =			goal_y
														lowerCAmelCase__      =			g_cost
														lowerCAmelCase__      =			parent
														lowerCAmelCase__      =			self.calculate_heuristic()
														lowerCAmelCase__      =			self.g_cost + self.h_cost







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							float:
														lowerCAmelCase__      =			self.pos_x - self.goal_x
														lowerCAmelCase__      =			self.pos_y - self.goal_y
														if HEURISTIC == 1:
																					return abs(lowerCamelCase_     ) + abs(lowerCamelCase_     )
														else:
																					return sqrt(dy**2 + dx**2     )







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




class 	a__       :





							'''simple docstring'''






							def __init__(	self      ,					lowerCamelCase_      ,					lowerCamelCase_     ) ->							Union[str, Any]:
														lowerCAmelCase__      =			Node(start[1]      ,					start[0]      ,					goal[1]      ,					goal[0]      ,					0      ,					lowerCamelCase_     )
														lowerCAmelCase__      =			Node(goal[1]      ,					goal[0]      ,					goal[1]      ,					goal[0]      ,					9_99_99      ,					lowerCamelCase_     )

														lowerCAmelCase__      =			[self.start]
														lowerCAmelCase__      =			[]

														lowerCAmelCase__      =			False







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							list[TPosition]:
														while self.open_nodes:
																					# Open Nodes are sorted using __lt__
																					self.open_nodes.sort()
																					lowerCAmelCase__      =			self.open_nodes.pop(0     )

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

																					self.closed_nodes.append(lowerCamelCase_     )
																					lowerCAmelCase__      =			self.get_successors(lowerCamelCase_     )

																					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(lowerCamelCase_     )
																												else:
																																			# retrieve the best current path
																																			lowerCAmelCase__      =			self.open_nodes.pop(self.open_nodes.index(lowerCamelCase_     )     )

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

														return [self.start.pos]







							def 						__SCREAMING_SNAKE_CASE							(	self      ,					lowerCamelCase_     ) ->							list[Node]:
														lowerCAmelCase__      =			[]
														for action in delta:
																					lowerCAmelCase__      =			parent.pos_x + action[1]
																					lowerCAmelCase__      =			parent.pos_y + action[0]
																					if not (0 <= pos_x <= len(grid[0]     ) - 1 and 0 <= pos_y <= len(lowerCamelCase_     ) - 1):
																												continue

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

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







							def 						__SCREAMING_SNAKE_CASE							(	self      ,					lowerCamelCase_     ) ->							list[TPosition]:
														lowerCAmelCase__      =			node
														lowerCAmelCase__      =			[]
														while current_node is not None:
																					path.append((current_node.pos_y, current_node.pos_x)     )
																					lowerCAmelCase__      =			current_node.parent
														path.reverse()
														return path




class 	a__       :





							'''simple docstring'''






							def __init__(	self      ,					lowerCamelCase_      ,					lowerCamelCase_     ) ->							None:
														lowerCAmelCase__      =			AStar(lowerCamelCase_      ,					lowerCamelCase_     )
														lowerCAmelCase__      =			AStar(lowerCamelCase_      ,					lowerCamelCase_     )
														lowerCAmelCase__      =			False







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							list[TPosition]:
														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__      =			self.fwd_astar.open_nodes.pop(0     )
																					lowerCAmelCase__      =			self.bwd_astar.open_nodes.pop(0     )

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

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

																					lowerCAmelCase__      =			current_bwd_node
																					lowerCAmelCase__      =			current_fwd_node

																					lowerCAmelCase__      =			{
																					    self.fwd_astar: self.fwd_astar.get_successors(lowerCamelCase_     ),
																					    self.bwd_astar: self.bwd_astar.get_successors(lowerCamelCase_     ),
																					}

																					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(lowerCamelCase_     )
																																			else:
																																										# retrieve the best current path
																																										lowerCAmelCase__      =			astar.open_nodes.pop(
																																										    astar.open_nodes.index(lowerCamelCase_     )     )

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

														return [self.fwd_astar.start.pos]







							def 						__SCREAMING_SNAKE_CASE							(	self      ,					lowerCamelCase_      ,					lowerCamelCase_     ) ->							list[TPosition]:
														lowerCAmelCase__      =			self.fwd_astar.retrace_path(lowerCamelCase_     )
														lowerCAmelCase__      =			self.bwd_astar.retrace_path(lowerCamelCase_     )
														bwd_path.pop()
														bwd_path.reverse()
														lowerCAmelCase__      =			fwd_path + bwd_path
														return path


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

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

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



'''simple docstring'''






def       _snake_case     (  A )		->					int:
							return 1 if digit in (0, 1) else (digit * factorial(digit - 1 ))


def       _snake_case     (  A )		->					bool:
							lowerCAmelCase__      =			0
							lowerCAmelCase__      =			number
							while duplicate > 0:
														lowerCAmelCase__     ,      lowerCAmelCase__      =			divmod(A				,					10 )
														fact_sum += factorial(A )
							return fact_sum == number


if __name__ == "__main__":
		print('''Program to check whether a number is a Krisnamurthy Number or not.''')
		__UpperCAmelCase					       =							int(input('''Enter number: ''').strip())
		print(
		    f"""{number} is {'' if krishnamurthy(number) else 'not '}a Krishnamurthy Number."""
		)