Just shoot me!

I spent all day (5 hours) working on a top coder problem and now it is

failing the test cases after I thought I finally had it.

I was wondering if anyone could tell me what is going wrong.

Here is the problem. (If I am misusing the word permutation and should be

using the word combination, please forgive me, but at least I will be

consistent!)

Problem Statement

A traveling salesman has recently decided to go international

and sell his wares around the globe. He has done in depth research and has

come up with a list of cities which he thinks will provide the best market

for his goods. In planning his trip, the salesman wants to minimize the

total distance he has to travel because he does not particularly like

traveling (which is unfortunate for him, as he is a traveling salesman) and

furthermore, he figures the less distance he has to travel, the cheaper his

trip will be. However, this salesman is not particularly good at math, and

so you must write a computer program to help him find his way in the least

distance.

You will be given a set of cities defined by their longitudes and

latitudes. In addition, you will be given the radius of the planet that this

traveling salesman resides on. Assume that there are direct flights, both

ways, between every pair of cities that the salesman wants to visit, and

that the flights follow the shortest path possible (over the surface of the

planet). In addition, the first element of the input String[] will be the

city in which the salesman lives, and thus his trip must start and end at

this city.

Each city is defined by two numbers, a latitude and a longitude. The

latitude is the number of degrees above the equator, with 90 being the north

pole, and -90 being the south pole. The longitude is the number of degrees

east or west of some arbitrary, predefined point. Thus, 90 degrees east is

one quarter of the way around the globe in the eastern direction.

If the result is not an integer, round it to the nearest integer (.5

rounds up)

Definition

Class: Travel

Method: shortest

Parameters: String[], int

Returns: int

Method signature: int shortest(String[] cities, int radius)

(be sure your method is public)

Notes

- Assume the planet is a perfect sphere.

- To find the cartesion coordinates of a city, assuming the center of

the planet is at (0,0,0), use the following formulas:

x = r*cos(latitude)*cos(longitude)

y = r*cos(latitude)*sin(longitude)

z = r*sin(latitude)

Constraints

- cities contains between 2 and 9 elements, inclusive.

- Each element of cities represents a unique point on the globe.

- Each element of cities is formatted as "<latitude> <longitude>"

where <latitude> is an integer in the range -90 to 90, inclusive, and

<longitude> is an integer in the range -180 to 180, inclusive.

- radius is an integer between 1 and 1,000, inclusive.

- to avoid rounding errors, the shortest path, prior to rounding,

will not be within 0.001 of <x>+0.5 for any integer <x>.

Examples

0)

{"0 0","0 1"}

1000

Returns: 35

The two cities are located one degree apart at the same

latitude

1)

{"0 0","0 1","0 -1","-1 0","1 0","-1 -1","1 1","1 -1","-1 1"}

1

Returns: 0

2)

{"40 -82","-27 -59","-40 48"

,"26 -12","-31 -37","-30 42"

,"-36 -23","-26 71","-19 83","8 63"}

698

Returns: 4505

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)2003, TopCoder, Inc. All rights reserved.

Alright then - here is my [flawed] solution (It passes the example problem

and first 15 test cases)

import java.math.*;

import java.lang.*;

