Home > PHP, software development > traveling elephpant

traveling elephpant

! This post is pretty old.

So a little while back ibuildings had this fun contest to build a path finding program that would solve a traveling salesman like problem. The constraints where pretty simple, you got a CSV file with latitude/longitude locations. You started at a certain location and you should end at a certain location. The application should then find the shortest route that touched all locations.

Now I’ll be the first to say that PHP is really not the language for that. A few years back I wrote a pathfinding tool for use with a game called EVE online in which I calculated certain trade routes based on data you could export from the game. After seeing PHP’s performance I switched to Python and more or less sliced the processing time in half if not more. Mainly because Python has specific array like types and PHP just has generic array’s, which with large data sets matters a lot. Perhaps also because my pathfinding-foo was still rather weak :)

However, back to now and the ibuildings challenge. The challenge would be rated on 3 criteria. Speed, lines of code and code complexity. Personally I could care less about the latter two and focused purely on speed. In the weeks that followed I had a great time comparing execution times with Remi and Andries. I think this was also key to keep diving into it and tweaking it until it was as fast as I could get it.

Sadly, my submission actually had a off-by-one bug in it which more or less instantly disqualified my entry. Yes, bit of a bummer, but such is life.

Now I had already decided to publish my code after the contest, however sadly I never really found the time to type this up. So a bit late but here is the code for my solution for the ibuildings elephpant challenge.

Below is the submitted code, and a link to download the code and original test data file so you can try it out for yourself.

download the code – Just unpack and run via php contest.php elephpant_landmarks.csv

-edit-

Ok scratch the code, I’m having some trouble with getting it to play nice. Just download the tar.gz and view the code in your favorite editor.


  1. July 1st, 2010 at 07:14 | #1

    Hi Erik,

    I noticed you picked what looks like the same algorithm as mine, though mine was optimised for complexity and LOC rather than speed.

    Did you find and fix the bug? How was the speed of it in the end?

    Andy

  2. admin
    July 1st, 2010 at 09:52 | #2

    After Ivo posted on twitter that some entries were calculating one location too little I got a nagging feeling and checked my code.

    On line 200, where I add the final node to the completed path I actually overwrote the last location instead of adding it.

    $nodeTrail[$step++] = $endNodeKey;
    vs.
    $nodeTrail[++$step] = $endNodeKey;

    I never got my exact speed score, so I don’t know the numbers. I do know I was a little more then twice as slow as Remi’s entry which was 11s. So my speed was probably ~25 seconds or so.

  3. July 4th, 2010 at 10:01 | #3

    Ouch, that must be very frustrating.

    I had another look at your algorithm, and came up with changes to my own. The speed I calculated from my own ratio is very subjective though.

    Check it out in my comments on my blog article

    http://andytson.com/blog/2010/05/travelling-elephpant-solutions/comment-page-1/#comment-31

  4. Dave Edwards
    January 29th, 2012 at 20:29 | #4

    Class ‘SplFixedArray’ not found…

    $nodeTrail = new SplFixedArray(count($dataset)+1);

    Is there is a class missing?

    Thanks

    Dave

  5. admin
    February 2nd, 2012 at 13:48 | #5

    @Dave Edwards
    SplFixedArray were introduced in PHP 5.3, make sure you are running 5.3 or newer.

  1. No trackbacks yet.