Mars Rescue Mission Challenge

This programming challenge is sponsored by Dr. Dobb's Journal and Frank Buß (CEO of IT4 Systems GmbH & Co. KG).

The story

"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!

The technical details

Input

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).

Output

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):

Moving Rules

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.

Java and Common Lisp reference implementations

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.

Image generation of the solution path

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.

The Challenge

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):

• A CD for the shortest solution (this means the shortest solution string).
• A CD for the most efficient fuel usage (the solution with the lowest number of jet activations).
• Three CDs for exceptional solutions. For example, if you generalize the solution to 3D and implement a robot that spin and has additional jets. Or with a map with multiple targets, proving P=NP for the traveling salesman problem. Or create a raytraced movie from the solution, or build the solution as real hardware for a device which you use to get you some food from the kitchen. Or just for an elegant solution, or a program, which solves all maps, including the new ones (see below). Or a program, which is very reliable, readable and maintainable, for example a little framework, which can be used to write solving algorithms for problems like this without much code.

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.

New maps

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.

Challenge Result

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.