Travelling Salesman with Spherical Coordinates.

Discussion in 'Java' started by Luc The Perverse, Apr 30, 2006.

  1. 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[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)

    [url]http://en.wikipedia.org/wiki/Great-circle_distance#The_formula[/url]

    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.
    [url]http://www.topcoder.com/stat?c=problem_statement&pm=996&rd=4372[/url]

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

    --

    LTP

    :)[/i]
    Luc The Perverse, Apr 30, 2006
    #1
    1. Advertising

  2. "Luc The Perverse" <> wrote in message
    news:...
    > 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.

    --
    LTP

    :)
    Luc The Perverse, May 1, 2006
    #2
    1. Advertising

  3. Luc The Perverse

    Guest

    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 ;)
    , May 1, 2006
    #3
  4. Luc The Perverse

    Eric Sosman Guest

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

    --
    Eric Sosman, May 1, 2006
    #4
  5. "Eric Sosman" <> 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.
    >> (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.

    --
    LTP

    :)
    Luc The Perverse, May 1, 2006
    #5
  6. Luc The Perverse

    Mitch Guest

    Luc The Perverse wrote:
    > "Eric Sosman" <> 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.
    >>> (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 :)
    Mitch, May 3, 2006
    #6
  7. "Mitch" <> wrote in message
    news:...
    > Luc The Perverse wrote:
    >> "Eric Sosman" <> 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.
    >>>> (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.)

    --
    LTP

    :)
    Luc The Perverse, May 3, 2006
    #7
  8. Luc The Perverse

    Chris Uppal Guest

    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
    Chris Uppal, May 4, 2006
    #8
  9. "Chris Uppal" <-THIS.org> wrote in message
    news:4459d2ad$0$616$...
    > 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 ?


    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

    :)
    Luc The Perverse, May 5, 2006
    #9
  10. 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
    Patricia Shanahan, May 5, 2006
    #10
  11. "Patricia Shanahan" <> wrote in message
    news:Zrx6g.3809$...
    > 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.


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

    --
    LTP

    :)
    Luc The Perverse, May 5, 2006
    #11
  12. Luc The Perverse

    Ed Guest

    Patricia Shanahan wrote:

    > 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

    --
    www.EdmundKirwan.com - Home of The Fractal Class Composition
    Ed, May 5, 2006
    #12
  13. Luc The Perverse

    Roedy Green Guest

    Modern Uses For Punch Cards

    On Thu, 4 May 2006 23:32:51 -0600, "Luc The Perverse"
    <> wrote, quoted or indirectly
    quoted someone who said :

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

    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, May 5, 2006
    #13
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Suresh  Kumar
    Replies:
    0
    Views:
    589
    Suresh Kumar
    Jul 3, 2003
  2. Suresh  Kumar
    Replies:
    0
    Views:
    514
    Suresh Kumar
    Jul 4, 2003
  3. Erlend Andreas Garberg

    Travelling salesman variation in python

    Erlend Andreas Garberg, Apr 1, 2004, in forum: Python
    Replies:
    20
    Views:
    4,166
    G√ľnter Jantzen
    Apr 2, 2004
  4. Bram Stolk

    spherical coordinates

    Bram Stolk, Apr 14, 2004, in forum: Python
    Replies:
    8
    Views:
    1,636
    Bram Stolk
    Apr 14, 2004
  5. Travelling salesman problem in C

    , Sep 10, 2006, in forum: C Programming
    Replies:
    26
    Views:
    14,257
Loading...

Share This Page