



'''simple docstring'''





from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
SCREAMING_SNAKE_CASE__          =  0

SCREAMING_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],
]

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

SCREAMING_SNAKE_CASE__          =  tuple[int, int]


class 					snake_case			:



       def __init__(					self  ,UpperCAmelCase_  ,UpperCAmelCase_  ,UpperCAmelCase_  ,UpperCAmelCase_  ,UpperCAmelCase_  ,UpperCAmelCase_  ,)	->				None:
           lowercase__									=    pos_x
           lowercase__									=    pos_y
           lowercase__									=    (pos_y, pos_x)
           lowercase__									=    goal_x
           lowercase__									=    goal_y
           lowercase__									=    g_cost
           lowercase__									=    parent
           lowercase__									=    self.calculate_heuristic()
           lowercase__									=    self.g_cost + self.h_cost



       def 				_a   (					self   )	->				float:
           lowercase__									=    self.pos_x - self.goal_x
           lowercase__									=    self.pos_y - self.goal_y
           if HEURISTIC == 1:
               return abs(UpperCAmelCase_   ) + abs(UpperCAmelCase_   )
           else:
               return sqrt(dy**2 + dx**2   )







       def __lt__(					self  ,UpperCAmelCase_   )	->				bool:
           return self.f_cost < other.f_cost





class 					snake_case			:



       def __init__(					self  ,UpperCAmelCase_  ,UpperCAmelCase_   )	->				int:
           lowercase__									=    Node(start[1]  ,start[0]  ,goal[1]  ,goal[0]  ,0  ,UpperCAmelCase_   )
           lowercase__									=    Node(goal[1]  ,goal[0]  ,goal[1]  ,goal[0]  ,99_999  ,UpperCAmelCase_   )

           lowercase__									=    [self.start]
           lowercase__									=    []

           lowercase__									=    False



       def 				_a   (					self   )	->				list[TPosition]:
           while self.open_nodes:
               # Open Nodes are sorted using __lt__
               self.open_nodes.sort()
               lowercase__									=    self.open_nodes.pop(0   )

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

               self.closed_nodes.append(UpperCAmelCase_   )
               lowercase__									=    self.get_successors(UpperCAmelCase_   )

               for child_node in successors:
                   if child_node in self.closed_nodes:
                       continue

                   if child_node not in self.open_nodes:
                       self.open_nodes.append(UpperCAmelCase_   )
                   else:
                       # retrieve the best current path
                       lowercase__									=    self.open_nodes.pop(self.open_nodes.index(UpperCAmelCase_   )   )

                       if child_node.g_cost < better_node.g_cost:
                           self.open_nodes.append(UpperCAmelCase_   )
                       else:
                           self.open_nodes.append(UpperCAmelCase_   )

           return [self.start.pos]



       def 				_a   (					self  ,UpperCAmelCase_   )	->				list[Node]:
           lowercase__									=    []
           for action in delta:
               lowercase__									=    parent.pos_x + action[1]
               lowercase__									=    parent.pos_y + action[0]
               if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(UpperCAmelCase_   ) - 1):
                   continue

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

               successors.append(
                   Node(
                       UpperCAmelCase_  ,UpperCAmelCase_  ,self.target.pos_y  ,self.target.pos_x  ,parent.g_cost + 1  ,UpperCAmelCase_  ,)   )
           return successors







       def 				_a   (					self  ,UpperCAmelCase_   )	->				list[TPosition]:
           lowercase__									=    node
           lowercase__									=    []
           while current_node is not None:
               path.append((current_node.pos_y, current_node.pos_x)   )
               lowercase__									=    current_node.parent
           path.reverse()
           return path





