TopCoder problem "Planets" used in TCO '03 Round 1 (Division I Level Three)



Problem Statement

    

The motion of planets is relatively simple to simulate using computers. Newton's laws of gravity allow us to model this motion, so long as we know the masses, initial positions, and initial velocities of all the planets involved.

There are four basic laws of physics that you need to perform this simulation. In all of these laws, force, acceleration, and velocity are three-dimensional vectors, meaning they have x, y and z components.

The first law is F = ma where F stands for force, m stands for mass, and a stands for acceleration.

The second law is F = (G*m1*m2)/(d^2), where F again stands for force, m1 and m2 stand for the masses of some object 1 and object 2, d stands for the distance between object 1 and object 2, and G is a numerical constant.

Third is posf = posi + v*t where posi is the initial position, posf is the final position, v is the velocity, and t is the time.

Lastly, vf = vi + at, where vf is the final velocity, vi is the initial velocity, a stands for acceleration, and t stands for the time that the objects are accelerating.



So, if there are a number of planets, there is some force between each pair of planets, as defined by the second law. The direction of the force between two planets is always in the direction from one planet to the other. The total force on a planet is thus the vector sum of all of the individual forces on the planet. Note that the vector sum takes the directions of the forces into account. From this, we can use the first law given to find the acceleration of each planet (acceleration is always in the same direction as the force). Then, by using some small time interval, we can repeatedly move each planet and adjust its velocity. Thus, the algorithm to model the motion of planets for one time interval t is:
	foreach (planet p){
		F = vector sum over all p'!=p of ( G*m[p]*m[p']/(dist(p,p')^2) )
		v[p] = v[p] + F/m[p] * t;
	}
	foreach (planet p){
		pos[p] = pos[p] + v[p]*t;
	}
In other words, for each planet, we first compute and apply its change in velocity based on the locations of the other planets, and then we move the planet based on the new velocity.



In this problem, we will be using a constant of G = 6.673*(10^-11), and t = 3600 (this represents one hour).



You will be given a String[], planets, each of whose elements represents a planet. Each element of planets will be formatted as "<x position> <y position> <z position> <x velocity> <y velocity> <z velocity> <mass>". You will also be given an int, time, representing how many times to move the planets. You are to return a String[] each of whose elements represents the location of a planet (in the same order they are given to you), and is formatted as "<x position> <y position> <z position>".



Each <position> in the return should be in scientific notation, formatted as "D.DDDEN" or "-D.DDDEN", where each 'D' represents a digit, 'E' is just a single letter, and 'N' is the appropriate exponent with no extra leading zeros ('N' should never be less than zero, so 0.002 should be formatted as 0.002E0, not 2.000E-3). The final (fourth) 'D' should be rounded (.5 rounds up). For example, 12435000 would be formatted as "1.244E7", while 12434999 would be formatted as "1.243E7" and -1.0625 would be formatted as "-1.062E0"
 

Definition

    
Class:Planets
Method:locations
Parameters:String[], int
Returns:String[]
Method signature:String[] locations(String[] planets, int time)
(be sure your method is public)
    
 

Notes

-Planets should be treated as points, and we will not worry about the possibility of collisions.
-Be careful not to return "-0.000E0". If the actual number is -0.000000001, you should return "0.000E0".
-All calculations should be done using the 64 bit double type.
 

Constraints

-Each element of planets will be formatted as "<x position> <y position> <z position> <x velocity> <y velocity> <z velocity> <mass>", where each term is a real valued number.
-Each real number will be a <real> conforming to the following grammar:
  • <real> ::= (-)<num> | (-)<num><exponent>
  • <num> ::= <digits> | <digits>.<digits> | .<digits>
  • <exponent> ::= E<digits>
  • <digits> ::= a sequence of 1 or more digits ('0'-'9')
-time will be between 1 and 100, inclusive.
-planets will contain between 2 and 5 elements, inclusive.
-Each element of planets will contain between 13 and 50 characters, inclusive.
-Each <position> will be between -1E100 and 1E100.
-Each <velocity> will be between -1E20 and 1E20.
-Each <mass> will be between 1 and 1E50, inclusive.
-To prevent rounding errors, the formatted result will not be affected by relative or absolute errors up to 1e-6.
-No two planets will ever be within 1000 units of each other during any time step. However, this does not mean that two planets may not jump through each other (see example 2).
-To further ensure that there are no rounding errors, the result obtained using doubles will match the result using very precise calculations (using the BigDecimal class in Java).
 

Examples

0)
    
{"0 0 0 0 0 0 1.98892E30","1.496E11 0 0 0 29785.391801 0 5.972E24"}
100
Returns: { "1.165E3 2.756E1 0.000E0",  "1.492E11 1.071E10 0.000E0" }
The first planet here represents our sun, which moves relatively little, due to its high mass. The second planet represents the Earth.
1)
    
{"0 0 -.00000001 0 0 0 1.98892E30","1.496E11 0 0 0 29785.391801 0 5.972E24"}
1
Returns: { "0.231E0 0.000E0 0.000E0",  "1.496E11 1.072E8 0.000E0" }
This is pretty much the same as above, except it is only 1 hour. Also, note that the sun has been shifted a little bit in the z direction. Be careful that the third term of the first element of your return is "0.000E0", not "-0.000E0"
2)
    
{"0 000E0000 .0000 0 0 0 1.98892E30","1.496E8 0 0 0 0 0 5.972E24"}
1
Returns: { "2.308E5 0.000E0 0.000E0",  "-7.671E10 0.000E0 0.000E0" }
3)
    
{"0 0 0.0000 0 0 0 1.98892E30","1.496E11 0 0 0 0 0 5.972E24"}
50
Returns: { "2.943E2 0.000E0 0.000E0",  "1.495E11 0.000E0 0.000E0" }
4)
    
{"5.05E9 -5.45E9 7.43E9 63.36 -66.61 37.53 4.43E49",
 "3.25E9 -3.34E9 -2.64E9 -93.91 85.61 -34.32 7.90E49",
 "4.97E8 -4.78E9 4.70E9 -2.032 -46.67 66.06 1.74E49",
 "3.31E9 -2.58E9 4.98E9 26.73 -40.55 -64.62 4.10E48",
 "1.66E9 2.34E9 2.2E9 -90.23 92.23 -53.40 4.23E49"}
100
Returns: 
{ "-7.660E28 6.211E28 -1.186E29",
 "-1.518E28 3.601E28 1.015E29",
 "1.823E29 7.816E28 -4.915E28",
 "-2.968E28 -1.486E29 -4.411E28",
 "3.647E28 -1.500E29 -4.098E28" }
5)
    
{"0 0 0 0 0 0 1000","500 500 866.02540378443864676372317 0 0 0 1000","1000 1000 0 0 0 0 1000"}
100
Returns: 
{ "0.003E0 0.003E0 0.003E0",
 "5.000E2 5.000E2 8.660E2",
 "1.000E3 1.000E3 0.003E0" }
These three objects with relatively low masses (1,000 kg) form an equilateral triangle that slowly closes in. After 100 hours, each object has moved about 0.0052 (meters) towards the center of the triangle.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1522

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4702&pm=1522

Writer:

lars2520

Testers:

Problem categories:

Simulation, String Manipulation