


from manim import *

class   A__ (   snake_case__     ):







    """simple docstring"""

    def 		a_      (	self   ):
         snake_case					=    Rectangle(height=0.5      , width=0.5   )
         snake_case					=    Rectangle(height=0.46      , width=0.46   ).set_stroke(width=0   )

         snake_case					=    [mem.copy() for i in range(6   )]
         snake_case					=    [mem.copy() for i in range(6   )]
         snake_case					=    VGroup(*__snake_case   ).arrange(__snake_case      , buff=0   )
         snake_case					=    VGroup(*__snake_case   ).arrange(__snake_case      , buff=0   )
         snake_case					=    VGroup(__snake_case      , __snake_case   ).arrange(__snake_case      , buff=0   )
         snake_case					=    Text('''CPU'''      , font_size=2_4   )
         snake_case					=    Group(__snake_case      , __snake_case   ).arrange(__snake_case      , buff=0.5      , aligned_edge=__snake_case   )
         cpu.move_to([-2.5, -0.5, 0]   )
         self.add(__snake_case   )

         snake_case					=    [mem.copy() for i in range(1   )]
         snake_case					=    VGroup(*__snake_case   ).arrange(__snake_case      , buff=0   )
         snake_case					=    Text('''GPU'''      , font_size=2_4   )
         snake_case					=    Group(__snake_case      , __snake_case   ).arrange(__snake_case      , buff=0.5      , aligned_edge=__snake_case   )
         gpu.align_to(__snake_case      , __snake_case   )
         gpu.set_x(gpu.get_x() - 1   )

         self.add(__snake_case   )

         snake_case					=    [mem.copy() for i in range(6   )]
         snake_case					=    VGroup(*__snake_case   ).arrange(__snake_case      , buff=0   )

         snake_case					=    Text('''Model'''      , font_size=2_4   )
         snake_case					=    Group(__snake_case      , __snake_case   ).arrange(__snake_case      , buff=0.5      , aligned_edge=__snake_case   )
         model.move_to([3, -1.0, 0]   )

         self.play(
             Create(__snake_case      , run_time=1   )      , Create(__snake_case      , run_time=1   )      , Create(__snake_case      , run_time=1   )      , )

         snake_case					=    MarkupText(
             F'''First, an empty model skeleton is loaded\ninto <span fgcolor=\'{YELLOW}\'>memory</span> without using much RAM.'''      , font_size=2_4      , )

         snake_case					=    Square(side_length=2.2   )
         key.move_to([-5, 2, 0]   )

         snake_case					=    MarkupText(
             F'''<b>Key:</b>\n\n<span fgcolor=\'{YELLOW}\'>●</span> Empty Model'''      , font_size=1_8      , )

         key_text.move_to([-5, 2.4, 0]   )

         step_a.move_to([2, 2, 0]   )
         self.play(Write(__snake_case      , run_time=2.5   )      , Write(__snake_case   )      , Write(__snake_case   )   )

         self.add(__snake_case   )

         snake_case					=    []
         snake_case					=    []
         snake_case					=    []
         for i, rect in enumerate(__snake_case   ):
              snake_case					=    Rectangle(height=0.46      , width=0.46   ).set_stroke(width=0.0   ).set_fill(__snake_case      , opacity=0.7   )
              cpu_target.move_to(__snake_case   )
              cpu_target.generate_target()
              snake_case					=    0.46 / 4
              snake_case					=    0.46 / 3

              if i == 0:
                   cpu_target.target.next_to(cpu_left_col_base[0].get_corner(DOWN + LEFT   )      , buff=0.02      , direction=__snake_case   )
                   cpu_target.target.set_x(cpu_target.target.get_x() + 0.1   )
              elif i == 3:
                   cpu_target.target.next_to(cpu_targs[0].target      , direction=__snake_case      , buff=0.0   )
              else:
                   cpu_target.target.next_to(cpu_targs[i - 1].target      , direction=__snake_case      , buff=0.0   )
              cpu_targs.append(__snake_case   )

              first_animations.append(rect.animate(run_time=0.5   ).set_stroke(__snake_case   )   )
              second_animations.append(MoveToTarget(__snake_case      , run_time=1.5   )   )

         self.play(*__snake_case   )
         self.play(*__snake_case   )

         self.wait()








from __future__ import annotations

import time

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

_SCREAMING_SNAKE_CASE      :			Any      				=   [
    [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      :			Any      				=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case      , __snake_case      , __snake_case      , __snake_case      , __snake_case   ):
         snake_case					=    pos_x
         snake_case					=    pos_y
         snake_case					=    (pos_y, pos_x)
         snake_case					=    goal_x
         snake_case					=    goal_y
         snake_case					=    parent






class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case      , __snake_case   ):
         snake_case					=    Node(start[1]      , start[0]      , goal[1]      , goal[0]      , __snake_case   )
         snake_case					=    Node(goal[1]      , goal[0]      , goal[1]      , goal[0]      , __snake_case   )

         snake_case					=    [self.start]
         snake_case					=    False
    def 		a_      (	self   ):
         while self.node_queue:
              snake_case					=    self.node_queue.pop(0   )

              if current_node.pos == self.target.pos:
                   snake_case					=    True
                   return self.retrace_path(__snake_case   )

              snake_case					=    self.get_successors(__snake_case   )

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

         if not self.reached:
              return [self.start.pos]
         return None
    def 		a_      (	self      , __snake_case   ):
         snake_case					=    []
         for action in delta:
              snake_case					=    parent.pos_x + action[1]
              snake_case					=    parent.pos_y + action[0]
              if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(__snake_case   ) - 1):
                   continue

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

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




    def 		a_      (	self      , __snake_case   ):
         snake_case					=    node
         snake_case					=    []
         while current_node is not None:
              path.append((current_node.pos_y, current_node.pos_x)   )
              snake_case					=    current_node.parent
         path.reverse()
         return path






class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case      , __snake_case   ):
         snake_case					=    BreadthFirstSearch(__snake_case      , __snake_case   )
         snake_case					=    BreadthFirstSearch(__snake_case      , __snake_case   )
         snake_case					=    False
    def 		a_      (	self   ):
         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
              snake_case					=    self.fwd_bfs.node_queue.pop(0   )
              snake_case					=    self.bwd_bfs.node_queue.pop(0   )

              if current_bwd_node.pos == current_fwd_node.pos:
                   snake_case					=    True
                   return self.retrace_bidirectional_path(
                       __snake_case      , __snake_case   )

              snake_case					=    current_bwd_node
              snake_case					=    current_fwd_node

              snake_case					=    {
                  self.fwd_bfs: self.fwd_bfs.get_successors(__snake_case   ),
                  self.bwd_bfs: self.bwd_bfs.get_successors(__snake_case   ),
              }

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

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




    def 		a_      (	self      , __snake_case      , __snake_case   ):
         snake_case					=    self.fwd_bfs.retrace_path(__snake_case   )
         snake_case					=    self.bwd_bfs.retrace_path(__snake_case   )
         bwd_path.pop()
         bwd_path.reverse()
         snake_case					=    fwd_path + bwd_path
         return path


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

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

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

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

 _SCREAMING_SNAKE_CASE      :			Any      				=   time.time()
 _SCREAMING_SNAKE_CASE      :			Union[str, Any]      				=   BidirectionalBreadthFirstSearch(init, goal)
 _SCREAMING_SNAKE_CASE      :			Union[str, Any]      				=   bd_bfs.search()
 _SCREAMING_SNAKE_CASE      :			Tuple      				=   time.time() - start_bd_bfs_time

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




