

"""simple docstring"""






from __future__ import annotations

import time

snake_case_ : List[Any]   =							list[tuple[int, int]]

snake_case_ : 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],
]

snake_case_ : int   =							[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right







class    snake_case__	:







			def __init__(      self      :			Optional[int]      ,	lowercase      :			int      ,	lowercase      :			int      ,	lowercase      :			int      ,	lowercase      :			int      ,	lowercase      :			Node | None	):





								'''simple docstring'''



								UpperCAmelCase      : Dict   =					pos_x
								UpperCAmelCase      : Dict   =					pos_y
								UpperCAmelCase      : Tuple   =					(pos_y, pos_x)
								UpperCAmelCase      : Dict   =					goal_x
								UpperCAmelCase      : Optional[Any]   =					goal_y
								UpperCAmelCase      : str   =					parent







class    snake_case__	:







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





								'''simple docstring'''



								UpperCAmelCase      : int   =					Node(start[1]      ,	start[0]      ,	goal[1]      ,	goal[0]      ,	_lowercase	)
								UpperCAmelCase      : Optional[Any]   =					Node(goal[1]      ,	goal[0]      ,	goal[1]      ,	goal[0]      ,	_lowercase	)

								UpperCAmelCase      : Dict   =					[self.start]
								UpperCAmelCase      : Optional[int]   =					False







			def       __lowerCAmelCase					(      self      :			int	):





								'''simple docstring'''



								while self.node_queue:
													UpperCAmelCase      : Dict   =					self.node_queue.pop(0	)

													if current_node.pos == self.target.pos:
																		UpperCAmelCase      : Dict   =					True
																		return self.retrace_path(_lowercase	)

													UpperCAmelCase      : Optional[Any]   =					self.get_successors(_lowercase	)

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

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







			def       __lowerCAmelCase					(      self      :			List[Any]      ,	lowercase      :			Node	):





								'''simple docstring'''



								UpperCAmelCase      : Union[str, Any]   =					[]
								for action in delta:
													UpperCAmelCase      : Dict   =					parent.pos_x + action[1]
													UpperCAmelCase      : List[Any]   =					parent.pos_y + action[0]
													if not (0 <= pos_x <= len(grid[0]	) - 1 and 0 <= pos_y <= len(_lowercase	) - 1):
																		continue

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

													successors.append(
													    Node(_lowercase      ,	_lowercase      ,	self.target.pos_y      ,	self.target.pos_x      ,	_lowercase	)	)
								return successors







			def       __lowerCAmelCase					(      self      :			Optional[int]      ,	lowercase      :			Node | None	):





								'''simple docstring'''



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







class    snake_case__	:







			def __init__(      self      :			Optional[Any]      ,	lowercase      :			Tuple      ,	lowercase      :			List[str]	):





								'''simple docstring'''



								UpperCAmelCase      : Any   =					BreadthFirstSearch(_lowercase      ,	_lowercase	)
								UpperCAmelCase      : Any   =					BreadthFirstSearch(_lowercase      ,	_lowercase	)
								UpperCAmelCase      : List[str]   =					False







			def       __lowerCAmelCase					(      self      :			Dict	):





								'''simple docstring'''



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

													if current_bwd_node.pos == current_fwd_node.pos:
																		UpperCAmelCase      : str   =					True
																		return self.retrace_bidirectional_path(
																		    _lowercase      ,	_lowercase	)

													UpperCAmelCase      : Dict   =					current_bwd_node
													UpperCAmelCase      : Optional[int]   =					current_fwd_node

													UpperCAmelCase      : Union[str, Any]   =					{
													    self.fwd_bfs: self.fwd_bfs.get_successors(_lowercase	),
													    self.bwd_bfs: self.bwd_bfs.get_successors(_lowercase	),
													}

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

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







			def       __lowerCAmelCase					(      self      :			str      ,	lowercase      :			Node      ,	lowercase      :			Node	):





								'''simple docstring'''



								UpperCAmelCase      : Any   =					self.fwd_bfs.retrace_path(_lowercase	)
								UpperCAmelCase      : Any   =					self.bwd_bfs.retrace_path(_lowercase	)
								bwd_path.pop()
								bwd_path.reverse()
								UpperCAmelCase      : List[Any]   =					fwd_path + bwd_path
								return path


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

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

	snake_case_ : List[Any]   =							time.time()
	snake_case_ : List[Any]   =							BreadthFirstSearch(init, goal)
	snake_case_ : List[str]   =							bfs.search()
	snake_case_ : Optional[Any]   =							time.time() - start_bfs_time

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

	snake_case_ : int   =							time.time()
	snake_case_ : int   =							BidirectionalBreadthFirstSearch(init, goal)
	snake_case_ : Any   =							bd_bfs.search()
	snake_case_ : Dict   =							time.time() - start_bd_bfs_time

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



# coding=utf-8
# Copyright 2023 The HuggingFace Inc. team.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# this script dumps information about the environment

import os
import platform
import sys


UpperCAmelCase_           =				'''3'''

print('''Python version:''', sys.version)

print('''OS platform:''', platform.platform())
print('''OS architecture:''', platform.machine())

try:
  import torch

  print('''Torch version:''', torch.__version__)
  print('''Cuda available:''', torch.cuda.is_available())
  print('''Cuda version:''', torch.version.cuda)
  print('''CuDNN version:''', torch.backends.cudnn.version())
  print('''Number of GPUs available:''', torch.cuda.device_count())
except ImportError:
  print('''Torch version:''', None)

try:
  import transformers

  print('''transformers version:''', transformers.__version__)
except ImportError:
  print('''transformers version:''', None)