The challenge is over (see the "Description" column for the submitted sources). We can't decide, which solution has not won, so Jon Erickson, editor of Dr. Dobb's Journal, increases the number of CD-ROMs to 7, for all people who have submitted a solution with source code. The winning list is:
Allen Noe
David Finch
Jeremie Allard
Kevin Shepherd
Matthew Ogilvie
Randy Sargent
Stefan Ram
Congratulation!
The challenge maps were:
Sort the submittet solutions (default is sorted by date):
Sort by steps, fuel usage, date
Sort by fuel usage, steps, date
| Name | Steps | Fuel Usage | Map | Submit Date (y/m/d h:m:s) | Solution | Path | Comment | Description |
|---|---|---|---|---|---|---|---|---|
| Jeremie Allard | 318 | 146 | map.txt | 2004/11/21 08:11:56 | show solution | | Optimized for fuel. This should be the best solution if my calculations are correct... | show description (42 chars) |
| Randy Sargent | 318 | 146 | map.txt | 2004/11/21 09:11:06 | show solution | | Optimized for least fuel, selecting the least fuel path with least steps. | show description (45 chars) |
| Kevin Shepherd | 318 | 146 | map.txt | 2005/01/14 22:01:58 | show solution | | There are 7 optimal solutions of 108 solutions with this minimum fuel usage. 3293 secs on AMD64 2 GHz 2GB. C++ with maximum bit packing to keep memory usage down. | show description (34359 chars) |
| Matthew Ogilvie | 318 | 146 | map.txt | 2005/01/26 07:01:45 | show solution | | Run in direct optimization mode. Another one of the 7 optimal fuel solutions. 6 minutes (2.6GHz P4); approximately 1 GB memory used (some in swap). | show description (41 chars) |
| Randy Sargent | 325 | 146 | map.txt | 2004/11/21 09:11:47 | show solution | | Optimized for minimum fuel. ~3 hours programmer time, ~15 mins P4 3GHz CPU time. | show description (45 chars) |
| Kevin Shepherd | 325 | 146 | map.txt | 2004/12/29 21:12:59 | show solution | | Breadth first search based on fuel cost. Took over an hour on P3 833 MHz 512 MB mostly due to page faulting. C++ bit bashing to keep memory cost down. | show description (18093 chars) |
| Jeremie Allard | 307 | 147 | map.txt | 2004/11/21 08:11:52 | show solution | | Optimized for fuel. Used ~ 400 000 000 state evaluations with a peak active queue size of ~ 25 000 000 states. Took 20 minutes on an opteron and ~ 600 MB of RAM. Still searching for better solutions... | show description (42 chars) |
| Kevin Shepherd | 329 | 157 | random.txt | 2005/01/14 06:01:29 | show solution | | Upgraded to 2 GB ram. This solution used 750 MB. C++ 20 minutes. AMD 64 2 GHz. This is the only optimal step for fuel solution, there are 35 solutions with this fuel usage. | show description (30781 chars) |
| Kevin Shepherd | 338 | 157 | random.txt | 2004/12/30 00:12:42 | show solution | | Fuel, then step count, optimal solution. Takes an hour and a half on a P3 833 MHz with 512 MB memory. Almost all of the time in page faulting ( 1 GB would have held it all in-RAM ). C++ bit bashing code. Displays progress on the command line in ASCII maps. | show description (66863 chars) |
| Stefan Ram | 314 | 158 | map.txt | 2005/01/31 23:01:10 | show solution | | A genetic heuristics written in Java 1.5. It mutates and selects the robot control sequence. The program is very slow and will not find the best possible solution within reasonable time. | show description (486 chars) |
| Jeremie Allard | 282 | 169 | map.txt | 2004/11/21 07:11:32 | show solution | | Filled up most of my RAM (1Gig). | show description (42 chars) |
| David Finch | 282 | 169 | map.txt | 2004/11/21 08:11:38 | show solution | | I'm now shooting for 3rd place. Still took less than 500mb. | show description (11357 chars) |
| Randy Sargent | 282 | 169 | map.txt | 2004/11/21 09:11:15 | show solution | | Optimized for fewest steps. | show description (45 chars) |
| Allen Noe | 282 | 169 | map.txt | 2004/11/22 14:11:34 | show solution | | Best fuel usage at 282 steps. | show description (37 chars) |
| Kevin Shepherd | 282 | 169 | map.txt | 2004/12/31 03:12:00 | show solution | | Finally, the optimal solution. 35 minutes on P3 833MHz 512 MB. C++ | show description (27930 chars) |
| Randy Sargent | 291 | 169 | map.txt | 2004/11/21 16:11:22 | show solution | | New rules. No wall-braking allowed (for normal spacecraft, that would be called a collision!). The only interaction with the ground that's allowed is a "safe landing", which means that -1 <= xvel <= 1 and 0 <= yvel <= 2 before collision (and after gravity, thrust added), xvel=yvel=0 after collision, and that after collision both the lower left and lower right corners of the vehicle are above rock (ie if x,y are the upper left, then (x,y+10) and (x+9,y+10) are both rock). Using these rules, this soln optimizes for fuel. | show description (45 chars) |
| Allen Noe | 282 | 171 | map.txt | 2004/11/21 12:11:43 | show solution | | Improved fuel usage. | show description (37 chars) |
| David Finch | 288 | 171 | map.txt | 2004/11/21 10:11:24 | show solution | | If forced to take the lower path. | show description (92 chars) |
| Clarence Risher | 307 | 172 | map.txt | 2004/11/20 04:11:57 | show solution | | Trial and error for mostly minimal fuel usage. Made use of wall-braking | show description (105 chars) |
| David Finch | 282 | 176 | map.txt | 2004/11/21 06:11:16 | show solution | | Looks like Allen beat us to the prize for fewest steps. I managed to lower the fuel usage though. Took 400mb of my 512mb of ram and finished in about 2 minutes. | show description (11005 chars) |
| Randy Sargent | 285 | 178 | map.txt | 2004/11/21 16:11:05 | show solution | | Using "no crash" rules already described, optimizing for fewest steps. One correction to the "no crash" rules -- the path must end with a "safe landing" after touching the start location (no landing is required at the remote target). | show description (45 chars) |
| Jan Van den Bergh | 283 | 185 | map.txt | 2004/12/01 14:12:18 | show solution | | Codes in C++. Execution took about 3O minutes. | show description (116 chars) |
| Jan Van den Bergh | 283 | 185 | map.txt | 2004/12/01 14:12:55 | show solution | | Same solution, but with missing last zero. | show description (42 chars) |
| David Finch | 293 | 186 | map.txt | 2005/02/01 03:02:15 | show solution | | Still javascript. Added a wall hit penalty. | show description (189 chars) |
| Allen Noe | 282 | 187 | map.txt | 2004/11/20 21:11:32 | show solution | | Algorithmic solution, optimized for number of steps. | show description (37 chars) |
| Kevin Shepherd | 282 | 187 | map.txt | 2004/12/28 23:12:23 | show solution | | Takes ten minutes on a P3 833 MHz with 512 MB memory. C++ bit bashing code. Displays progress on the command line in ASCII maps. | show description (15859 chars) |
| Matthew Ogilvie | 301 | 189 | map.txt | 2005/01/26 08:01:37 | show solution | | Generated on 200 MHz PPro with only 64MB ram. Optimize relatively short subsequences of an initial rough solution (less effective optimization). 45 minutes. | show description (41 chars) |
| David Finch | 304 | 196 | map.txt | 2005/01/30 09:01:27 | show solution | | Just for fun. Ported to javascript, in the form of a web page. 13 seconds. | show description (397 chars) |
| David Finch | 292 | 198 | map.txt | 2005/01/27 07:01:55 | show solution | | 0.43 seconds. | show description (17 chars) |
| David Finch | 299 | 204 | map.txt | 2004/11/20 05:11:30 | show solution | | A manual solution, aiming for fewest steps. Still room for improvement. | show description (315 chars) |
| David Finch | 271 | 237 | random.txt | 2004/12/08 08:12:30 | show solution | | A bit easier than the other new maps. | show description (16352 chars) |
| Kevin Shepherd | 271 | 237 | random.txt | 2004/12/31 13:12:58 | show solution | | C++. There are four optimal solutions. It took 72 minutes page swapping plus ten minutes actual run-time. P3 833 MHz 512 MB. | show description (29979 chars) |
| Kevin Shepherd | 271 | 253 | random.txt | 2004/12/29 00:12:51 | show solution | | Takes twenty-five minutes on a P3 833 MHz with 512 MB memory. Mostly Page faulting ( need another 512 MB ). C++ bit bashing code. Displays progress on the command line in ASCII maps. | show description (21691 chars) |
| David Finch | 297 | 265 | map.txt | 2004/11/21 10:11:46 | show solution | | If forced to take the higher, narrow path | show description (67 chars) |
| Kevin Shepherd | 715 | 267 | big.txt | 2005/01/19 07:01:02 | show solution | | Six hours runtime AMD64 2GHz 2GB, plus days of re-optimizing memory footprint. There are two fuel optimal solutions. | show description (53186 chars) |
| Frank Buß (fb@frank-buss.de) | 338 | 305 | map.txt | 2004/11/05 18:11:16 | show solution | | This is a test solution with the "Play game" function of the Java application and moving by hand. | show description (12 chars) |
| Jan Van den Bergh | 358 | 321 | map.txt | 2004/11/29 15:11:02 | show solution | | Solution implemented in C++. Can still be optimized. | show description (178 chars) |
| Jason Goemaat | 342 | 327 | map.txt | 2004/11/22 07:11:01 | show solution | | Manual taking the narrow path, created with C# modified program | show description (381 chars) |
| Kevin Shepherd | 660 | 345 | big.txt | 2005/01/18 04:01:07 | show solution | | 10 optimal of 2219 solutions for minimal steps. C++ 3 hours on an AMD64 2 GHz 2GB ram. The key seems to be to minimize memory usage when storing states, after optimizing the algorithm. | show description (44333 chars) |
| David Finch | 733 | 431 | big.txt | 2004/12/08 08:12:36 | show solution | | 2.4ghz celeron, 512mb of ram, and some manual editing after waiting 1/2 hour and taking 5 months off the life expectancy of my HD to get a broken answer. Restricted to lower path. | show description (41109 chars) |
| Kevin Shepherd | 883 | 440 | random2.txt | 2005/01/29 13:01:40 | show solution | | This is the most fuel efficient solution I have found so far for this map. Took twelve minutes. | show description (86062 chars) |
| Kevin Shepherd | 689 | 600 | random2.txt | 2005/01/19 23:01:34 | show solution | | This is the best minimal step solution so far, the program is still running... | show description (57285 chars) |
| Kevin Shepherd | 1815 | 742 | big2.txt | 2005/01/27 07:01:42 | show solution | | The best fuel-efficient solution that the program has found so far. Runs faster by pruning unlikely branches from the search tree. | show description (68184 chars) |
| Frank Buß | 834 | 858 | random.txt | 2004/12/07 02:12:27 | show solution | | This is a test solution with the "Play game" function of the Java application and moving by hand. | show description (12 chars) |
| Frank Buß | 913 | 874 | big.txt | 2004/12/07 02:12:52 | show solution | | This is a test solution with the \\\"Play game\\\" function of the Java application and moving by hand. | show description (12 chars) |
| Matthew Ogilvie | 1755 | 879 | big2.txt | 2005/01/26 07:01:13 | show solution | | Same, but cost function tuned a bit more towards saving fuel. (18 hours) | show description (41 chars) |
| David Finch | 959 | 898 | random2.txt | 2005/01/27 07:01:15 | show solution | | My fast solver doesn't work as well on noisy maps. 2 seconds on a 2.4ghz celeron. | show description (234 chars) |
| Kevin Shepherd | 1646 | 962 | big2.txt | 2005/01/22 07:01:44 | show solution | | Took two days to calculate this solution. Thirty nine runs at one and a quarter hours per run. There may be better solution strings for different target order. | show description (64044 chars) |
| Matthew Ogilvie | 1694 | 974 | big2.txt | 2005/01/26 07:01:16 | show solution | | Optimize many subsequences (of length 27) of an initial rough solution. Use simulated annealing for target order. 16 hours on a 2.6 GHz P4. | show description (41 chars) |
| David Finch (dtfinch a t charter dot n e t) | 1677 | 1197 | big2.txt | 2005/01/25 08:01:08 | show solution | | Took 3.5 seconds this time, with slightly improved results. | show description (3742 chars) |
| David Finch | 1691 | 1238 | big2.txt | 2005/01/24 09:01:33 | show solution | | Took 8 seconds and very little memory to calculate. Heuristic solution. | show description (908 chars) |
| David Finch | 1776 | 1297 | big2.txt | 2005/02/01 03:02:37 | show solution | | Big map with the javascript solver. 4 minutes in Mozilla 1.7. | show description (118 chars) |
| Frank Buß | 2101 | 1905 | random2.txt | 2004/12/07 02:12:44 | show solution | | This is a test solution with the "Play game" function of the Java application and moving by hand. | show description (12 chars) |
| Frank Buß | 3063 | 3009 | big2.txt | 2004/12/07 02:12:19 | show solution | | This is a test solution with the "Play game" function of the Java application and moving by hand. | show description (12 chars) |