public class Travel{

double sin(double x){return Math.sin(x);};

double cos(double x){return Math.cos(x);};

double[][] di;

void calc(String[] cities, int radius){

double r = (double) radius;

double[][] p = new double[cities.length][2];

for(int i=0;i<cities.length;i++){

p[i][0] =

Math.toRadians((double)java.lang.Integer.parseInt( cities[i].substring(0,cities[i].indexOf("

"))));

p[i][1] =

Math.toRadians((double)java.lang.Integer.parseInt( cities[i].substring(cities[i].indexOf("

")+1)));

}

for(int i=0;i<cities.length;i++)

for(int j=0;j<cities.length;j++){

di[i][j] = (double) r* Math.acos(sin(p[i][0]) * sin(p[j][0]) +

cos(p[i][0]) * cos(p[j][0]) * cos(p[i][1] - p[j][1]) );

}

}

int[] newPerm(int c, int[] pr){ // c>=0 && c<=pr.length

int[] ret = new int[pr.length+1];

for(int i=0;i<pr.length;i++)

ret[i] = pr[i];

ret[pr.length] = ret[c];

ret[c] = pr.length+1;

return ret;

}

public int shortest(String[] cities, int radius){

di = new double[cities.length][cities.length];

calc(cities, radius);

int NP = 1;

int[][][] perms = new int[cities.length][][];

perms[0] = new int[0][0]; //empty set

for(int i=1;i<cities.length;i++){ //remember home cities is always start

and end point, ignore

NP*=i;

perms[i] = new int[NP][];

}

perms[1][0] = new int[1];

perms[1][0][0]=1;

for(int i = 2; i<perms.length;i++){

int cp=0;

for(int j=0;j<perms[i-1].length;j++)

for(int c=0;c<i;c++)

perms[i][cp++] = newPerm(c, perms[i-1][j]);

}

int[][] my = perms[perms.length-1]; // used to reference

perms[perms.length-1] to aid with clarity

double min = 0.0;

for(int i=0;i<di.length;i++)

for(int j=0;j<di.length;j++)

min+=di[i][j];

for(int i=0;i<my.length;i++){

double len = di[0][my[i][0]];

len+= di[0][my[i][my[i].length-1]];

for(int j=1;j<my[i].length;j++)

len += di[my[i][j-1]][my[i][j]];

if(len<min)

min = len;

}

return (int)(min+0.5); //remember to round up

}

}

This is the report I got

Failed system test 16 on the 300-point problem with args: [{"52 -150",

"-16 -166", "-88 -166", "58 -157", "58 147", "-32 41"}, 125]

EXPECTED: 790

RECEIVED: 0

I am fairly unfamiliar with spherical geometry so I used this wikipedia

article here to get my distance formula (this is my best guess as to where

the problem lies)

http://en.wikipedia.org/wiki/Great-c...ce#The_formula
It says that the formula I used suffered from rounding errors in a real

world environment, but the function itself is theoretically always accurate.

Since they were talking from a historical perspective, I was under the

assumption that the other formulae were simply there to facilitate with hand

calculations. (I did initially try one of the other fomulae but I think I

typed it wrong.)

I believe the lowest theortical score you can get on a top coder problem is

30% of the total points available, and I am within 1 point of this on the

exponential decay curve. In other words, I have failed! But that doesn't

mean I don't want to set it right.

I'll probably come back later and try to figure it out again, but for now I

am very frustrated. Any help would be appreciated. I have struggled with

every part of this. I tried to use a method for generating permutations in

which I could avoid overuse of the modulus operator, and I was forced to put

part of it in a function because it was exceptionally convoluted inline.

Appologies on the variable names. I wasn't planning on showing this to

anyone. Here is a brief synopsis (most variables are truncated english

words, shortened for easier typing):

Class:

di = distance between two cities

Calc Function (for calculating distances and putting in table)

r = radius, was originally used extensively so a shortened precasted

double was needed

p = the latitude and longitude of a location extracted from the string

array, but converted to rtadians

newPerm function (For generating a single permuation of X items 1 through X

given a permuation of X-1, by inserting X at location c)

ret = abbreviation for return value, holds the permutation

shortest function (As defined in the problem)

note: since the starting and ending city are always index 0,

index 0 is ommitted from the permutations

NP - holds the number of total permutations and is used incrementally

for declaring array sizes

perms - a holder for the permutations

cp - current position (a counter) simply a way of keeping track of which

permutation we are currently populating

my - a shortcut to perms[perms.length-1] and a variable name I

anticipate criticism for

min - the current minimum distance, initialized to the sum of all the

values in the di table (assumed all positive) which should be [greatly]

larger than the first permutation, so it will be reset in the first

iteration.

len - a temporary variable for holding the length of the trip to compare

against min. (The length is obviously just the sum of the distances

between all cities visited.)

Sorry if I missed any of them.

Thanks in advance for any help!

Oh if anyone cares, or it helps anyone this is practice room 14 300 point

(easy LOL) problem corresponding to the 2002 TopCoder Invitational Semifinal

Round 3. Here is a link to the problem, but I don't see where to get the

solution as they were submitted. It looks like 3 of the 4 contestants

submitted and they all three got it right.

http://www.topcoder.com/stat?c=probl...pm=996&rd=4372
Am I making this problem way harder than I need to?

--

LTP