Submitted Solutions

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

Sort by date

NameStepsFuel UsageMapSubmit Date (y/m/d h:m:s)SolutionPathCommentDescription
Jeremie Allard318146map.txt2004/11/21 08:11:56show solutionOptimized for fuel. This should be the best solution if my calculations are correct...show description (42 chars)
Randy Sargent318146map.txt2004/11/21 09:11:06show solutionOptimized for least fuel, selecting the least fuel path with least steps.show description (45 chars)
Kevin Shepherd318146map.txt2005/01/14 22:01:58show solutionThere 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 Ogilvie318146map.txt2005/01/26 07:01:45show solutionRun 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 Sargent325146map.txt2004/11/21 09:11:47show solutionOptimized for minimum fuel. ~3 hours programmer time, ~15 mins P4 3GHz CPU time. show description (45 chars)
Kevin Shepherd325146map.txt2004/12/29 21:12:59show solutionBreadth 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 Allard307147map.txt2004/11/21 08:11:52show solutionOptimized 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 Shepherd329157random.txt2005/01/14 06:01:29show solutionUpgraded 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 Shepherd338157random.txt2004/12/30 00:12:42show solutionFuel, 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 Ram314158map.txt2005/01/31 23:01:10show solutionA 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 Allard282169map.txt2004/11/21 07:11:32show solutionFilled up most of my RAM (1Gig).show description (42 chars)
David Finch282169map.txt2004/11/21 08:11:38show solutionI'm now shooting for 3rd place. Still took less than 500mb.show description (11357 chars)
Randy Sargent282169map.txt2004/11/21 09:11:15show solutionOptimized for fewest steps.show description (45 chars)
Allen Noe282169map.txt2004/11/22 14:11:34show solutionBest fuel usage at 282 steps.show description (37 chars)
Kevin Shepherd282169map.txt2004/12/31 03:12:00show solutionFinally, the optimal solution. 35 minutes on P3 833MHz 512 MB. C++show description (27930 chars)
Randy Sargent291169map.txt2004/11/21 16:11:22show solutionNew 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 Noe282171map.txt2004/11/21 12:11:43show solutionImproved fuel usage.show description (37 chars)
David Finch288171map.txt2004/11/21 10:11:24show solutionIf forced to take the lower path.show description (92 chars)
Clarence Risher307172map.txt2004/11/20 04:11:57show solutionTrial and error for mostly minimal fuel usage. Made use of wall-brakingshow description (105 chars)
David Finch282176map.txt2004/11/21 06:11:16show solutionLooks 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 Sargent285178map.txt2004/11/21 16:11:05show solutionUsing "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 Bergh283185map.txt2004/12/01 14:12:18show solutionCodes in C++. Execution took about 3O minutes.show description (116 chars)
Jan Van den Bergh283185map.txt2004/12/01 14:12:55show solutionSame solution, but with missing last zero.show description (42 chars)
David Finch293186map.txt2005/02/01 03:02:15show solutionStill javascript. Added a wall hit penalty.show description (189 chars)
Allen Noe282187map.txt2004/11/20 21:11:32show solutionAlgorithmic solution, optimized for number of steps.show description (37 chars)
Kevin Shepherd282187map.txt2004/12/28 23:12:23show solutionTakes 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 Ogilvie301189map.txt2005/01/26 08:01:37show solutionGenerated 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 Finch304196map.txt2005/01/30 09:01:27show solutionJust for fun. Ported to javascript, in the form of a web page. 13 seconds.show description (397 chars)
David Finch292198map.txt2005/01/27 07:01:55show solution0.43 seconds.show description (17 chars)
David Finch299204map.txt2004/11/20 05:11:30show solutionA manual solution, aiming for fewest steps. Still room for improvement.show description (315 chars)
David Finch271237random.txt2004/12/08 08:12:30show solutionA bit easier than the other new maps.show description (16352 chars)
Kevin Shepherd271237random.txt2004/12/31 13:12:58show solutionC++. 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 Shepherd271253random.txt2004/12/29 00:12:51show solutionTakes 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 Finch297265map.txt2004/11/21 10:11:46show solutionIf forced to take the higher, narrow pathshow description (67 chars)
Kevin Shepherd715267big.txt2005/01/19 07:01:02show solutionSix 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)338305map.txt2004/11/05 18:11:16show solutionThis is a test solution with the "Play game" function of the Java application and moving by hand.show description (12 chars)
Jan Van den Bergh358321map.txt2004/11/29 15:11:02show solutionSolution implemented in C++. Can still be optimized.show description (178 chars)
Jason Goemaat342327map.txt2004/11/22 07:11:01show solutionManual taking the narrow path, created with C# modified programshow description (381 chars)
Kevin Shepherd660345big.txt2005/01/18 04:01:07show solution10 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 Finch733431big.txt2004/12/08 08:12:36show solution2.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 Shepherd883440random2.txt2005/01/29 13:01:40show solutionThis is the most fuel efficient solution I have found so far for this map. Took twelve minutes.show description (86062 chars)
Kevin Shepherd689600random2.txt2005/01/19 23:01:34show solutionThis is the best minimal step solution so far, the program is still running...show description (57285 chars)
Kevin Shepherd1815742big2.txt2005/01/27 07:01:42show solutionThe 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ß834858random.txt2004/12/07 02:12:27show solutionThis is a test solution with the "Play game" function of the Java application and moving by hand.show description (12 chars)
Frank Buß913874big.txt2004/12/07 02:12:52show solutionThis is a test solution with the \\\"Play game\\\" function of the Java application and moving by hand.show description (12 chars)
Matthew Ogilvie1755879big2.txt2005/01/26 07:01:13show solutionSame, but cost function tuned a bit more towards saving fuel. (18 hours)show description (41 chars)
David Finch959898random2.txt2005/01/27 07:01:15show solutionMy fast solver doesn't work as well on noisy maps. 2 seconds on a 2.4ghz celeron.show description (234 chars)
Kevin Shepherd1646962big2.txt2005/01/22 07:01:44show solutionTook 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 Ogilvie1694974big2.txt2005/01/26 07:01:16show solutionOptimize 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)16771197big2.txt2005/01/25 08:01:08show solutionTook 3.5 seconds this time, with slightly improved results.show description (3742 chars)
David Finch16911238big2.txt2005/01/24 09:01:33show solutionTook 8 seconds and very little memory to calculate. Heuristic solution.show description (908 chars)
David Finch17761297big2.txt2005/02/01 03:02:37show solutionBig map with the javascript solver. 4 minutes in Mozilla 1.7.show description (118 chars)
Frank Buß21011905random2.txt2004/12/07 02:12:44show solutionThis is a test solution with the "Play game" function of the Java application and moving by hand.show description (12 chars)
Frank Buß30633009big2.txt2004/12/07 02:12:19show solutionThis is a test solution with the "Play game" function of the Java application and moving by hand.show description (12 chars)

02. Nov 2005, Frank Buß