Travelling Salesman with Spherical Coordinates.


L

Luc The Perverse

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[0] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(0,cities.indexOf("
"))));
p[1] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(cities.indexOf("
")+1)));
}
for(int i=0;i<cities.length;i++)
for(int j=0;j<cities.length;j++){
di[j] = (double) r* Math.acos(sin(p[0]) * sin(p[j][0]) +
cos(p[0]) * cos(p[j][0]) * cos(p[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 = pr;
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 = 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[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[j];

for(int i=0;i<my.length;i++){
double len = di[0][my[0]];
len+= di[0][my[my.length-1]];
for(int j=1;j<my.length;j++)
len += di[my[j-1]][my[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-circle_distance#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=problem_statement&pm=996&rd=4372

Am I making this problem way harder than I need to?
 
Ad

Advertisements

L

Luc The Perverse

Luc The Perverse said:
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

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[0] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(0,cities.indexOf("
"))));
p[1] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(cities.indexOf("
")+1)));
}
for(int i=0;i<cities.length;i++)
for(int j=0;j<cities.length;j++){
double o1 = p[0];
double o2 = p[j][0];
double dh = p[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[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.
 
A

alexandre_paterson

Luc The Perverse pasted copyrighted content to c.l.j.p., including
the following copyright notice:
...
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.

:)

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

By registering to TopCoder, you agree to their terms of services.

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 ;)
 
E

Eric Sosman

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

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

Luc The Perverse

Eric Sosman said:
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.
(c)2003, TopCoder, Inc. All rights reserved.

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.
2. I had no mal-intent
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.
 
M

Mitch

Luc said:
Eric Sosman said:
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.
(c)2003, TopCoder, Inc. All rights reserved.

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 :)
 
Ad

Advertisements

L

Luc The Perverse

Mitch said:
Luc said:
Eric Sosman said:
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.
(c)2003, TopCoder, Inc. All rights reserved.

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.)
 
C

Chris Uppal

Luc said:
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
 
L

Luc The Perverse

Chris Uppal said:
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 ?

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.
 
P

Patricia Shanahan

Chris said:
Luc The Perverse wrote:




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
 
L

Luc The Perverse

Patricia Shanahan said:
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.

Not too many people could come up with a positive for punchcards over modern
compilers. Good job!
 
Ad

Advertisements

E

Ed

Patricia said:
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

There is a Remove-Delete-And-Backspace-Functionality PlugIn for
Eclipse.

Comes with a sample, "Helo Wurld," program ...

..ed
 
Ad

Advertisements

R

Roedy Green

Not too many people could come up with a positive for punchcards over modern
compilers. Good job!

There is another use for punch cards. One of the Canadian computer
journals published my article on how you do it.

I discovered the technique was faster than the "modern" OCR approach
for a project for BC Hydro to associate telephone poles with
transformers. The punch card technique was faster most of the time,
though in sparsely populated areas OCR turned out to be faster.

I originally first used the idea when I was 16 for high school
scheduling. The students filled in forms, but paid absolutely no
attention to the official list of course names.

So I punched out a card for every course name that any student used,
along with a count of how many students chose that spelling.

Then I handed the deck of cards to the vice principal who ordered the
cards with his preferred course name followed by all the variants
using a marker card between courses. He did this in just a few
minutes. The cards were already in alphabetical order. I used that
to build a HashMap(in FORTRAN back then) to convert all the data to
standard form.

I used the HashMap technique more recently for a government database
cleanup There were no punchcards, just records manually ordered by
mouse driven application to create the HashMap.

You could use it to create a list of canonical street names with
variants for example. It can be used then to automatically clean up
future errors as well.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top