

from __future__ import annotations

import random

from matplotlib import animation
from matplotlib import pyplot as plt

# Frame rate of the animation
_lowerCAmelCase     :			Optional[Any]    =20

# Time between time steps in seconds
_lowerCAmelCase     :			Tuple    =INTERVAL / 10_00

class __UpperCamelCase    :






					'''simple docstring'''



					def __init__(							self							,			lowerCamelCase__							,			lowerCamelCase__							,			lowerCamelCase__							,			lowerCamelCase__							,			lowerCamelCase__ = 1.0							,			lowerCamelCase__ = 1.0							,			lowerCamelCase__ = "blue"							,			):
						UpperCAmelCase__:  Any		       =   position_x
						UpperCAmelCase__:  Optional[int]		       =   position_y
						UpperCAmelCase__:  Dict		       =   velocity_x
						UpperCAmelCase__:  Union[str, Any]		       =   velocity_y
						UpperCAmelCase__:  Optional[int]		       =   mass
						UpperCAmelCase__:  int		       =   size
						UpperCAmelCase__:  Union[str, Any]		       =   color





					@property
					def       _UpperCAmelCase						(							self	):
						return self.position_x, self.position_y





					@property
					def       _UpperCAmelCase						(							self	):
						return self.velocity_x, self.velocity_y





					def       _UpperCAmelCase						(							self							,			lowerCamelCase__							,			lowerCamelCase__							,			lowerCamelCase__	):
						self.velocity_x += force_x * delta_time
						self.velocity_y += force_y * delta_time





					def       _UpperCAmelCase						(							self							,			lowerCamelCase__	):
						self.position_x += self.velocity_x * delta_time
						self.position_y += self.velocity_y * delta_time

class __UpperCamelCase    :






					'''simple docstring'''



					def __init__(							self							,			lowerCamelCase__							,			lowerCamelCase__ = 1.0							,			lowerCamelCase__ = 1.0							,			lowerCamelCase__ = 0.0							,			):
						UpperCAmelCase__:  str		       =   bodies
						UpperCAmelCase__:  Tuple		       =   gravitation_constant
						UpperCAmelCase__:  Tuple		       =   time_factor
						UpperCAmelCase__:  Optional[Any]		       =   softening_factor





					def __len__(							self	):
						return len(self.bodies	)





					def       _UpperCAmelCase						(							self							,			lowerCamelCase__	):
						for bodya in self.bodies:
							UpperCAmelCase__:  Any		       =   0.0
							UpperCAmelCase__:  Optional[Any]		       =   0.0
							for bodya in self.bodies:
								if bodya != bodya:
									UpperCAmelCase__:  Optional[int]		       =   bodya.position_x - bodya.position_x
									UpperCAmelCase__:  List[Any]		       =   bodya.position_y - bodya.position_y

									# Calculation of the distance using Pythagoras's theorem
									# Extra factor due to the softening technique
									UpperCAmelCase__:  int		       =   (dif_x**2 + dif_y**2 + self.softening_factor) ** (
									    1 / 2
									)

									# Newton's law of universal gravitation.
									force_x += (
									    self.gravitation_constant * bodya.mass * dif_x / distance**3
									)
									force_y += (
									    self.gravitation_constant * bodya.mass * dif_y / distance**3
									)

            # Update the body's velocity once all the force components have been added
							bodya.update_velocity(lowerCamelCase__							,			lowerCamelCase__							,			delta_time * self.time_factor	)

						# Update the positions only after all the velocities have been updated
						for body in self.bodies:
							body.update_position(delta_time * self.time_factor	)



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	body_system.update_system(SCREAMING_SNAKE_CASE			)

	# Update the positions of the patches
	for patch, body in zip(SCREAMING_SNAKE_CASE  ,body_system.bodies			):
		UpperCAmelCase__:  str		       =   (body.position_x, body.position_y)



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE = -1  ,SCREAMING_SNAKE_CASE = 1  ,SCREAMING_SNAKE_CASE = -1  ,SCREAMING_SNAKE_CASE = 1  ,):
	UpperCAmelCase__:  int		       =   plt.figure()
	fig.canvas.set_window_title(SCREAMING_SNAKE_CASE			)
	UpperCAmelCase__:  Optional[int]		       =   plt.axes(
	    xlim=(x_start, x_end)  ,ylim=(y_start, y_end)			)  # Set section to be plotted
	plt.gca().set_aspect("equal"			)  # Fix aspect ratio

	# Each body is drawn as a patch by the plt-function
	UpperCAmelCase__:  Optional[int]		       =   [
	    plt.Circle((body.position_x, body.position_y)  ,body.size  ,fc=body.color			)
	    for body in body_system.bodies
	]

	for patch in patches:
		ax.add_patch(SCREAMING_SNAKE_CASE			)

	# Function called at each step of the animation
	def update(SCREAMING_SNAKE_CASE			) -> list[plt.Circle]:
		update_step(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			)
		return patches

	UpperCAmelCase__:  Tuple		       =   animation.FuncAnimation(  # noqa: F841
	    SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,interval=SCREAMING_SNAKE_CASE  ,blit=SCREAMING_SNAKE_CASE			)

	plt.show()



