






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__ :

       '''simple docstring'''



       def __init__(				self      ,    a__      ,    a__      ,    a__      ,    a__      ,    a__     )			->   Tuple:






            '''simple docstring'''





            __snake_case      :str 							=    pos_x
            __snake_case      :List[Any] 							=    pos_y
            __snake_case      :Any 							=    (pos_y, pos_x)
            __snake_case      :Tuple 							=    goal_x
            __snake_case      :int 							=    goal_y
            __snake_case      :Dict 							=    parent




class       snake_case__ :

       '''simple docstring'''



       def __init__(				self      ,    a__      ,    a__     )			->   str:






            '''simple docstring'''





            __snake_case      :Any 							=    Node(start[1]      ,    start[0]      ,    goal[1]      ,    goal[0]      ,    a__     )
            __snake_case      :int 							=    Node(goal[1]      ,    goal[0]      ,    goal[1]      ,    goal[0]      ,    a__     )

            __snake_case      :Optional[int] 							=    [self.start]
            __snake_case      :Optional[Any] 							=    False



       def        __lowercase    (				self     )			->   Path | None:






            '''simple docstring'''





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

                 if current_node.pos == self.target.pos:
                      __snake_case      :Optional[Any] 							=    True
                      return self.retrace_path(a__     )

                 __snake_case      :str 							=    self.get_successors(a__     )

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

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



       def        __lowercase    (				self      ,    a__     )			->   list[Node]:






            '''simple docstring'''





            __snake_case      :Optional[int] 							=    []
            for action in delta:
                 __snake_case      :Optional[Any] 							=    parent.pos_x + action[1]
                 __snake_case      :Dict 							=    parent.pos_y + action[0]
                 if not (0 <= pos_x <= len(grid[0]     ) - 1 and 0 <= pos_y <= len(a__     ) - 1):
                      continue

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

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



       def        __lowercase    (				self      ,    a__     )			->   Path:






            '''simple docstring'''





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




class       snake_case__ :

       '''simple docstring'''



       def __init__(				self      ,    a__      ,    a__     )			->   Optional[Any]:






            '''simple docstring'''





            __snake_case      :List[str] 							=    BreadthFirstSearch(a__      ,    a__     )
            __snake_case      :Optional[Any] 							=    BreadthFirstSearch(a__      ,    a__     )
            __snake_case      :List[Any] 							=    False



       def        __lowercase    (				self     )			->   Path | None:






            '''simple docstring'''





            while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
                 __snake_case      :Any 							=    self.fwd_bfs.node_queue.pop(0     )
                 __snake_case      :List[str] 							=    self.bwd_bfs.node_queue.pop(0     )

                 if current_bwd_node.pos == current_fwd_node.pos:
                      __snake_case      :Optional[Any] 							=    True
                      return self.retrace_bidirectional_path(
                          a__      ,    a__     )

                 __snake_case      :List[Any] 							=    current_bwd_node
                 __snake_case      :List[str] 							=    current_fwd_node

                 __snake_case      :Optional[int] 							=    {
                     self.fwd_bfs: self.fwd_bfs.get_successors(a__     ),
                     self.bwd_bfs: self.bwd_bfs.get_successors(a__     ),
                 }

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

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



       def        __lowercase    (				self      ,    a__      ,    a__     )			->   Path:






            '''simple docstring'''





            __snake_case      :List[Any] 							=    self.fwd_bfs.retrace_path(a__     )
            __snake_case      :Tuple 							=    self.bwd_bfs.retrace_path(a__     )
            bwd_path.pop()
            bwd_path.reverse()
            __snake_case      :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)










import copy
from dataclasses import dataclass, field
from typing import ClassVar, Dict

from ..features import Audio, ClassLabel, Features
from .base import TaskTemplate




@dataclass(frozen=lowercase_)
class       snake_case__ (				lowercase_):

       '''simple docstring'''
       lowerCamelCase				:					str								=			field(default="audio-classification"						,     metadata={"include_in_asdict_even_if_is_default": True})
       lowerCamelCase				:					ClassVar[Features]								=			Features({"audio": Audio()})
       lowerCamelCase				:					ClassVar[Features]								=			Features({"labels": ClassLabel})
       lowerCamelCase				:					str								=			"audio"
       lowerCamelCase				:					str								=			"labels"



       def        __lowercase    (				self      ,    a__     )			->   Dict:






            '''simple docstring'''





            if self.label_column not in features:
                 raise ValueError(F'''Column {self.label_column} is not present in features.'''     )
            if not isinstance(features[self.label_column]      ,    a__     ):
                 raise ValueError(F'''Column {self.label_column} is not a ClassLabel.'''     )
            __snake_case      :Any 							=    copy.deepcopy(self     )
            __snake_case      :List[Any] 							=    self.label_schema.copy()
            __snake_case      :List[Any] 							=    features[self.label_column]
            __snake_case      :Optional[Any] 							=    label_schema
            return task_template



       @property
       def        __lowercase    (				self     )			->   Dict[str, str]:






            '''simple docstring'''





            return {
                self.audio_column: "audio",
                self.label_column: "labels",
            }


