12
\$\begingroup\$

This question is slightly harder than the ASCII art version. There is no art, and now you get to do some floating point arithmetic!

The Challenge

The U.S.S. StackExchange was traveling through the gravity field of planet cg-00DLEF when an astronomical explosion occurred on board. As the head programming officer of the ship, it is your job to simulate the trajectory of your ship in order to predict whether you will be forced to crash land in cg-00DELF's solar system. During the explosion, your ship was heavily damaged. Due to the limited free DEEEPRAROM* of the spaceship, you must write your program in as few characters as possible.

*Dynamically Executable Electronically Erasable Programmable Random Access Read Only Memory

The Simulation

Somewhat like the ASCII art version, there will be the idea of time-steps. In the other version, a time-step was a relatively large amount of time: the ship could travel way beyond the gravity of a planet in a single time-step. Here, the time-step is a much smaller unit of time due to the larger distances involved. One major difference, however, is the non-existence of cells. The spaceship's current location and velocity will be floating point numbers, along with the gravitational forces involved. Another change is the fact that planets now have a much larger size.

There will be up to three planets in the simulation. All three will have a specific location, radius, and gravity. The gravity for each planet is a vector that exerts a force directly towards the center of the planet. The formula to find the strength of this vector is (Gravity)/(Distance**2), where the distance is the exact distance from the ship to the center of the planet. This means that there is no limit to where gravity can reach.

At any specific time, the spaceship has a velocity, which is the distance and angle that it traveled from last time-step to now. The ship also has momentum. The distance that it will travel between the current time-step and the next is the sum of its current velocity added to all of the gravity vectors at its location. This becomes the spaceship's new velocity.

