from __future__ import annotations

import time

snake_case__				= list[tuple[int, int]]

snake_case__				= [
    [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__				= [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class  UpperCamelCase				:

     '''simple docstring'''

     def __init__(					self				,				A_				,				A_				,				A_				,				A_				,				A_						) ->				Dict:






           """simple docstring"""
           _lowerCamelCase			    =				pos_x
           _lowerCamelCase			    =				pos_y
           _lowerCamelCase			    =				(pos_y, pos_x)
           _lowerCamelCase			    =				goal_x
           _lowerCamelCase			    =				goal_y
           _lowerCamelCase			    =				parent





class  UpperCamelCase				:

     '''simple docstring'''

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






           """simple docstring"""
           _lowerCamelCase			    =				Node(start[1]				,				start[0]				,				goal[1]				,				goal[0]				,				_SCREAMING_SNAKE_CASE						)
           _lowerCamelCase			    =				Node(goal[1]				,				goal[0]				,				goal[1]				,				goal[0]				,				_SCREAMING_SNAKE_CASE						)

           _lowerCamelCase			    =				[self.start]
           _lowerCamelCase			    =				False



     def 		UpperCamelCase_						(					self						) ->				Path | None:






           """simple docstring"""
           while self.node_queue:
                 _lowerCamelCase			    =				self.node_queue.pop(0						)

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

                 _lowerCamelCase			    =				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				,				A_						) ->				list[Node]:






           """simple docstring"""
           _lowerCamelCase			    =				[]
           for action in delta:
                 _lowerCamelCase			    =				parent.pos_x + action[1]
                 _lowerCamelCase			    =				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				,				A_						) ->				Path:






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





class  UpperCamelCase				:

     '''simple docstring'''

     def __init__(					self				,				A_				,				A_						) ->				Any:






           """simple docstring"""
           _lowerCamelCase			    =				BreadthFirstSearch(_SCREAMING_SNAKE_CASE				,				_SCREAMING_SNAKE_CASE						)
           _lowerCamelCase			    =				BreadthFirstSearch(_SCREAMING_SNAKE_CASE				,				_SCREAMING_SNAKE_CASE						)
           _lowerCamelCase			    =				False



     def 		UpperCamelCase_						(					self						) ->				Path | None:






           """simple docstring"""
           while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
                 _lowerCamelCase			    =				self.fwd_bfs.node_queue.pop(0						)
                 _lowerCamelCase			    =				self.bwd_bfs.node_queue.pop(0						)

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

                 _lowerCamelCase			    =				current_bwd_node
                 _lowerCamelCase			    =				current_fwd_node

                 _lowerCamelCase			    =				{
                     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				,				A_				,				A_						) ->				Path:






           """simple docstring"""
           _lowerCamelCase			    =				self.fwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE						)
           _lowerCamelCase			    =				self.bwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE						)
           bwd_path.pop()
           bwd_path.reverse()
           _lowerCamelCase			    =				fwd_path + bwd_path
           return path


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

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

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

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

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

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


def       __magic_name__(  __UpperCAmelCase ,						__UpperCAmelCase		)						->    bool:



      '''simple docstring'''

      _lowerCamelCase			    =				len(__UpperCAmelCase		)
      _lowerCamelCase			    =				[[False] * (required_sum + 1) for _ in range(arr_len + 1		)]

      # for each arr value, a sum of zero(0) can be formed by not taking any element
      # hence True/1
      for i in range(arr_len + 1		):
            _lowerCamelCase			    =				True

      # sum is not zero and set is empty then false
      for i in range(1 ,						required_sum + 1		):
            _lowerCamelCase			    =				False

      for i in range(1 ,						arr_len + 1		):
            for j in range(1 ,						required_sum + 1		):
                  if arr[i - 1] > j:
                        _lowerCamelCase			    =				subset[i - 1][j]
                  if arr[i - 1] <= j:
                        _lowerCamelCase			    =				subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

      return subset[arr_len][required_sum]


if __name__ == "__main__":
     import doctest

     doctest.testmod()