class 					snake_case			:



       def __init__(					self  ,UpperCAmelCase_  ,UpperCAmelCase_   )	->				None:
           lowercase__									=    AStar(UpperCAmelCase_  ,UpperCAmelCase_   )
           lowercase__									=    AStar(UpperCAmelCase_  ,UpperCAmelCase_   )
           lowercase__									=    False



       def 				_a   (					self   )	->				list[TPosition]:
           while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
               self.fwd_astar.open_nodes.sort()
               self.bwd_astar.open_nodes.sort()
               lowercase__									=    self.fwd_astar.open_nodes.pop(0   )
               lowercase__									=    self.bwd_astar.open_nodes.pop(0   )

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

               self.fwd_astar.closed_nodes.append(UpperCAmelCase_   )
               self.bwd_astar.closed_nodes.append(UpperCAmelCase_   )

               lowercase__									=    current_bwd_node
               lowercase__									=    current_fwd_node

               lowercase__									=    {
                   self.fwd_astar: self.fwd_astar.get_successors(UpperCAmelCase_   ),
                   self.bwd_astar: self.bwd_astar.get_successors(UpperCAmelCase_   ),
               }

               for astar in [self.fwd_astar, self.bwd_astar]:
                   for child_node in successors[astar]:
                       if child_node in astar.closed_nodes:
                           continue

                       if child_node not in astar.open_nodes:
                           astar.open_nodes.append(UpperCAmelCase_   )
                       else:
                           # retrieve the best current path
                           lowercase__									=    astar.open_nodes.pop(
                               astar.open_nodes.index(UpperCAmelCase_   )   )

                           if child_node.g_cost < better_node.g_cost:
                               astar.open_nodes.append(UpperCAmelCase_   )
                           else:
                               astar.open_nodes.append(UpperCAmelCase_   )

           return [self.fwd_astar.start.pos]







       def 				_a   (					self  ,UpperCAmelCase_  ,UpperCAmelCase_   )	->				list[TPosition]:
           lowercase__									=    self.fwd_astar.retrace_path(UpperCAmelCase_   )
           lowercase__									=    self.bwd_astar.retrace_path(UpperCAmelCase_   )
           bwd_path.pop()
           bwd_path.reverse()
           lowercase__									=    fwd_path + bwd_path
           return path


if __name__ == "__main__":
 # all coordinates are given in format [y,x]
 SCREAMING_SNAKE_CASE__          =  (0, 0)
 SCREAMING_SNAKE_CASE__          =  (len(grid) - 1, len(grid[0]) - 1)
 for elem in grid:
  print(elem)

 SCREAMING_SNAKE_CASE__          =  time.time()
 SCREAMING_SNAKE_CASE__          =  AStar(init, goal)
 SCREAMING_SNAKE_CASE__          =  a_star.search()
 SCREAMING_SNAKE_CASE__          =  time.time() - start_time
 print(f'''AStar execution time = {end_time:f} seconds''')

 SCREAMING_SNAKE_CASE__          =  time.time()
 SCREAMING_SNAKE_CASE__          =  BidirectionalAStar(init, goal)
 SCREAMING_SNAKE_CASE__          =  time.time() - bd_start_time
 print(f'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')









'''simple docstring'''





import unittest

from transformers import JukeboxTokenizer
from transformers.testing_utils import require_torch


