Velocity Reviews > Java > Travelling Salesman with Spherical Coordinates.

# Travelling Salesman with Spherical Coordinates.

Luc The Perverse
Guest
Posts: n/a

 04-30-2006
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.

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;
double[][] p = new double[cities.length][2];
for(int i=0;i<cities.length;i++){
p[i][0] =
"))));
p[i][1] =
")+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];
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

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

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

Luc The Perverse
Guest
Posts: n/a

 05-01-2006
"Luc The Perverse" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Just shoot me!

*snip*

Ok I got it. I guess my distance formula was just off.

Here is the working distance formula if anyone cares

double[][] p = new double[cities.length][2];
for(int i=0;i<cities.length;i++){
p[i][0] =
"))));
p[i][1] =
")+1)));
}
for(int i=0;i<cities.length;i++)
for(int j=0;j<cities.length;j++){
double o1 = p[i][0];
double o2 = p[j][0];
double dh = p[i][1] - p[j][1];
double p1 = cos(o2) * sin(dh);
p1*=p1;
double p2 = cos(o1) * sin(o2) - sin(o1) * cos(o2) * cos(dh);
p2*=p2;
double p3 = sin(o1) * sin(o2) + cos(o1)*cos(o2)*cos(dh);
di[i][j] = (double) r* Math.atan2(Math.sqrt(p1+p2), p3);
}
}

Someone pointed out that the problem would imply that I was supposed to use
the dot product to calculate the distance - but I didn't so oh well.

--
LTP

alexandre_paterson@yahoo.fr
Guest
Posts: n/a

 05-01-2006
Luc The Perverse pasted copyrighted content to c.l.j.p., including
>...
> 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.

You've got to be a registered TopCoder member to have access to
this problem.

You are not allowed to do what you just did (I'm pretty sure
you didn't ask for the permission to reproduce this information

By the way, TopCoder has very interesting discussion forums and
you'll find very knowledgeable coders there willing to answer your
question(s).

Alex (a "yellow" TopCoder member)

P.S: when I started competing on TopCoder I also needed, while
practicing, hours to solve some of the problems others where solving
in 15 minutes... Now I'm way better at it but "red" members are in
another league (if I was in that league I would be earning tens
of thousands of dollars per year competing

Eric Sosman
Guest
Posts: n/a

 05-01-2006

Luc The Perverse wrote On 04/30/06 18:04,:
> Just shoot me!

It may come to that ...

> Problem Statement
> [snipped long quotation, ending with]
> 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.

I hope (1) that you don't get in trouble, and (2) that
you'll be more careful in the future ...

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

Luc The Perverse
Guest
Posts: n/a

 05-01-2006
"Eric Sosman" <(E-Mail Removed)> wrote in message
news:1146499255.380754@news1nwk...
>
>
> Luc The Perverse wrote On 04/30/06 18:04,:
>> Just shoot me!

>
> It may come to that ...
>
>> Problem Statement
>> [snipped long quotation, ending with]
>> 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.

>
> I hope (1) that you don't get in trouble, and (2) that
> you'll be more careful in the future ...

I don't believe I will get in trouble for several reasons:

1. I don't think this is the reason they copyright their problems.
3. I don't think they are assholes.
4. They are not losing anything.
5. I'm not gaining anything.

I was unaware that there were top coder forums however though. I will
limit my conversations to there in the future.

Thanks for bringing it to my attention - I won't do it again.

--
LTP

Mitch
Guest
Posts: n/a

 05-03-2006
Luc The Perverse wrote:
> "Eric Sosman" <(E-Mail Removed)> wrote in message
> news:1146499255.380754@news1nwk...
>>
>> Luc The Perverse wrote On 04/30/06 18:04,:
>>> Just shoot me!
>>> [snipped long quotation, ending with]
>>> 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.

I'm sure no-one would have had any trouble with anything
Little rewording and you can post it wherever you like, I'm sure

Luc The Perverse
Guest
Posts: n/a

 05-03-2006
"Mitch" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Luc The Perverse wrote:
>> "Eric Sosman" <(E-Mail Removed)> wrote in message
>> news:1146499255.380754@news1nwk...
>>>
>>> Luc The Perverse wrote On 04/30/06 18:04,:
>>>> Just shoot me!
>>>> [snipped long quotation, ending with]
>>>> 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.

>
> The 'problem statement' is copyright. If you hadn't posted it verbatim
> I'm sure no-one would have had any trouble with anything
> Little rewording and you can post it wherever you like, I'm sure

I was tired, frustrated and not thinking.

Although I realize some companies can be difficult - I learned this while
trying to get
Concorde-New Horizons Studios to give, sell or license me the right to
listen to a song from a movie which never had a soundtrack released.

I learned a little bit about spherical geometry, but mostly I learned that
while mentally fatigued I have a severe inability to correctly transcribe a
formula from a webpage to a computer program. Learning when to take a
break will be a great accomplishment if I ever figure it out. (Reminiscent
of when I was trying to use a model of a pyramid, built with blocks to
deduce a formula for 1^2 + 2^2 + . . . + (n-1) ^ 2 + n.)

--
LTP

Chris Uppal
Guest
Posts: n/a

 05-04-2006
Luc The Perverse wrote:

> Learning when to take a
> break will be a great accomplishment if I ever figure it out.

Do you think of yourself as a late-night kind of person ?

I do and always have, but it took me years (decades!) to realise that despite
that my best hours for programming are from when I wake up through to about
11am. Maybe you are misjudging yourself similarly ?

-- chris

Luc The Perverse
Guest
Posts: n/a

 05-04-2006
"Chris Uppal" <(E-Mail Removed)-THIS.org> wrote in message
> Luc The Perverse wrote:
>
>> Learning when to take a
>> break will be a great accomplishment if I ever figure it out.

>
> Do you think of yourself as a late-night kind of person ?
>
> I do and always have, but it took me years (decades!) to realise that
> despite
> that my best hours for programming are from when I wake up through to
> 11am. Maybe you are misjudging yourself similarly ?

To be honest programming comes during "project time" which exists
independent of "optimal time". And yes I agree completely. However,
knowing my tendency to stay up to ridiculous hours and sleep all day, I
found it necessary to secure an early morning job to break me of that.

--
LTP

Patricia Shanahan
Guest
Posts: n/a

 05-05-2006
Chris Uppal wrote:
> Luc The Perverse wrote:
>
>
>> Learning when to take a
>>break will be a great accomplishment if I ever figure it out.

>
>
> Do you think of yourself as a late-night kind of person ?
>
> I do and always have, but it took me years (decades!) to realise that despite
> that my best hours for programming are from when I wake up through to about
> 11am. Maybe you are misjudging yourself similarly ?

For this one issue, programming on punch cards was better than modern
IDEs. When I got the point that I couldn't type a complete line
correctly with no backspace key in a few tries, I HAD to stop.

Patricia