Recent track work on the railroad, adding stations and tracks mean that existing timetables are now useless. It's your job as chief railroad engineer to work out the shortest route starting at any station and traveling to every other station on the network.
The railroad network has been modeled as a text file called tracks.txt which has 27 rows of 80 chars. Each char is one of
- . Empty
- + Railtrack
- S Switch
- 1-9,a-k Station
There is a complete path between any two stations which will cross any switches and go through other stations. Each station has two tracks and each switch can switch between three tracks in any direction. From station 1 a train can go direct to station 7, or via a switch to station 2 or 6 etc.
- Download tracks.txt (Updated Jan 27th)
Any route is possible, for instance a train could go from station 3 via a switch to station 2, and from there via another switch to station 6, or it could from station 3 go via 4 switches to station 6.
Your task is to process this text file which will be located in the same place as your exe and work out the shortest path that will reach every station. It can go through multiple switches, over the same track and stations multiple times however there is a cost for going along track and through stations and switches.
Costs
- Each * Costs 1
- Each S Costs 3
- Each 1-9,a-k Costs 5
The first station (whichever it is) costs nothing. After that total up the costs as your train proceeds. So the minimum cost would be 19x5 (all other stations) plus track and switch costs.
Output File
Please create a file route.txt in the same location as your exe. It should have one line for each route to a station in the following format.
Started at station 1 to station 2. Went 6 to Switch at (15,6) then 7 to Station 2 at (23,6) Total = 6(*) + 3(S) + 7(*) + 5(2)= 21.
etc
Total Score = 1234
Average time to process 0.023 secs
Timing Code
Please time from after reading the tracks.txt to doing the output. As this is likely to be very fast, please add code to loop multiple times calculating the route so that the total elapsed time is 1-5 seconds. Do not cache the calculation results or you'll be disqualified! If for instance it took 0.001 seconds to process the route once once then a loop of 1000 times should take just about a second to run.
This code below will do high speed timing for Windows (first three) and the fourth one for Linux.
Winning Criteria
Lowest score wins. If tied, then fastest time wins.
General Tips on Entering
This is a single page article with tips on things to do and not do when entering challenges. Please read it!
Rules
This is for glory only. About.com does not permit prizes to be given.Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Contest 54 email address with the subject line Programming Contest 54.
It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.
Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is January 31 2011.
The top ten entries in each challenge will be listed, judged on lowest number of moves and in the case of a draw, the lowest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.
- An index of Every Past Programming Contest on this site