class 					snake_case			(unittest.TestCase ):
       lowerCAmelCase__	:Dict     =       JukeboxTokenizer
       lowerCAmelCase__	:List[str]     =       {
           "artist": "Zac Brown Band",
           "genres": "Country",
           "lyrics": "I met a traveller from an antique land,\n        Who said \"Two vast and trunkless legs of stone\n        Stand in the desert. . . . Near them, on the sand,\n        Half sunk a shattered visage lies, whose frown,\n        And wrinkled lip, and sneer of cold command,\n        Tell that its sculptor well those passions read\n        Which yet survive, stamped on these lifeless things,\n        The hand that mocked them, and the heart that fed;\n        And on the pedestal, these words appear:\n        My name is Ozymandias, King of Kings;\n        Look on my Works, ye Mighty, and despair!\n        Nothing beside remains. Round the decay\n        Of that colossal Wreck, boundless and bare\n        The lone and level sands stretch far away\n        ",
       }



       @require_torch
       def 				_a   (					self   )	->				Dict:
           import torch

           lowercase__									=    JukeboxTokenizer.from_pretrained("openai/jukebox-1b-lyrics"   )
           lowercase__									=    tokenizer(**self.metas   )["input_ids"]
           # fmt: off
           lowercase__									=    [
               torch.tensor([[
                   0, 0, 0, 7_169, 507, 9, 76, 39, 31, 46, 76, 27,
                   76, 46, 44, 27, 48, 31, 38, 38, 31, 44, 76, 32,
                   44, 41, 39, 76, 27, 40, 76, 27, 40, 46, 35, 43,
                   47, 31, 76, 38, 27, 40, 30, 64, 78, 76, 76, 76,
                   76, 76, 76, 76, 76, 23, 34, 41, 76, 45, 27, 35,
                   30, 76, 71, 20, 49, 41, 76, 48, 27, 45, 46, 76,
                   27, 40, 30, 76, 46, 44, 47, 40, 37, 38, 31, 45,
                   45, 76, 38, 31, 33, 45, 76, 41, 32, 76, 45, 46,
                   41, 40, 31, 78, 76, 76, 76, 76, 76, 76, 76, 76,
                   19, 46, 27, 40, 30, 76, 35, 40, 76, 46, 34, 31,
                   76, 30, 31, 45, 31, 44, 46, 63, 76, 63, 76, 63,
                   76, 63, 76, 14, 31, 27, 44, 76, 46, 34, 31, 39,
                   64, 76, 41, 40, 76, 46, 34, 31, 76, 45, 27, 40,
                   30, 64, 78, 76, 76, 76, 76, 76, 76, 76, 76, 8,
                   27, 38, 32, 76, 45, 47, 40, 37, 76, 27, 76, 45,
                   34, 27, 46, 46, 31, 44, 31, 30, 76, 48, 35, 45,
                   27, 33, 31, 76, 38, 35, 31, 45, 64, 76, 49, 34,
                   41, 45, 31, 76, 32, 44, 41, 49, 40, 64, 78, 76,
                   76, 76, 76, 76, 76, 76, 76, 1, 40, 30, 76, 49,
                   44, 35, 40, 37, 38, 31, 30, 76, 38, 35, 42, 64,
                   76, 27, 40, 30, 76, 45, 40, 31, 31, 44, 76, 41,
                   32, 76, 29, 41, 38, 30, 76, 29, 41, 39, 39, 27,
                   40, 30, 64, 78, 76, 76, 76, 76, 76, 76, 76, 76,
                   20, 31, 38, 38, 76, 46, 34, 27, 46, 76, 35, 46,
                   45, 76, 45, 29, 47, 38, 42, 46, 41, 44, 76, 49,
                   31, 38, 38, 76, 46, 34, 41, 45, 31, 76, 42, 27,
                   45, 45, 35, 41, 40, 45, 76, 44, 31, 27, 30, 78,
                   76, 76, 76, 76, 76, 76, 76, 76, 23, 34, 35, 29,
                   34, 76, 51, 31, 46, 76, 45, 47, 44, 48, 35, 48,
                   31, 64, 76, 45, 46, 27, 39, 42, 31, 30, 76, 41,
                   40, 76, 46, 34, 31, 45, 31, 76, 38, 35, 32, 31,
                   38, 31, 45, 45, 76, 46, 34, 35, 40, 33, 45, 64,
                   78, 76, 76, 76, 76, 76, 76, 76, 76, 20, 34, 31,
                   76, 34, 27, 40, 30, 76, 46, 34, 27, 46, 76, 39,
                   41, 29, 37, 31, 30, 76, 46, 34, 31, 39, 64, 76,
                   27, 40, 30, 76, 46, 34, 31, 76, 34, 31, 27, 44,
                   46, 76, 46, 34, 27, 46, 76, 32, 31, 30, 66, 78,
                   76, 76, 76, 76, 76, 76, 76, 76, 1, 40, 30, 76,
                   41, 40, 76, 46, 34, 31, 76, 42, 31, 30, 31, 45,
                   46, 27, 38, 64, 76, 46, 34, 31, 45, 31, 76, 49,
                   41, 44, 30, 45, 76, 27, 42, 42, 31, 27, 44, 65,
                   78, 76, 76, 76, 76, 76, 76, 76, 76, 13, 51, 76,
                   40, 27, 39, 31, 76, 35, 45, 76, 15, 52, 51, 39,
                   27, 40, 30, 35, 27, 45, 64, 76, 11, 35, 40, 33,
                   76, 41, 32, 76, 11, 35, 40, 33, 45, 66, 78, 76,
                   76, 76, 76, 76, 76, 76, 76, 12, 41, 41, 37, 76,
                   41, 40, 76, 39, 51, 76, 23, 41, 44, 37, 45, 64,
                   76, 51, 31, 76, 13, 35, 33, 34, 46, 51, 64, 76,
                   27, 40, 30, 76, 30, 31, 45, 42, 27, 35, 44, 67,
                   78, 76, 76, 76, 76, 76, 76, 76, 76, 14, 41, 46,
                   34, 35, 40, 33, 76, 28, 31, 45, 35, 30, 31, 76,
                   44, 31, 39, 27, 35, 40, 45, 63, 76, 18, 41, 47,
                   40, 30, 76, 46, 34, 31, 76, 30, 31, 29, 27, 51,
                   78, 76, 76, 76, 76, 76, 76, 76, 76, 15, 32, 76,
                   46, 34, 27, 46, 76, 29, 41, 38, 41, 45, 45, 27,
                   38, 76, 23, 44, 31, 29, 37, 64, 76, 28, 41, 47,
                   40, 30, 38, 31, 45, 45, 76, 27, 40, 30, 76, 28,
                   27, 44, 31, 78, 76, 76, 76, 76, 76, 76, 76, 76,
                   20, 34, 31, 76, 38, 41, 40, 31, 76, 27, 40, 30,
                   76, 38, 31, 48, 31, 38, 76, 45, 27, 40, 30, 45,
                   76, 45, 46, 44, 31, 46, 29, 34, 76, 32, 27, 44,
                   76, 27, 49, 27, 51, 78, 76, 76, 76, 76, 76, 76,
                   76, 76]]   ),
               torch.tensor([[0, 0, 0, 1_069, 11]]   ),
               torch.tensor([[0, 0, 0, 1_069, 11]]   ),
           ]
           # fmt: on
           self.assertTrue(torch.allclose(tokens[0]  ,EXPECTED_OUTPUT[0]   )   )
           self.assertTrue(torch.allclose(tokens[1]  ,EXPECTED_OUTPUT[1]   )   )
           self.assertTrue(torch.allclose(tokens[2]  ,EXPECTED_OUTPUT[2]   )   )







       @require_torch
       def 				_a   (					self   )	->				Optional[Any]:
           import torch

           lowercase__									=    JukeboxTokenizer.from_pretrained("openai/jukebox-5b-lyrics"   )
           lowercase__									=    tokenizer(**self.metas   )["input_ids"]
           # fmt: off
           lowercase__									=    [
               torch.tensor([[
                   0, 0, 0, 1_069, 11, -1, -1, -1, -1, 9, 77, 39,
                   31, 46, 77, 27, 77, 46, 44, 27, 48, 31, 38, 38,
                   31, 44, 77, 32, 44, 41, 39, 77, 27, 40, 77, 27,
                   40, 46, 35, 43, 47, 31, 77, 38, 27, 40, 30, 64,
                   79, 77, 77, 77, 77, 77, 77, 77, 77, 23, 34, 41,
                   77, 45, 27, 35, 30, 77, 72, 20, 49, 41, 77, 48,
                   27, 45, 46, 77, 27, 40, 30, 77, 46, 44, 47, 40,
                   37, 38, 31, 45, 45, 77, 38, 31, 33, 45, 77, 41,
                   32, 77, 45, 46, 41, 40, 31, 79, 77, 77, 77, 77,
                   77, 77, 77, 77, 19, 46, 27, 40, 30, 77, 35, 40,
                   77, 46, 34, 31, 77, 30, 31, 45, 31, 44, 46, 63,
                   77, 63, 77, 63, 77, 63, 77, 14, 31, 27, 44, 77,
                   46, 34, 31, 39, 64, 77, 41, 40, 77, 46, 34, 31,
                   77, 45, 27, 40, 30, 64, 79, 77, 77, 77, 77, 77,
                   77, 77, 77, 8, 27, 38, 32, 77, 45, 47, 40, 37,
                   77, 27, 77, 45, 34, 27, 46, 46, 31, 44, 31, 30,
                   77, 48, 35, 45, 27, 33, 31, 77, 38, 35, 31, 45,
                   64, 77, 49, 34, 41, 45, 31, 77, 32, 44, 41, 49,
                   40, 64, 79, 77, 77, 77, 77, 77, 77, 77, 77, 1,
                   40, 30, 77, 49, 44, 35, 40, 37, 38, 31, 30, 77,
                   38, 35, 42, 64, 77, 27, 40, 30, 77, 45, 40, 31,
                   31, 44, 77, 41, 32, 77, 29, 41, 38, 30, 77, 29,
                   41, 39, 39, 27, 40, 30, 64, 79, 77, 77, 77, 77,
                   77, 77, 77, 77, 20, 31, 38, 38, 77, 46, 34, 27,
                   46, 77, 35, 46, 45, 77, 45, 29, 47, 38, 42, 46,
                   41, 44, 77, 49, 31, 38, 38, 77, 46, 34, 41, 45,
                   31, 77, 42, 27, 45, 45, 35, 41, 40, 45, 77, 44,
                   31, 27, 30, 79, 77, 77, 77, 77, 77, 77, 77, 77,
                   23, 34, 35, 29, 34, 77, 51, 31, 46, 77, 45, 47,
                   44, 48, 35, 48, 31, 64, 77, 45, 46, 27, 39, 42,
                   31, 30, 77, 41, 40, 77, 46, 34, 31, 45, 31, 77,
                   38, 35, 32, 31, 38, 31, 45, 45, 77, 46, 34, 35,
                   40, 33, 45, 64, 79, 77, 77, 77, 77, 77, 77, 77,
                   77, 20, 34, 31, 77, 34, 27, 40, 30, 77, 46, 34,
                   27, 46, 77, 39, 41, 29, 37, 31, 30, 77, 46, 34,
                   31, 39, 64, 77, 27, 40, 30, 77, 46, 34, 31, 77,
                   34, 31, 27, 44, 46, 77, 46, 34, 27, 46, 77, 32,
                   31, 30, 66, 79, 77, 77, 77, 77, 77, 77, 77, 77,
                   1, 40, 30, 77, 41, 40, 77, 46, 34, 31, 77, 42,
                   31, 30, 31, 45, 46, 27, 38, 64, 77, 46, 34, 31,
                   45, 31, 77, 49, 41, 44, 30, 45, 77, 27, 42, 42,
                   31, 27, 44, 65, 79, 77, 77, 77, 77, 77, 77, 77,
                   77, 13, 51, 77, 40, 27, 39, 31, 77, 35, 45, 77,
                   15, 52, 51, 39, 27, 40, 30, 35, 27, 45, 64, 77,
                   11, 35, 40, 33, 77, 41, 32, 77, 11, 35, 40, 33,
                   45, 66, 79, 77, 77, 77, 77, 77, 77, 77, 77, 12,
                   41, 41, 37, 77, 41, 40, 77, 39, 51, 77, 23, 41,
                   44, 37, 45, 64, 77, 51, 31, 77, 13, 35, 33, 34,
                   46, 51, 64, 77, 27, 40, 30, 77, 30, 31, 45, 42,
                   27, 35, 44, 67, 79, 77, 77, 77, 77, 77, 77, 77,
                   77, 14, 41, 46, 34, 35, 40, 33, 77, 28, 31, 45,
                   35, 30, 31, 77, 44, 31, 39, 27, 35, 40, 45, 63,
                   77, 18, 41, 47, 40, 30, 77, 46, 34, 31, 77, 30,
                   31, 29, 27, 51, 79, 77, 77, 77, 77, 77, 77, 77,
                   77, 15, 32, 77, 46, 34, 27, 46, 77, 29, 41, 38,
                   41, 45, 45, 27, 38, 77, 23, 44, 31, 29, 37, 64,
                   77, 28, 41, 47, 40, 30, 38, 31, 45, 45, 77, 27,
                   40, 30, 77, 28, 27, 44, 31, 79, 77, 77, 77, 77,
                   77, 77, 77, 77, 20, 34, 31, 77, 38, 41, 40, 31,
                   77, 27, 40, 30, 77, 38, 31, 48, 31, 38, 77, 45,
                   27, 40, 30, 45, 77, 45, 46, 44, 31, 46, 29, 34,
                   77, 32, 27, 44, 77, 27, 49, 27, 51, 79, 77, 77,
                   77, 77, 77, 77, 77, 77]]   ),
               torch.tensor([[0, 0, 0, 1_069, 11, -1, -1, -1, -1]]   ),
               torch.tensor([[0, 0, 0, 1_069, 11, -1, -1, -1, -1]]   ),
           ]
           # fmt: on
           self.assertTrue(torch.allclose(tokens[0]  ,EXPECTED_OUTPUT[0]   )   )
           self.assertTrue(torch.allclose(tokens[1]  ,EXPECTED_OUTPUT[1]   )   )
           self.assertTrue(torch.allclose(tokens[2]  ,EXPECTED_OUTPUT[2]   )   )