Each simulation has a time limit of 10000 time steps. If the spaceship travels inside of a planet (it is closer to the center of the planet than the planet's radius), then it crashes into that planet. If the spaceship does not crash into any planet by the end of the simulation, then it is presumed to have escaped from gravity. It is unlikely that the ship could be aligned so perfectly that it manages to stay in orbit for 10000 time-steps while crashing on the 10001st time-step.

Input

Input will be four lines to STDIN. Each line consists of four comma-delimited numbers. Here is the format of the numbers:

ShipLocX,ShipLocY,ShipVelX,ShipVelY
Planet1LocX,Planet1LocY,Planet1Gravity,Planet1Radius
Planet2LocX,Planet2LocY,Planet2Gravity,Planet2Radius
Planet3LocX,Planet3LocY,Planet3Gravity,Planet3Radius

If there are fewer than three planets, then the leftover lines will be filled with zeros for all values. Here is an example input:

60,0,0,10
0,0,4000,50
100,100,4000,50
0,0,0,0

This means that the spaceship is located at (60,0) and is traveling straight "up/north" at a rate of 10 units/time-step. There are two planets, one located at (0,0) and one at (100,100). Both have a gravity of 4000 and a radius of 50. Even though all of these are integers, they will not always be integers.

Output

Output will be a single word to STDOUT to tell whether the spaceship has crash landed or not. If the ship crash lands, print crash. Otherwise, print escape. Here is the expected output for the above input:

crash

You may be wondering what happened. Here is a Pastebin post that has a detailed flight log for the spaceship. Numbers aren't very good at helping people visualize the event so here is what happened: The spaceship manages to escape the gravity of the first planet (to its west) with the help of the gravity of the second planet (to its northeast). It moves north and then passes slightly to the west of the second planet, barely missing it. It then curves around the northern side of the planet and crashes into the eastern side of the second planet.

Some more cases for examination

60,0,10,-10
0,0,2000,50
100,100,1357.9,47.5
0,0,0,0

escape (due to the inverse square law, 2000 isn't much gravity if you are 60 units away)

0,0,0,0
100,100,20000,140
-50,-50,50,50
-100,-100,50,50

crash (the first planet is extremely massive and extremely close)

0,0,0,0
0,0,0,0
0,0,0,0
0,0,0,0

escape (this is an edge case: there are no planets and a straightforward interpretation would suggest that the spaceship is directly on top of the planets)

Rules, Restrictions, and Notes

This is code golf. Standard code golf rules apply. Your program should be written in printable ASCII characters only. You cannot access any sort of external database. You may write entries in any language (other than one that is specialized towards solving this challenge).

End Transmission

\$\endgroup\$
  • \$\begingroup\$ rofl DEEEPRAROM! — The planets' gravitational interaction isn't supposed to be simulated? Still not exactly expensive numerically then, but fair enough. — I assume the reference simulation uses standard Runge-Kutta 4th order integration, and our program must create equivalent results? \$\endgroup\$ – ceased to turn counterclockwis Apr 15 '12 at 11:06
  • \$\begingroup\$ I haven't figured out how to do multiple planets interacting. The problem is that they will tend to just crash into each other immediately. Fixing this will require bumping the scale of the simulation up incredibly. \$\endgroup\$ – PhiNotPi Apr 15 '12 at 13:48
  • \$\begingroup\$ As for the Runge-Kutta method, I'm honestly not that advanced in math yet. :( What I did was to calculate the gravity at the ship's current location and add this to the ship's velocity, generating the ship's new velocity. I did this for each time step. I know that this is not completely accurate, but I found out that dividing the ship's starting velocity and the planets' gravity by 10 increases the accuracy of the simulation. \$\endgroup\$ – PhiNotPi Apr 15 '12 at 13:52
  • \$\begingroup\$ Ah, that would be Euler's method. For small enough time steps that one is accurate, too; yet Runge-Kutta or something else more sophisticated would be more interesting to implement IMO. Maybe I should devise my own challenge, I can't seem to be easily satisfiable... \$\endgroup\$ – ceased to turn counterclockwis Apr 15 '12 at 14:51
  • \$\begingroup\$ @leftaroundabout Go ahead. You can make something like "simulate entire solar system using differential equations" or something fancy like that, or maybe add in the third dimension. \$\endgroup\$ – PhiNotPi Apr 16 '12 at 1:59
6
\$\begingroup\$

Python, 178 170 chars

p=input
a,b,c,d=p()
x=a+b*1j
v=c+d*1j
P=(p(),p(),p())
R='escape'
for i in' '*10000:
 for a,b,g,r in P:
  d=a+b*1j-x;v+=g*d/abs(d)**3
  if abs(d)<r:R='crash'
 x+=v
print R
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You're in a complex mood today, aren't you? \$\endgroup\$ – ceased to turn counterclockwis Apr 15 '12 at 20:50
  • 8
    \$\begingroup\$ yes, i am.... \$\endgroup\$ – Keith Randall Apr 15 '12 at 21:55
  • \$\begingroup\$ How can I compete with that? \$\endgroup\$ – Neil Apr 20 '12 at 16:06
  • \$\begingroup\$ @Neil: the code, or the witty banter? \$\endgroup\$ – Keith Randall Apr 20 '12 at 16:09
  • \$\begingroup\$ Well the code. The witty banter I can keep up with. \$\endgroup\$ – Neil Apr 23 '12 at 8:29
2
\$\begingroup\$

Golfrun/GolfScript?, 243 232 chars

10000:M;n%(','%2/{{~}%}/{{M*}%}:_~:v;_:x;'escape':R;{[','%2/{{~M*}%}/]}%:P;
M,{;P{~\x{0\-}%{+~@+@@+[\]}:|~:d.[~0\-]{[+.2%~*\.-2%~*@\-\.3%~*\(;);~*+]}:&~);~sqrt:z
..**\~d@[`~0]\&@M.*/\{1$/}%v|:v;;z\<{'crash':R;}{}if}/x v|:x;}/R puts

Golfrun is a language I'm working on, born as GolfScript C interpreter, but soon drifted away someway; though I've written this code without using knowingly specific Golfrun features (except for sqrt), the test with the original GolfScript failed (I had to add the sqrt feature to the original code, I am not a Ruby guru but I believe the problem is not my tweaking).

The first problem with this solution is that Golfrun, as GolfScript, has no floating point math. It is "simulated" magnifying the numbers, hopefully in the correct way (but I am not 100% confident I've done it coherently). Even so, the solution does not handle floating point numbers as input, so I had to magnify them by hand to have only integer numbers.

Trying to implement the algorithm in the Python code, I have also implemented bits of complex math in a rather "general" way. Manipulating the algorithm in order to avoid this, and/or inlining whenever possible, delaying the definitions, could save other chars...

How do I know this code works? Indeed, I am not sure it does! But giving the examples as input (after "removing" points where they appear), it wrote the expected results, except for the "corner case" (which raises an exception in Python too)...

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.