This takes place on a map that is an 250 x 180 array of ints. Each point has the char value in the range '*','A'-'J' or '1'-'9'. No other values are allowed. These values have the following meanings.
- '*' - An impassable point. Cannot be included in the route.
- 'A'-'J' - There is one of each, ten in all. None occurs more than once.
- '1'..'9' The cost of entering a location is the ASCII value - 48. So to enter a '1' location (ASCII 49) costs 49-48 = 1.
*17594631*577393*244*454466252352121327**47*93955*3
3524412734*1565*2*3191197531816245*8**1759613859778
53*253416576251392268418395265918596444*58233992532
9951*294785*4A*5656*87718896*662295*91*185628846844
211*65754*47*63767*748687*51221536*4972*9*66*849289
991496*1667737798285213688473543324267384993194*79*
97513776433*3*3327925434*57825947255444679131265458
73564347183668524*5298*4168974178825474967672297712
7679979*46*8113182489189685282531*76655*85185*93*86
2981474*85*534186891737369*281*336*59*12253*4366*49
159*45156384216436639*9*177792581412681934149945627
987747*3444669656**65*B1*43581546884934614967*3965*
9673646777641149816313472955**731*4*61*229912468768
969625978*2689961825**74*649*64837636692349956351*2
6*798353987653618**42*9*87295688*48219*957682893158
Download the Data file. This is a zipped up file, 23KB in size.
Your program must read the file and locate the first point 'A'. It must then work out the lowest cost route from point 'A' to 'B' then 'B' to 'C' all the way to 'J'. You are allowed to use any algorithms you choose- including A*.
The cost of a route is the total cost of entering all the locations between the end points of a route. There is no cost to enter a way point 'A'-'J'. But of course the route must not enter any location with a *. Your route can move diagonally, horizontally or vertically in any direction by 1 square at a time. If a point is unreachable because it's surrounded by * then you can bypass it though with only 5,000 * in the map this is unlikely.
Output
Please output the following:
Path A to B costs x
Path B to C costs y
Total Cost of all 9 paths= z
Then output the data file in the same location (different name) as the original (in the same folder as your executable) with all unused locations set to a period. But leave the '*' and 'A' to 'J' in. So if printed it would show the ten routes and the route location costs for every location on the route. Routes may cross.
Also in the case of a tie, please include the total time it took, excluding the time to load the test data file. This is the code that you can use for timing.
Results
There were 4 entries, two in C++ and two in C#. This was quite a hard challenge so congrats to everyone who entered as they solved it. Particular congrats to Jared Cox with the shortest routes and an incredibly fast time!- Jared Cox (USA,31) - C# Score = 2801 Time(secs) = 0.166
- Sameerkumar Namdeo - C++ Score = 3001 Time(secs) = 429.46
- Dennis Muhlestein (USA,31) Dennis's Website - C++ Score = 4626 Time(secs) = 0.65
- Esteban Martínez (Argentina,18) - C# Score = 5136 Time(secs) = 227.91
More Programming Challenges
- Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
- Link to Programming Challenge 2 - Count the Islands. (Finished)
- Link to Programming Challenge 3 - Manage Elevators. (Finished)
- Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
- Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
- Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
- Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
- Link to Programming Challenge 8 - Score Poker Hands - (Finished)
- Link to Programming Challenge 9 - Manage a Data structure - (Finished)
- Link to Programming Challenge 10 - Hide Text (Finished)
- Link to Programming Challenge 11 - Match Sets of Cards (Closed)
- Link to Programming Challenge 13 - Play Battleships (Deadline June 30 2008)
