




from __future__ import annotations

import time

a    				=      list[tuple[int, int]]

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

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




class    _A					:






		def __init__(     self    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE      ):
								_UpperCAmelCase	     =      pos_x
								_UpperCAmelCase	     =      pos_y
								_UpperCAmelCase	     =      (pos_y, pos_x)
								_UpperCAmelCase	     =      goal_x
								_UpperCAmelCase	     =      goal_y
								_UpperCAmelCase	     =      parent




class    _A					:






		def __init__(     self    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE      ):
								_UpperCAmelCase	     =      Node(start[1]    ,		start[0]    ,		goal[1]    ,		goal[0]    ,		__SCREAMING_SNAKE_CASE      )
								_UpperCAmelCase	     =      Node(goal[1]    ,		goal[0]    ,		goal[1]    ,		goal[0]    ,		__SCREAMING_SNAKE_CASE      )

								_UpperCAmelCase	     =      [self.start]
								_UpperCAmelCase	     =      False






		def 					UpperCAmelCase			(     self      ):







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

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

														_UpperCAmelCase	     =      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    ,		_SCREAMING_SNAKE_CASE      ):
								_UpperCAmelCase	     =      []
								for action in delta:
														_UpperCAmelCase	     =      parent.pos_x + action[1]
														_UpperCAmelCase	     =      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    ,		_SCREAMING_SNAKE_CASE      ):
								_UpperCAmelCase	     =      node
								_UpperCAmelCase	     =      []
								while current_node is not None:
														path.append((current_node.pos_y, current_node.pos_x)      )
														_UpperCAmelCase	     =      current_node.parent
								path.reverse()
								return path




class    _A					:






		def __init__(     self    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE      ):
								_UpperCAmelCase	     =      BreadthFirstSearch(__SCREAMING_SNAKE_CASE    ,		__SCREAMING_SNAKE_CASE      )
								_UpperCAmelCase	     =      BreadthFirstSearch(__SCREAMING_SNAKE_CASE    ,		__SCREAMING_SNAKE_CASE      )
								_UpperCAmelCase	     =      False






		def 					UpperCAmelCase			(     self      ):







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

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

														_UpperCAmelCase	     =      current_bwd_node
														_UpperCAmelCase	     =      current_fwd_node

														_UpperCAmelCase	     =      {
														    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    ,		_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE      ):
								_UpperCAmelCase	     =      self.fwd_bfs.retrace_path(__SCREAMING_SNAKE_CASE      )
								_UpperCAmelCase	     =      self.bwd_bfs.retrace_path(__SCREAMING_SNAKE_CASE      )
								bwd_path.pop()
								bwd_path.reverse()
								_UpperCAmelCase	     =      fwd_path + bwd_path
								return path


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

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

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

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

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

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

def 				SCREAMING_SNAKE_CASE_   (      UpperCamelCase__			,		UpperCamelCase__		):

      def get_matched_characters(UpperCamelCase__			,		UpperCamelCase__		) -> str:
            UpperCamelCase__     : Union[str, Any]											=					[]
            UpperCamelCase__     : Union[str, Any]											=					min(len(_stra		)			,		len(_stra		)		) // 2
            for i, l in enumerate(_stra		):
                  UpperCamelCase__     : Optional[int]											=					int(max(0			,		i - limit		)		)
                  UpperCamelCase__     : List[str]											=					int(min(i + limit + 1			,		len(_stra		)		)		)
                  if l in _stra[left:right]:
                        matched.append(UpperCamelCase__		)
                        UpperCamelCase__     : List[str]											=					f'''{_stra[0:_stra.index(UpperCamelCase__		)]} {_stra[_stra.index(UpperCamelCase__		) + 1:]}'''

            return "".join(UpperCamelCase__		)

      # matching characters
      UpperCamelCase__     : Any											=					get_matched_characters(UpperCamelCase__			,		UpperCamelCase__		)
      UpperCamelCase__     : Union[str, Any]											=					get_matched_characters(UpperCamelCase__			,		UpperCamelCase__		)
      UpperCamelCase__     : List[Any]											=					len(UpperCamelCase__		)

      # transposition
      UpperCamelCase__     : str											=					(
          len([(ca, ca) for ca, ca in zip(UpperCamelCase__			,		UpperCamelCase__		) if ca != ca]		) // 2
      )

      if not match_count:
            UpperCamelCase__     : Union[str, Any]											=					0.0
      else:
            UpperCamelCase__     : Optional[int]											=					(
                1
                / 3
                * (
                    match_count / len(UpperCamelCase__		)
                    + match_count / len(UpperCamelCase__		)
                    + (match_count - transpositions) / match_count
                )
            )

      # common prefix up to 4 characters
      UpperCamelCase__     : Dict											=					0
      for ca, ca in zip(stra[:4]			,		stra[:4]		):
            if ca == ca:
                  prefix_len += 1
            else:
                  break

      return jaro + 0.1 * prefix_len * (1 - jaro)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(jaro_winkler("hello", "world"))


