This programming challenge is sponsored by Dr. Dobb's Journal and Frank Buß (CEO of IT4 Systems GmbH & Co. KG).
"Mayday, mayday!" the pilot is calling in the radio, "we explored the new cave in the Elysium region, near the pyramid and suddenly an electromagnetic pulse destroyed most of our ship electronics and we crashed. If someone on Earth station can hear us, please help us!"--then the signal disappeared in noise. This was one hour ago and you are listening from Mission Control Center on Earth. The only way to rescue the crew is to program a flying mining robot to fly to the crashed ship, pick it up, and fly back to the Mars base camp. Because of the delay of several minutes from Earth to Mars you have to program all commands to turn on/off the jets of the robot in advance. Good luck!
You have a map like this as input:
37 12 ##################################### # # # # # # # # # O # ############ ################## ############# ###### ## ############# #### + ### ############## ##### ################### ###### #####################################
The first two lines are the width and height of the map. The next lines are the map, where the start is at "O" and the crashed ship target is at "+". Empty fields are spaces and all other chars are interpreted as stone. Newline is the MS-DOS newline (\r\n: 0x0d followed by 0x0a).
The robot starts at the start and has three jets--on the left, right, and bottom. For every step, you have to specify the on/off state of the jets: 1 for the left jet, 2 for the bottom jet, and 4 for the right jet. When ORed together, the results is a list of numbers from 0 to 7. You have to fly to the target, touch it, and then fly back to the start, touching it. One solution for the example above looks like this:
2644664000000002222220222022222001131003222222202222000000000000
If you have a Flash player version 4 (or greater) installed, you can see the animated solution (was created with JavaSWF2 and a small Java program):
The moving rules are straightforward. Every cell on the map, the robot, and the target are 10x10 pixels in size. The coordinates starts at top left and count to bottom right, so the coordinates of the top-left corner of the robot is (40, 50) and the coordinates of the top-left corner of the target is (320, 80). Every step a speed vector is added to the coordinates of the robot. The x- and y- component of the speed vector are integers >=-10 and <=+10. Every step the gravity increments the y-component of the speed by one. If you enable the left jet, the x-component is decremented by 2, the right jet increments it by 2 and the bottom jet decrements the y-component by 2 of the speed vector. After this the speed vector is added to the coordinate, but only, if the new coordinate does not hit a stone after adding the speed. If a stone is hit, the speed vectors are divided by 2 (integer division without fraction) as long as no stone is hit (which can result in a speed vector of (0, 0)). Hitting a stone is calulated by checking if one or more of the four corners of the robot lies within a stone. Moving to coordinates <0 or >= the size of the map counts as a hit.
It is sufficient to hit the target (the target "hit" definition is the same as hitting a stone), you don't need to land at the exact position. After this you have to hit the start position.
The Java reference application implements the moving algorithm, you can load maps and you can test your solutions (MarsRescue.zip). You can recompile it with Ant or you can just start it by double clicking on the mrescue.jar file or the run.cmd file (perhaps you need to include java.exe in your path on Windows). For starting it a Java Environment with version 1.4 or greater is needed.
If you don't have a GUI or Java, you can download a reference implementation of the moving algorithm in Common Lisp (mars.lisp.txt). It should run in every Common Lisp implementation. The "run-solution" function prints the coordinates and speed vector for each step, like in this table, which was generated with the demo map (download it in text form). At the end the number of steps and the required fuel are printed. The fuel is calculated by counting all jet activations. The example above has 64 steps and a fuel usage of 42. The Lisp program works only for single targets, not with big2.txt and random2.txt, but it should be easy to enhance it.
You can generate an image of the path with marsimg.cpp. Download a precompiled version for Windows or for Linux. The program generates small images and large images. This is the image of my test solution of the challenge map:
The black line is the path to the target and the red line back to start. Click on the image to view the large version.
For the challenge you have to use this map. There are five prizes (the CD is Dr. Dobb's CD/Release 16, which includes archives of the journal from January 1988 to December 2004):
In short, it doesn't matter how do you solve the challenge. You can use the Java program and try it by hand with the cursor keys, or you can write a sophisticated program in your favorite computer language or perhaps using some mathematics to find the proveable best solution.
Looks like the challenge map was too easy, so there are some more maps, which can be used for exceptional solutions:
To solve the maps with multiple targets, you start as usual, but you have to touch every target and then fly back to the start. When submitting, you can specify the map you have used. I've updated the Java program to test it, too.
But don't limit yourself to these maps. A good idea would be to enhance the Java program, because it is not very optimized for such large maps (perhaps with scrolling, faster movements etc.). Or create better maps and solutions.
The challenge is over, click here for the winners list and a list of all authors, solutions, steps/fuel counts, images of the solution paths and the solution programs.
I created this challenge, because the previous challenge was fun, with many nice solutions and I expect the same for this challenge. The idea is influenced by the ICFP contest but the rules of this challenge are a bit different and easier to help focussing on the algorithm and not the movement calculations and physics.
For discussions take a look at the Slashdot article.
