





"""simple docstring"""






from __future__ import annotations

import time

lowerCAmelCase__      =    list[tuple[int, int]]

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






class 	__snake_case	:




  def __init__(			self					:						str						, __lowerCAmelCase					:						int						, __lowerCAmelCase					:						int						, __lowerCAmelCase					:						int						, __lowerCAmelCase					:						int						, __lowerCAmelCase					:						Node | None		):






         """simple docstring"""






         _lowerCamelCase						:    Optional[Any]         =			pos_x
         _lowerCamelCase						:    List[Any]         =			pos_y
         _lowerCamelCase						:    Dict         =			(pos_y, pos_x)
         _lowerCamelCase						:    Any         =			goal_x
         _lowerCamelCase						:    List[Any]         =			goal_y
         _lowerCamelCase						:    Optional[int]         =			parent






class 	__snake_case	:




  def __init__(			self					:						str						, __lowerCAmelCase					:						tuple[int, int]						, __lowerCAmelCase					:						tuple[int, int]		):






         """simple docstring"""






         _lowerCamelCase						:    str         =			Node(start[1]						, start[0]						, goal[1]						, goal[0]						, UpperCamelCase_		)
         _lowerCamelCase						:    Any         =			Node(goal[1]						, goal[0]						, goal[1]						, goal[0]						, UpperCamelCase_		)

         _lowerCamelCase						:    Union[str, Any]         =			[self.start]
         _lowerCamelCase						:    str         =			False




  def 						SCREAMING_SNAKE_CASE    (			self					:						Any		):






         """simple docstring"""






         while self.node_queue:
                _lowerCamelCase						:    Tuple         =			self.node_queue.pop(0		)

                if current_node.pos == self.target.pos:
                       _lowerCamelCase						:    Tuple         =			True
                       return self.retrace_path(UpperCamelCase_		)

                _lowerCamelCase						:    Dict         =			self.get_successors(UpperCamelCase_		)

                for node in successors:
                       self.node_queue.append(UpperCamelCase_		)

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




  def 						SCREAMING_SNAKE_CASE    (			self					:						Dict						, __lowerCAmelCase					:						Node		):






         """simple docstring"""






         _lowerCamelCase						:    Any         =			[]
         for action in delta:
                _lowerCamelCase						:    int         =			parent.pos_x + action[1]
                _lowerCamelCase						:    Tuple         =			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						, UpperCamelCase_		)		)
         return successors




  def 						SCREAMING_SNAKE_CASE    (			self					:						Optional[Any]						, __lowerCAmelCase					:						Node | None		):






         """simple docstring"""






         _lowerCamelCase						:    List[Any]         =			node
         _lowerCamelCase						:    str         =			[]
         while current_node is not None:
                path.append((current_node.pos_y, current_node.pos_x)		)
                _lowerCamelCase						:    List[str]         =			current_node.parent
         path.reverse()
         return path






class 	__snake_case	:




  def __init__(			self					:						Union[str, Any]						, __lowerCAmelCase					:						Dict						, __lowerCAmelCase					:						Any		):






         """simple docstring"""






         _lowerCamelCase						:    str         =			BreadthFirstSearch(UpperCamelCase_						, UpperCamelCase_		)
         _lowerCamelCase						:    Dict         =			BreadthFirstSearch(UpperCamelCase_						, UpperCamelCase_		)
         _lowerCamelCase						:    Optional[Any]         =			False




  def 						SCREAMING_SNAKE_CASE    (			self					:						Any		):






         """simple docstring"""






         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
                _lowerCamelCase						:    Dict         =			self.fwd_bfs.node_queue.pop(0		)
                _lowerCamelCase						:    Optional[int]         =			self.bwd_bfs.node_queue.pop(0		)

                if current_bwd_node.pos == current_fwd_node.pos:
                       _lowerCamelCase						:    str         =			True
                       return self.retrace_bidirectional_path(
                           UpperCamelCase_						, UpperCamelCase_		)

                _lowerCamelCase						:    int         =			current_bwd_node
                _lowerCamelCase						:    Union[str, Any]         =			current_fwd_node

                _lowerCamelCase						:    Any         =			{
                    self.fwd_bfs: self.fwd_bfs.get_successors(UpperCamelCase_		),
                    self.bwd_bfs: self.bwd_bfs.get_successors(UpperCamelCase_		),
                }

                for bfs in [self.fwd_bfs, self.bwd_bfs]:
                       for node in successors[bfs]:
                              bfs.node_queue.append(UpperCamelCase_		)

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




  def 						SCREAMING_SNAKE_CASE    (			self					:						int						, __lowerCAmelCase					:						Node						, __lowerCAmelCase					:						Node		):






         """simple docstring"""






         _lowerCamelCase						:    int         =			self.fwd_bfs.retrace_path(UpperCamelCase_		)
         _lowerCamelCase						:    str         =			self.bwd_bfs.retrace_path(UpperCamelCase_		)
         bwd_path.pop()
         bwd_path.reverse()
         _lowerCamelCase						:    List[Any]         =			fwd_path + bwd_path
         return path


if __name__ == "__main__":
   # all coordinates are given in format [y,x]
   import doctest

   doctest.testmod()
   lowerCAmelCase__      =    (0, 0)
   lowerCAmelCase__      =    (len(grid) - 1, len(grid[0]) - 1)
   for elem in grid:
      print(elem)

   lowerCAmelCase__      =    time.time()
   lowerCAmelCase__      =    BreadthFirstSearch(init, goal)
   lowerCAmelCase__      =    bfs.search()
   lowerCAmelCase__      =    time.time() - start_bfs_time

   print('''Unidirectional BFS computation time : ''', bfs_time)

   lowerCAmelCase__      =    time.time()
   lowerCAmelCase__      =    BidirectionalBreadthFirstSearch(init, goal)
   lowerCAmelCase__      =    bd_bfs.search()
   lowerCAmelCase__      =    time.time() - start_bd_bfs_time

   print('''Bidirectional BFS computation time : ''', bd_bfs_time)







"""simple docstring"""






def 	snake_case_  (				A_ :		int						):


       '''simple docstring'''





       return 1 if digit in (0, 1) else (digit * factorial(digit - 1						))






def 	snake_case_  (				A_ :		int						):


       '''simple docstring'''





       _lowerCamelCase						:    str         =			0
       _lowerCamelCase						:    Any         =			number
       while duplicate > 0:
              _lowerCamelCase      ,   _lowerCamelCase						:    Union[str, Any]         =			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.''')
   lowerCAmelCase__      =    int(input('''Enter number: ''').strip())
   print(
       F"""{number} is {"" if krishnamurthy(number) else "not "}a Krishnamurthy Number."""
   )


