'''simple docstring'''



from manim import *






class 							__lowercase    ( lowerCamelCase__  ):







	'''simple docstring'''

	def   _UpperCAmelCase       (self	)							->							int:







				'''simple docstring'''





				__lowercase			  =							Rectangle(height=0.5       ,width=0.5	)
				__lowercase			  =							Rectangle(height=0.4_6       ,width=0.4_6	).set_stroke(width=0	)

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

				__lowercase			  =							[mem.copy() for i in range(4	)]
				__lowercase			  =							VGroup(*__lowerCamelCase	).arrange(__lowerCamelCase       ,buff=0	)
				__lowercase			  =							Text('''GPU'''       ,font_size=24	)
				__lowercase			  =							Group(__lowerCamelCase       ,__lowerCamelCase	).arrange(__lowerCamelCase       ,buff=0.5       ,aligned_edge=__lowerCamelCase	)
				gpu.move_to([-1, -1, 0]	)
				self.add(__lowerCamelCase	)

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

				__lowercase			  =							Text('''Model'''       ,font_size=24	)
				__lowercase			  =							Group(__lowerCamelCase       ,__lowerCamelCase	).arrange(__lowerCamelCase       ,buff=0.5       ,aligned_edge=__lowerCamelCase	)
				model.move_to([3, -1.0, 0]	)
				self.add(__lowerCamelCase	)

				__lowercase			  =							[]
				for i, rect in enumerate(__lowerCamelCase	):
							rect.set_stroke(__lowerCamelCase	)
							# target = fill.copy().set_fill(YELLOW, opacity=0.7)
							# target.move_to(rect)
							# self.add(target)

							__lowercase			  =							Rectangle(height=0.4_6 / 4       ,width=0.4_6 / 3	).set_stroke(width=0.0	).set_fill(__lowerCamelCase       ,opacity=0.7	)

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

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

				__lowercase			  =							Text('''Loaded Checkpoint'''       ,font_size=24	)
				__lowercase			  =							Group(__lowerCamelCase       ,__lowerCamelCase	).arrange(__lowerCamelCase       ,aligned_edge=__lowerCamelCase       ,buff=0.4	)
				checkpoint.move_to([3, 0.5, 0]	)

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

				__lowercase			  =							MarkupText(
				    f"<b>Key:</b>\n\n<span fgcolor='{YELLOW}'>●</span> Empty Model"       ,font_size=18       ,)

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

				self.add(__lowerCamelCase       ,__lowerCamelCase	)

				__lowercase			  =							MarkupText(
				    f"<span fgcolor='{BLUE}'>●</span> Checkpoint"       ,font_size=18       ,)

				blue_text.next_to(__lowerCamelCase       ,DOWN * 2.4       ,aligned_edge=key_text.get_left()	)

				__lowercase			  =							MarkupText(
				    f"Next, a <i><span fgcolor=\"{BLUE}\">second</span></i> model is loaded into memory,\nwith the weights of a <span fgcolor=\"{BLUE}\">single shard</span>."       ,font_size=24       ,)
				step_a.move_to([2, 2, 0]	)
				self.play(Write(__lowerCamelCase	)       ,Write(__lowerCamelCase	)	)

				self.play(Write(__lowerCamelCase       ,run_time=1	)       ,Create(__lowerCamelCase       ,run_time=1	)	)

				__lowercase			  =							[]
				__lowercase			  =							[]
				for i, rect in enumerate(__lowerCamelCase	):
							__lowercase			  =							fill.copy().set_fill(__lowerCamelCase       ,opacity=0.7	)
							target.move_to(__lowerCamelCase	)
							first_animations.append(GrowFromCenter(__lowerCamelCase       ,run_time=1	)	)

							__lowercase			  =							target.copy()
							cpu_target.generate_target()
							if i < 5:
										cpu_target.target.move_to(cpu_left_col_base[i + 1]	)
							else:
										cpu_target.target.move_to(cpu_right_col_base[i - 5]	)
							second_animations.append(MoveToTarget(__lowerCamelCase       ,run_time=1.5	)	)

				self.play(*__lowerCamelCase	)
				self.play(*__lowerCamelCase	)
				self.wait()












'''simple docstring'''



_SCREAMING_SNAKE_CASE   =      {
    '''A''': ['''B''', '''C''', '''E'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F''', '''G'''],
    '''D''': ['''B'''],
    '''E''': ['''A''', '''B''', '''D'''],
    '''F''': ['''C'''],
    '''G''': ['''C'''],
}




def 				_lowerCAmelCase  (			lowerCamelCase_     :					dict						,    lowerCamelCase_     :					Optional[Any]						,    lowerCamelCase_     :					List[str]			):
			__lowercase			  =							set()
			# keep track of all the paths to be checked
			__lowercase			  =							[[start]]

			# return path if start is goal
			if start == goal:
						return [start]

			# keeps looping until all possible paths have been checked
			while queue:
						# pop the first path from the queue
						__lowercase			  =							queue.pop(0			)
						# get the last node from the path
						__lowercase			  =							path[-1]
						if node not in explored:
									__lowercase			  =							graph[node]
									# go through all neighbour nodes, construct a new path and
									# push it into the queue
									for neighbour in neighbours:
												__lowercase			  =							list(lowerCamelCase_			)
												new_path.append(lowerCamelCase_			)
												queue.append(lowerCamelCase_			)
												# return path if neighbour is goal
												if neighbour == goal:
															return new_path

            # mark node as explored
									explored.add(lowerCamelCase_			)

    # in case there's no path between the 2 nodes
			return []




def 				_lowerCAmelCase  (			lowerCamelCase_     :					dict						,    lowerCamelCase_     :					str						,    lowerCamelCase_     :					str			):
			if not graph or start not in graph or target not in graph:
						return -1
			if start == target:
						return 0
			__lowercase			  =							[start]
			__lowercase			  =							set(lowerCamelCase_			)
			# Keep tab on distances from `start` node.
			__lowercase			  =							{start: 0, target: -1}
			while queue:
						__lowercase			  =							queue.pop(0			)
						if node == target:
									__lowercase			  =							(
									    dist[node] if dist[target] == -1 else min(dist[target]						,    dist[node]			)
									)
						for adjacent in graph[node]:
									if adjacent not in visited:
												visited.add(lowerCamelCase_			)
												queue.append(lowerCamelCase_			)
												__lowercase			  =							dist[node] + 1
			return dist[target]


if __name__ == "__main__":
	print(bfs_shortest_path(demo_graph, '''G''', '''D'''))  # returns ['G', 'C', 'A', 'B', 'D']
	print(bfs_shortest_path_distance(demo_graph, '''G''', '''D'''))  # returns 4





