

'''simple docstring'''



from __future__ import annotations

import time

UpperCAmelCase :       Dict			   =     list[tuple[int, int]]

UpperCAmelCase :       List[str]			   =     [
    [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 :       List[str]			   =     [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right







class 						lowerCAmelCase__   :



 """simple docstring"""



 def __init__(		self					:       Optional[Any]					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       Node | None			)  -> int:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      pos_x
      __SCREAMING_SNAKE_CASE     =      pos_y
      __SCREAMING_SNAKE_CASE     =      (pos_y, pos_x)
      __SCREAMING_SNAKE_CASE     =      goal_x
      __SCREAMING_SNAKE_CASE     =      goal_y
      __SCREAMING_SNAKE_CASE     =      parent







class 						lowerCAmelCase__   :



 """simple docstring"""



 def __init__(		self					:       List[Any]					,							__SCREAMING_SNAKE_CASE					:       tuple[int, int]					,							__SCREAMING_SNAKE_CASE					:       tuple[int, int]			)  -> Union[str, Any]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      Node(start[1]					,							start[0]					,							goal[1]					,							goal[0]					,							__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      Node(goal[1]					,							goal[0]					,							goal[1]					,							goal[0]					,							__SCREAMING_SNAKE_CASE			)

      __SCREAMING_SNAKE_CASE     =      [self.start]
      __SCREAMING_SNAKE_CASE     =      False
 def       UpperCAmelCase__		(		self					:       str			)  -> Path | None:


      """simple docstring"""




      while self.node_queue:
           __SCREAMING_SNAKE_CASE     =      self.node_queue.pop(0			)

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

           __SCREAMING_SNAKE_CASE     =      self.get_successors(__SCREAMING_SNAKE_CASE			)

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

      if not self.reached:
           return [self.start.pos]
      return None
 def       UpperCAmelCase__		(		self					:       Dict					,							__SCREAMING_SNAKE_CASE					:       Node			)  -> list[Node]:


      """simple docstring"""




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


 def       UpperCAmelCase__		(		self					:       List[str]					,							__SCREAMING_SNAKE_CASE					:       Node | None			)  -> Path:


      """simple docstring"""




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







class 						lowerCAmelCase__   :



 """simple docstring"""



 def __init__(		self					:       List[Any]					,							__SCREAMING_SNAKE_CASE					:       Dict					,							__SCREAMING_SNAKE_CASE					:       Optional[Any]			)  -> Optional[int]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      BreadthFirstSearch(__SCREAMING_SNAKE_CASE					,							__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      BreadthFirstSearch(__SCREAMING_SNAKE_CASE					,							__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      False
 def       UpperCAmelCase__		(		self					:       List[str]			)  -> Path | None:


      """simple docstring"""




      while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
           __SCREAMING_SNAKE_CASE     =      self.fwd_bfs.node_queue.pop(0			)
           __SCREAMING_SNAKE_CASE     =      self.bwd_bfs.node_queue.pop(0			)

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

           __SCREAMING_SNAKE_CASE     =      current_bwd_node
           __SCREAMING_SNAKE_CASE     =      current_fwd_node

           __SCREAMING_SNAKE_CASE     =      {
               self.fwd_bfs: self.fwd_bfs.get_successors(__SCREAMING_SNAKE_CASE			),
               self.bwd_bfs: self.bwd_bfs.get_successors(__SCREAMING_SNAKE_CASE			),
           }

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

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


 def       UpperCAmelCase__		(		self					:       Dict					,							__SCREAMING_SNAKE_CASE					:       Node					,							__SCREAMING_SNAKE_CASE					:       Node			)  -> Path:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      self.fwd_bfs.retrace_path(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      self.bwd_bfs.retrace_path(__SCREAMING_SNAKE_CASE			)
      bwd_path.pop()
      bwd_path.reverse()
      __SCREAMING_SNAKE_CASE     =      fwd_path + bwd_path
      return path


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

  doctest.testmod()
  UpperCAmelCase :       List[str]			   =     (0, 0)
  UpperCAmelCase :       Optional[Any]			   =     (len(grid) - 1, len(grid[0]) - 1)
  for elem in grid:
    print(elem)

  UpperCAmelCase :       Union[str, Any]			   =     time.time()
  UpperCAmelCase :       int			   =     BreadthFirstSearch(init, goal)
  UpperCAmelCase :       int			   =     bfs.search()
  UpperCAmelCase :       Optional[Any]			   =     time.time() - start_bfs_time

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

  UpperCAmelCase :       Tuple			   =     time.time()
  UpperCAmelCase :       List[Any]			   =     BidirectionalBreadthFirstSearch(init, goal)
  UpperCAmelCase :       str			   =     bd_bfs.search()
  UpperCAmelCase :       Any			   =     time.time() - start_bd_bfs_time

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









'''simple docstring'''



class 						lowerCAmelCase__   :



 """simple docstring"""



 def __init__(		self					:       List[Any]					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       Union[str, Any]					,							__SCREAMING_SNAKE_CASE					:       Any			)  -> Tuple:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      name
      __SCREAMING_SNAKE_CASE     =      value
      __SCREAMING_SNAKE_CASE     =      weight
 def __repr__(		self					:       str			)  -> Union[str, Any]:


      """simple docstring"""




      return f'{self.__class__.__name__}({self.name}, {self.value}, {self.weight})'
 def       UpperCAmelCase__		(		self					:       List[Any]			)  -> List[Any]:


      """simple docstring"""




      return self.value
 def       UpperCAmelCase__		(		self					:       Any			)  -> str:


      """simple docstring"""




      return self.name
 def       UpperCAmelCase__		(		self					:       Union[str, Any]			)  -> Union[str, Any]:


      """simple docstring"""




      return self.weight


 def       UpperCAmelCase__		(		self					:       int			)  -> Tuple:


      """simple docstring"""




      return self.value / self.weight







def    a__       (  a__      ,    a__      ,    a__						):




     """simple docstring"""


     __SCREAMING_SNAKE_CASE     =      []
     for i in range(len(a__						)						):
          menu.append(Things(name[i]      ,    value[i]      ,    weight[i]						)						)
     return menu







def    a__       (  a__      ,    a__      ,    a__						):




     """simple docstring"""


     __SCREAMING_SNAKE_CASE     =      sorted(a__      ,    key=a__      ,    reverse=a__						)
     __SCREAMING_SNAKE_CASE     =      []
     __SCREAMING_SNAKE_CASE   ,			__SCREAMING_SNAKE_CASE     =      0.0, 0.0
     for i in range(len(a__						)						):
          if (total_cost + items_copy[i].get_weight()) <= max_cost:
               result.append(items_copy[i]						)
               total_cost += items_copy[i].get_weight()
               total_value += items_copy[i].get_value()
     return (result, total_value)







def    a__       (  ):




     """simple docstring"""




if __name__ == "__main__":
  import doctest

  doctest.testmod()






