Clarifications

[Mr. Sketch]

Can the names have more than character?
Are they case sensitive?
If we don't print our full route, how will you verify that we didn't use a 1-way street the wrong way?
What's the maximum number of nodes/edges in the map and nodes in dest.txt that we should expect to have to deal with?
Probably more to come later, I'm sure...

Cool problem btw, I'm getting A B L I G 38 as the shortest path in the example and if I add every node to the destination list I'm getting D I G E H L K J F C B A 65 is anyone else getting something in the ballpark?

I should be okay on time, when having every node in dest.txt it takes my script less than a second on my P4 2.6Ghz.

[stuart]

Can the names have more than character?

I assume you mean 1 character... anyway the destinations will always be 1 character long yes.

Are they case sensitive

hmm.. no, a=A

If we don't print our full route, how will you verify that we didn't use a 1-way street the wrong way?

The be honest I wish I had asked for the full route... but its too late now ... I guess I will just need to check all posible routes to make sure entries are valid.

What's the maximum number of nodes/edges in the map and nodes in dest.txt that we should expect to have to deal with?

I will not have anymore than 26 nodes (a-z), and anywhere upto 26 destination drop-off points.[quote]

hope this helps

[ciaccia]

Originally posted by Mr. Sketch@Jul 24 2003, 11:53 PM
I'm getting A B L I G 38 as the shortest path in the example and if I add every node to the destination list I'm getting D I G E H L K J F C B A 65 is anyone else getting something in the ballpark?

Sure, I also get D I G E H L K J F C B A 65 adding all destination nodes. I only have to tweak speed a little bit now

[Mr. Sketch]

hope this helps

Yes, this helps a lot I was looking at making some speed improvements, since I wasn't relying on the assumption that each destination was one characater but since they are I can optimize that.

I guess I will just need to check all posible routes to make sure entries are valid.

That's non-trivial and may take a while to verify. Perhaps if you just checked the shortest route, to see if their distance is at least as short as they are claiming? If they found a longer route, too bad for them.

[FryGuy]

is anyone getting the A-L done in the 60 seconds?

I think i'll need to speed my code up.. It was almost instantaneous for the 5-path though

[Mr. Sketch]

Originally posted by FryGuy@Aug 15 2003, 11:44 AM
is anyone getting the A-L done in the 60 seconds?

I'm assuming you mean having all the destination nodes A through L in the dest.txt file. If so, then I do. It takes my script 0.53 seconds to solve and I get the path:
D I G E H L K J F C B A 65
The default route of 5 dests takes mine about 0.01 seconds and I get the path:
A B L I G 38

These are times on a P4 2.6GHz system, so your times may vary.

[dcann1222]

It takes my script 0.53 seconds to solve and I get the path:
D I G E H L K J F C B A 65

Wow, that's great. Are you checking all possible routes? My script solves the 5-destination route in 0.02 seconds, but it grows exponentially from there.

For example:
5 points = 120 possible routes (0.02 sec)
6 points = 720 possible routes (0.1 sec)
...
12 points = 479,001,600 possible routes (hours)
...
26 points = 403,291,461,126,606,000,000,000,000 possible routes (years!)

When calculating all of the possible permutations of the points, processing time quickly becomes unreasonable. I'd like to see how you guys solved this problem.

Originally posted by dcann1222@Aug 19 2003, 04:08 AM

Wow, that's great. Are you checking all possible routes? My script solves the 5-destination route in 0.02 seconds, but it grows exponentially from there.

For example:
5 points = 120 possible routes (0.02 sec)
6 points = 720 possible routes (0.1 sec)
...
12 points = 479,001,600 possible routes (hours)
...
26 points = 403,291,461,126,606,000,000,000,000 possible routes (years!)

When calculating all of the possible permutations of the points, processing time quickly becomes unreasonable. I'd like to see how you guys solved this problem.

You can use pruning to get the result space down. For instance if you know you have a solution that's 56, and you've got A B C D E F 60, then you don't have to worry about the permutations of G H I J K L (saving 5! or 120 permutations). If you catch the "error" earlier, then you save even more.

Yesterday I thought of an even better solution which goes along the lines of:

PHP Code:

// $bestdisttable[$a][$b] is the shortest path from $a to $b, calculated by using dijikstra in my case
$moves = explode(" ", $moves);
if (count($moves) == 2) {
  // assume that there is a path at least.
  if (&#036;bestdisttable[$moves[0]] < $bestdisttable[$moves[1]]) {
     echo &#036;moves[0]." ".$moves[1]." "($bestdisttable[$moves[0]] < $bestdisttable[$moves[1]]);
  } else {
     die(&#036;moves[0]." ".$moves[1]." "($bestdisttable[$moves[0]] < $bestdisttable[$moves[1]]));
  }
} else if (count(&#036;moves) == 1) {
   die(&#036;moves[0]." 0");
}


// we have 3 or more elements. Have fun with them!
&#036;movesleft = heap(); // theoretical function. I didn't make this yet
foreach (&#036;bestdisttable as $from=>$bestdist) {
  foreach (&#036;bestdist as $to=>$dist) {
     &#036;movesleft->insert = array("score" => $dist, "path" => array($from, $to));
  }
  while (&#036;work = $movesleft->lowest()) {
    if (count(&#036;work["path"]) == count($moves) {
      // if this is the first complete path, then it's a winner since you can't get lower than this by having a longer distance incomplete path added to some value.
      die (implode(" ", &#036;work["path"])." ".$work["score"]);
    } else {
      // otherwise put all the permutations from here on the heap
      foreach (&#036;moves as $move) {
         if (in_array(&#036;move, $work["path"])) continue;
         &#036;copy = $work;
         &#036;last = $copy["path"][count($copy["path"])-1];
         &#036;copy["path"][] = $move;
         &#036;copy["score"] += $bestdisttable[$last][$move];
         &#036;movesleft->insert($copy);
      }
    }
  }
} 


There's still lots of optimizations to be done, but it's too late for the contest anyways, so I didn't worry about it (I actually wrote it in this box). I haven't done any complexity tests, but I think it's still along the lines of n! worst-case, and much faster in the average-case

[Mr. Sketch]

Originally posted by dcann1222@Aug 18 2003, 10:08 PM
Wow, that's great. Are you checking all possible routes? My script solves the 5-destination route in 0.02 seconds, but it grows exponentially from there.

No, I don't check all possible routes. I construct a modified minimum spanning tree and continue modifying it (adding shortest edges) until I get a straight path that contains all the nodes. I didn't have time to do additional pruning on my MST so I just keep adding shortest edges until there exists a straight line containing all the nodes instead of forcing a tree structure so it still has an exponential worst case. But in the average case it runs quickly.

Well, that's what I do for larger numbers of destinations. For smaller numbers of destinations it's okay to check all possible routes since it can be done quickly. I basically cap out at 40 seconds of searching for the best route and then switch to my MST approach.