| | Introduction
In this problem you will have to navigate a spaceship to a series of waypoints in a two dimensionsal universe with a few stationary planets. Your goal is to visit all the waypoints, in order, as quickly as possible, but without using much fuel. Along the way, you need to avoid crashing into the planets, while taking their gravity into account for navigation.
Universe Details
Each waypoint is defined by its x and y coordinates, while each planet is defined by its coordinates and its radius. The mass of each planet is radius3 and standard physics equations are used to determine the movement of the ship. You have a single thruster that can accelerate your ship in any direction at a rate of 1E-4. The acceleration on your ship due to the gravity of a single planet is 5E-6*m/dist2, where m = radius3 is the mass of the planet. This acceleration is a vector in the direction of the center of the planet. The sum of all the acceleration vectors at a particular point gives the acceleration on the ship. Recall that to sum two vectors, you need only sum their components independently.
The center of each planet will be chosen with x and y in [-15000,15000], with its radius in [200,1200]. Each waypoint will be chosen with x and y in [-10000,10000]. Your ship will start at (0,0). There will be between 0 and 10 planets, and between 2 and 10 waypoints. All choices will be uniform except for radius, which will be chosen as rand2*1000+200, where rand is a uniform number in [0,1]. Any planet that is too close to the start will be rejected and a new one will be generated. In particular, if the distance to (0,0) is less than sqrt(0.05*r3) it will be rejected. Also, any planet that touches another planet will be rejected. Any waypoint generated within a planet (planets are generated first) will be rejected. To summarize:
0-10 planets in [-15000,15000]
radii in [200,1200]
2-10 waypoints in [-10000,10000]
G = 5E-6
thrust acceleration = 1E-4
gravity acceleration = G*r3/dist2
Implementation Details
At the beginning of execution, your init method will be called, giving the details of all the planets and waypoints. After this, getMoves will be called a number of times with your ships current position and velocity, as well as the index of the next waypoint you need to visit. You should return a String[] where each element gives either a thrust direction and time, or just a drift time. These commands will be executed in order, and the getMoves method will be called again. Each element should either be formatted as "dx dy time" or just "time". The first format gives the thrust direction and duration, while the second format tells how long to drift for. If your ship comes within 100 units of the next waypoint, that waypoint is considered to be touched. You may execute at most 10000 commands, and may use at most 10,000,000 units of time. Execution will continue until you give up (return {}), crash into a planet, run out of time, run out of commands, or touch all the waypoints.
Scoring
Your score will be based on how much fuel you use, how much time you take, and how many waypoints you touch. You will only be scored based on the time and fuel you had used at the last waypoint you touched (so there is never a penalty for trying to go further). Your base score will be time + fuel * 10, where fuel is the sum of your thrust durations, up to the last waypoint touched. When computing the final score, relative scoring will be used. If you touched at least one waypoint and as many as the person who touched the most (for a particular test case) you will get BEST/YOU points for that test. Otherwise, you will get 0.
Simulation Details
Computing the exact location of the ship after some interval will be done numerically, using a somewhat complicated method. The algorithm iteratively approximates and refines until it converges:
- compute ax(t) and ay(t) -- the acceleration at time t
- approximate x(t+h/2), y(t+h/2), x(t+h), and y(t+h), assuming that acceleration remains constant over this interval
- compute ax(t+h/2), ay(t+h/2), ax(t+h), and ay(t+h) using the current positional values for x(t+h/2), y(t+h/2), x(t+h), and y(t+h)
- fit a quadratic to the values from steps 1 and 3
- integrate the quadratic twice to find new values for x(t+h/2), y(t+h/2), x(t+h), and y(t+h)
- if convergence reached exit, else goto step 3
The only parameter in the above algorithm is h, the step size. To produce faster, more accurate reults, this parameter is determined during the above execution. In particular, it is chosen so that if the fitted quadratic is a(t) = U + V*t + W*t2, the value |W|*t5/12 = 1E-7. This causes the effect of the second order term to be small, and when the second order term has a small contribution, the error from the missing third order term should be even smaller. Here is the code used to simulate your ship.
/*
* x, y, dx, dy, and wp describe the current situation
* p and w give the planets and waypoints, while wp is the index of the next waypoint
* MAX_CHANGE controls the error
* when we simulate your code, we use 1E-7,
* however much larger results may work for most purposes
* for instance, even 0.1 gives good results over a short period of time,
* though the errors obviously accumulate to be huge in the long run
*
* tx and ty give the acceleration vector.
* It should have length 1E-4 or 0.
*
* The ship is then accelerated in that direction for time seconds
*
* The code is a bit complicated. It runs a numeric simulation.
* The idea behind the simulation is to approximate the acceleration equation with a
* quadratic equation over a small interval. This can be integrated exactly.
* The size of the interval depends on how crazy things are.
*/
boolean move(double tx, double ty, double time){
double expended = 0;
while(expended < time){
//start with a small amount of time -- simulation should be pretty stable over
//this intereval, in all but the crazies situations
double interval = 10;
double fx = tx;
double fy = ty;
double closest = hypot(x-w[wp][0],y-w[wp][1]);
for(int i = 0; i<p.length; i++){
double xd = p[i][0]-x;
double yd = p[i][1]-y;
double d = hypot(xd,yd);
if(d < p[i][2]){
//CRASH!
return false;
}
closest = min(closest,d-p[i][2]);
double F = pow(p[i][2],3)/d/d*G;
fx += F*xd/d;
fy += F*yd/d;
}
//fx and fy are something like force vectors (though really acceleration vectors)
//they give the vector at the start point
double ax = 0, bx = 0, cx = 0, ay = 0, by = 0, cy = 0;
double nfx1 = fx;
double nfy1 = fy;
double nfx2 = fx;
double nfy2 = fy;
//based on fx and fy, we approximate the ship's position interval/2 and interval seconds later
double nx1 = x + dx * interval/2 + fx * interval*interval/8;
double ny1 = y + dy * interval/2 + fy * interval*interval/8;
double nx2 = x + dx * interval + fx * interval*interval/2;
double ny2 = y + dy * interval + fy * interval*interval/2;
//now comes the refinement
for(int it = 0; it < ITERATIONS; it++){//shouldn't even reach ITERATIONS (200)
nfx1 = nfx2 = tx;
nfy1 = nfy2 = ty;
for(int i = 0; i<p.length; i++){
double xd1 = p[i][0]-nx1;
double yd1 = p[i][1]-ny1;
double d1 = hypot(xd1,yd1);
double F1 = pow(p[i][2],3)/d1/d1*G;
double xd2 = p[i][0]-nx2;
double yd2 = p[i][1]-ny2;
double d2 = hypot(xd2,yd2);
double F2 = pow(p[i][2],3)/d2/d2*G;
nfx1 += F1*xd1/d1;
nfy1 += F1*yd1/d1;
nfx2 += F2*xd2/d2;
nfy2 += F2*yd2/d2;
}
//nfx1,nfy1 and nfx2,nfy2 give the acceleration vectors at two
//positions: interval/2 and interval seconds later
//now we fit a quadratic to the x and y directions, independently
//so x(t) =~ ax + bx*t + cx * t * t
//so y(t) =~ ay + by*t + cy * t * t
ax = fx;
bx = -(nfx2-4*nfx1+3*fx)/interval;
cx = (nfx2-2*nfx1+fx)*2/interval/interval;
ay = fy;
by = -(nfy2-4*nfy1+3*fy)/interval;
cy = (nfy2-2*nfy1+fy)*2/interval/interval;
//here we adjust the time interval
//the goal is for the change acceleration to be MAX_CHANGE
double nt = pow(MAX_CHANGE/hypot(cx,cy)*12,.2);
//don't go very far if close to a planet or waypoint
double ttc = max(1,interval*closest/hypot(nx2-x,ny2-y));
if(nt > ttc){
nt = ttc;
}
//we ensure that we don't skip anything important by only
//adjusting up by factors of 2
if(nt > interval*2)nt = interval*2;
//always go at least 1
if(nt < 1)nt = 1;
if(nt > time-expended)nt = time-expended;
double pt = interval;
interval = nt;
//finally we integrate twice to get a better approximation of
//nx1,ny1 and nx2,ny2
double onx2 = nx2;
double ony2 = ny2;
nx1 = x + dx * interval/2 + ax * interval*interval/2/4 + bx*interval*interval*interval/6/8 + cx*interval*interval*interval*interval/12/16;
ny1 = y + dy * interval/2 + ay * interval*interval/2/4 + by*interval*interval*interval/6/8 + cy*interval*interval*interval*interval/12/16;
nx2 = x + dx * interval + ax * interval*interval/2 + bx*interval*interval*interval/6 + cx*interval*interval*interval*interval/12;
ny2 = y + dy * interval + ay * interval*interval/2 + by*interval*interval*interval/6 + cy*interval*interval*interval*interval/12;
//convergence reached
if(hypot(nx2-onx2,ny2-ony2) < MAX_CHANGE*1e-2 && abs(nt-pt) < 1e-8){
break;
}
}
x = nx2;
y = ny2;
dx += ax*interval + bx*interval*interval/2 + cx * interval * interval * interval / 3;
dy += ay*interval + by*interval*interval/2 + cy * interval * interval * interval / 3;
expended += interval;
//check waypoints
double wpd;
if(wp < w.length)wpd = hypot(x-w[wp][0],y-w[wp][1]);
else wpd = 1e9;
while(wpd < 100){//I guess we might we hit two at once
wp++;
if(wp < w.length)wpd = hypot(x-w[wp][0],y-w[wp][1]);
else wpd = 1e9;
}
}
return true;
}
Visualizer
The interface to the visualizer will work using standard in, out, and err, as in previous contests. You will read the parameters from standard in and write your return to standard out. First, you should read the parameters to init, in the same order as they appear in the function definition. Each parameter will be placed on a line by itself, formatted as: "NUM_ELEMENTS ELEMENT1 ELEMENT2 ...". Once you've read the parameters to init, you should print your first sequence of moves (the one you make will x=y=dx=dy=wp=0). You should then read the parameters to the next call to the getMoves method, one per line, and output your sequence of moves, and so on. Each time you output a a sequence of moves, you should first print the number of moves on a line by itself, and then the moves, one per line. In code, this looks like:
readIntArray(){
int length = readInt();
ret = new int[length];
for(int i = 0; i < length; i++){
ret[i] = readInt();
}
return ret;
}
main(){
px = readIntArray();
py = readIntArray();
pr = readIntArray();
wx = readIntArray();
wy = readIntArray();
moves = getMoves(0,0,0,0,0);
while(moves.length > 0){
printLine(moves.length);
for(int i = 0; i < moves.length; i++){
printLine(moves[i]);
}
x = readDouble();
y = readDouble();
dx = readDouble();
dy = readDouble();
wp = readInt();
moves = getMoves(x,y,dx,dy,wp);
}
}
Sample sequence of communication (the pare after the '#' or before the ':' is not part of the communication):
SERVER: 1 10342 #px
SERVER: 1 -1044 #py
SERVER: 1 1234 #pr
SERVER: 2 44 -904 #wx
SERVER: 2 -19229 52 #wy
YOU : 2 #moves.length
YOU : 200 #first move
YOU : 1 1 1000 #second move
SERVER: -23.11094 #x
SERVER: 3.3539 #y
SERVER: -1.50923E-6 #dx
SERVER: 0.000014948 #dy
SERVER: 0 #wp
YOU : 1 #moves.length
...
The password for the visualizer is marathon900
|