JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: 2007 TopCoder Open Marathon Finals
Problem: Navigator

Problem Statement

    

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:
  1. compute ax(t) and ay(t) -- the acceleration at time t
  2. approximate x(t+h/2), y(t+h/2), x(t+h), and y(t+h), assuming that acceleration remains constant over this interval
  3. 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)
  4. fit a quadratic to the values from steps 1 and 3
  5. integrate the quadratic twice to find new values for x(t+h/2), y(t+h/2), x(t+h), and y(t+h)
  6. 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
 

Definition

    
Class:Navigator
Method:getMoves
Parameters:double, double, double, double, int
Returns:String[]
Method signature:String[] getMoves(double x, double y, double dx, double dy, int wp)
 
Method:init
Parameters:int[], int[], int[], int[], int[]
Returns:int
Method signature:int init(int[] px, int[] py, int[] pr, int[] wx, int[] wy)
(be sure your methods are public)
    
 

Notes

-Planets don't move.
-All coordinates and radii are integers.
-Your ship is treated as a point.
-While the visualizer uses the same code as the servers, the floating point arithmetic is slightly different between the two versions. Due to the chaotic nature of the problem, this can potentially lead to dramatic differences by the end of the game, for some solutions and test cases.
-The visualizer may use scientific notation when writing floating point numbers.
-The time limit is 60 seconds, and the memory limit is 1024M.
-There are 50 regular tests.
-Keep in mind that you don't have as much time as you are used to and that the way the scoring works, the most important thing is to hit waypoints.
 

Examples

0)
    
From seed 1 there are 0 planets and 2 waypoints
1)
    
From seed 2 there are 9 planets and 5 waypoints
2)
    
From seed 3 there are 5 planets and 2 waypoints
3)
    
From seed 4 there are 7 planets and 9 waypoints
4)
    
From seed 5 there are 4 planets and 2 waypoints
5)
    
From seed 6 there are 9 planets and 10 waypoints
6)
    
From seed 7 there are 10 planets and 3 waypoints
7)
    
From seed 8 there are 1 planets and 9 waypoints
8)
    
From seed 9 there are 0 planets and 3 waypoints
9)
    
From seed 14 there are 8 planets and 8 waypoints

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.