This contest is intended for the PHP Programmer with more than
6 months experience. You will be given strict instructions and it's
your job to create the most effective coded solution.
Contest Details:
You have just got a new job as a Pizza Deliverer; the location is in a new
town cleverly designed with those nice new one way traffic systems (he, he).
To do your job successfully you need to deliver a number of orders to various
destinations. You have been supplied a bottom of the range 50cc scooter with an
extremely low fuel tank (bummer). So, in order to keep your job (and not get stuck
in the middle of nowhere) you need to plan your route perfectly.
You will be supplied with a map which includes route distances. Delivery destinations and your time limit.
Map
Here is an example map:
Your map will look like this: (supplied in a text file, map.txt)
A 20 L 1
A 8 B 2
B 4 C 2
B 3 C 1
B 7 H 2
C 6 F 2
D 11 I 2
E 5 H 2
G 4 I 2
G 4 E 1
H 5 I 2
H 7 L 2
J 5 F 1
J 3 K 2
K 8 L 2
* note: above map has been fixed (23rd July)
Key to your map
From |
Distance |
To |
Rounte Type
There are 2 route types available. 1 = one way, and 2 = two way.
Note that '2' routes are only shown one way on the map (2 ways can be used). For example, if the map has A 5 B 2, then B 5 A 2 is also valid but will not be shown.
Delivery
Your delivery instructions will have this structure: (supplied in a text file, dest.txt)
A L I G B
It's up to you to plan your route, you do not have to deleiver in any certain order. For example you can deleivery to G then A then B etc, if you think this is the shortest route. I will allow your start point to be your first destination.
Remember you cannot travel the wrong way on a one way system!!
You can travel via other destinations, for example to travel from G to L - you can do G->I->H->L.
Time Limit
Your time limit is 60 seconds (scooters are fast these days you know :)
Details
Your script will be presented with map.txt and dest.txt, no graphical map will actually exist.
map.txt will follow this structure: From, space, distance, space, To, space, route type (1 or 2 way).
dest.txt will have this structure: Destinations split by a single space.
One way structures cannot be altered, if the map has A 5 B 1 then you cannot use the route B->A directly.
Script Maximim execution time will be set to 60 seconds. This may be increased if all entries fail (but im sure this will not happen :)
WINNING
The winner will be the script that finds the shortest route.
In the event of a tiebraker, the fastest script will rank higher.
Script accuracy is more important that speed!!!
Input
map.txt and dest.txt as explained above
Output
Your route delivery points in order, followed by total distance. For example:
A B I G L 40
Do not output via rounte points. For example I traveled from B to I via H, H should not be shown in the output.
My solution above may not be the best (more than likely will not).
Final Notes
The map and destinations given above are examples only, your script may be tested on different ones.
Closing Date:
All entries in by Monday 18th August 2003 at 23.59 (GMT)
Submissions:
send your entry (with scripts) to contest@php-editors.com please include a text file
'contact.txt' with your forum username, Full Name and Email Address.
Submissions should be zipped.
Judging:
In the event of a tiebrake (when script execution time is used)
I will execute several runs on each script to obtain an average.
Rules and Restrictions:
Must run on Windows, and Unix systems
Must run with PHP4.2 (register globals off)
No third party PHP extensions ( other than ones supplied with php 4.2 on php.net )
Maximum execution time 60 seconds.
All code must be writen by you !
Prizes:
1st. Nusphere PHPEd
2nd. 1 years subscription to PHP Magazine, Tamplate Tamer, $15 ThinkGeek Voucher
3rd. 1 month free hosting from TheHostingCompany.us. (Platinum Package)
*UPDATE: On the 23rd July I updated the Map and routes - I also stated that your start point is your first drop-off.