def  _A  (			):
	UpperCAmelCase__:  str		       =   0.9_70_04_36
	UpperCAmelCase__:  Optional[int]		       =   -0.24_30_87_53
	UpperCAmelCase__:  Dict		       =   0.4_66_20_36_85
	UpperCAmelCase__:  Union[str, Any]		       =   0.43_23_65_73

	UpperCAmelCase__:  Tuple		       =   [
	    Body(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,size=0.2  ,color="red"			),
	    Body(-position_x  ,-position_y  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,size=0.2  ,color="green"			),
	    Body(0  ,0  ,-2 * velocity_x  ,-2 * velocity_y  ,size=0.2  ,color="blue"			),
	]
	return BodySystem(SCREAMING_SNAKE_CASE  ,time_factor=3			)



def  _A  (			):
	UpperCAmelCase__:  Union[str, Any]		       =   7.3476e22
	UpperCAmelCase__:  Any		       =   5.972e24
	UpperCAmelCase__:  Any		       =   1_0_2_2
	UpperCAmelCase__:  List[Any]		       =   3_8_4_3_9_9_0_0_0
	UpperCAmelCase__:  List[str]		       =   6.674e-11

	# Calculation of the respective velocities so that total impulse is zero,
	# i.e. the two bodies together don't move
	UpperCAmelCase__:  List[str]		       =   earth_mass * velocity_dif / (earth_mass + moon_mass)
	UpperCAmelCase__:  Tuple		       =   moon_velocity - velocity_dif

	UpperCAmelCase__:  Union[str, Any]		       =   Body(-earth_moon_distance  ,0  ,0  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,1_0_0_0_0_0_0_0  ,"grey"			)
	UpperCAmelCase__:  Any		       =   Body(0  ,0  ,0  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,5_0_0_0_0_0_0_0  ,"blue"			)
	return BodySystem([earth, moon]  ,SCREAMING_SNAKE_CASE  ,time_factor=1_0_0_0_0_0_0			)



def  _A  (			):
	UpperCAmelCase__:  Dict		       =   []
	for _ in range(1_0			):
		UpperCAmelCase__:  Dict		       =   random.uniform(-0.5  ,0.5			)
		UpperCAmelCase__:  Union[str, Any]		       =   random.uniform(-0.5  ,0.5			)

		# Bodies are created pairwise with opposite velocities so that the
		# total impulse remains zero
		bodies.append(
		    Body(
		        random.uniform(-0.5  ,0.5			)  ,random.uniform(-0.5  ,0.5			)  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,size=0.05  ,)			)
		bodies.append(
		    Body(
		        random.uniform(-0.5  ,0.5			)  ,random.uniform(-0.5  ,0.5			)  ,-velocity_x  ,-velocity_y  ,size=0.05  ,)			)
	return BodySystem(SCREAMING_SNAKE_CASE  ,0.01  ,1_0  ,0.1			)


if __name__ == "__main__":
					plot("""Figure-8 solution to the 3-body-problem""", example_a(), -2, 2, -2, 2)
					plot(
					    """Moon's orbit around the earth""",
					    example_a(),
					    -4_30_00_00_00,
					    4_30_00_00_00,
					    -4_30_00_00_00,
					    4_30_00_00_00,
					)
					plot("""Random system with many bodies""", example_a(), -1.5, 1.5, -1.5, 1.5)


from __future__ import annotations



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	assert n > 1 and a > 0 and greatest_common_divisor(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			) == 1
	((UpperCAmelCase__)       ,	(UpperCAmelCase__)       ,	(UpperCAmelCase__)):  Optional[Any]		       =   extended_gcd(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			)  # Implemented below
	UpperCAmelCase__:  List[str]		       =   (b * s) % n
	return x



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	((UpperCAmelCase__)       ,	(UpperCAmelCase__)):  int		       =   extended_euclid(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			)  # Implemented below
	if b < 0:
		UpperCAmelCase__:  List[str]		       =   (b % n + n) % n
	return b



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	UpperCAmelCase__:  Union[str, Any]		       =   invert_modulo(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			)
	UpperCAmelCase__:  Any		       =   (b * s) % n
	return x



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	assert a >= 0 and b >= 0

	if b == 0:
		UpperCAmelCase__       ,	UpperCAmelCase__       ,	UpperCAmelCase__:  List[Any]		       =   a, 1, 0
	else:
		((UpperCAmelCase__)       ,	(UpperCAmelCase__)       ,	(UpperCAmelCase__)):  Tuple		       =   extended_gcd(SCREAMING_SNAKE_CASE  ,a % b			)
		UpperCAmelCase__:  Union[str, Any]		       =   q
		UpperCAmelCase__:  Union[str, Any]		       =   p - q * (a // b)

	assert a % d == 0 and b % d == 0
	assert d == a * x + b * y

	return (d, x, y)



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	if b == 0:
		return (1, 0)
	((UpperCAmelCase__)       ,	(UpperCAmelCase__)):  List[str]		       =   extended_euclid(SCREAMING_SNAKE_CASE  ,a % b			)
	UpperCAmelCase__:  Optional[Any]		       =   a // b
	return (y, x - k * y)



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	if a < b:
		UpperCAmelCase__       ,	UpperCAmelCase__:  str		       =   b, a

	while a % b != 0:
		UpperCAmelCase__       ,	UpperCAmelCase__:  Union[str, Any]		       =   b, a % b

	return b


if __name__ == "__main__":
					from doctest import testmod

					testmod(name="""modular_division""", verbose=True)
					testmod(name="""modular_division2""", verbose=True)
					testmod(name="""invert_modulo""", verbose=True)
					testmod(name="""extended_gcd""", verbose=True)
					testmod(name="""extended_euclid""", verbose=True)
					testmod(name="""greatest_common_divisor""", verbose=True)