Core S2 Software Solutions

Mars Rover Programming Challenge for Non Programmers

Awhile ago, during a required High School senior project, I was introduced to a neat programming question that wasn’t really a programming question. It’s a sort of “can you be a programmer” question without any sort of experience or knowledge needed from formal education. This kind of question goes along an idea introduced by an academic paper about how some people are naturally inclined to become good programmers, similar to many other skills we might be “naturally good at”. The paper is linked and well described on Jeff Atwood’s Coding Horror blog; one of my favorites.

Problem Description: The Mars Rover Program
Difficulty: 1/3
Note: Anyone can solve this, it’s not really a true programming problem

You have just been hired by NASA to program two robots to land on mars. The good news is that they are sending two of the exact same robots, the bad news is that because of financial problems, both robots will have the exact same programs put on them (same computer, same hardware, and exact same instructions on each, but two separate execution paths but executed at the same time). Your goal is to write a program such that when the two robots land (it is known they land next to each other), they must eventually (within reasonable time) move in oposite directions (i.e. one moves towards north, the other towards south). You do not want them to follow each other.

The “Mars” world can be described as a one-dimensional plane (i.e. left and right), where both robots start executing their programs on landing platforms. Robots only move in single meter steps, so imagine that the world has markers every meter in both directions. There is no origin or “0” location on these meter-based distances. Do not take into account that the robots could eventually circle the planet and intercept; assume the battery lives are not good enough. These robots can move on and off the platforms as many times as they want. You can also assume both robots start near each other, but in any order (i.e. robot one may or may not be to the left of or right of robot 2). In total, when the program starts executing, there will be two robots and two landing pads; the landing pads are assumed to always be where the robot is when the code starts.

The programing language is of a linear paradigm (no functions, just instructions execute one after the other, starting at line 1, much like assembly). The instructions are as follows:

  1. MOVE_LEFT – Moves the robot to the left (north)
  2. MOVE_RIGHT – Moves the robot to the right (south)
  3. IF_ON_PLATFORM – If the robot is currently on the capsule, the next instruction is executed, if not on the capsule, the second to next line is executed. This of this as a single line if-else. The second to next line is ignored if the conditional was true (See example).
  4. GOTO # – Jumps to the given line.

The following is a sample program that moves the robot two steps to the left, one step to the right, and then repeats infinitely; this is a very convoluted way to moving left, but is only a sample piece of code.

  4. GOTO 1

The following is another piece of sample code. This code moves the robot towards the left off a ramp, but then does nothing (does a busy wait). The first instruction checks if the robot is on the landing platform; if it is true, it immediately executes the next line which moves the robot to the left. If the robot is not on the platform, then the program just immediately moves back to the top of the code. Simply put: If on platform, goto instruction 2, skips instruction 3, else if not on the platform, skips instruction 2, goto intruction 3.

  3. GOTO 1
  4. GOTO 1

My final hint is that the solution is 6 instructions long and is quite easy, but you will have to make sure the first instruction moves the robots off the platforms (this is quite a massive hint).

Did you attempt a solution? What did you get; did you write an algorithm? The idea with this question is that a group people without programming experience generally split down the line: one part of the group eventually finds a general algorithm (written as words, and then transcribed to code) while the other group struggles quit hard and never can quite get the right answer. Again, why is this? I would recommend reading the link provided at the top of this article, but simply put: some people can immediately grasp logical control systems found in modern programming languages such as loops and conditionals, wile other are very unaffordable with the idea. Though, this is not meant to discourage people who don’t feel comfortable programming for the first time: from my experience tutoring, there is always an analogy, example, or different approach you can use to learn or teach programming primitives. (i.e. “algorithms are like instructions”, “processors read instruction books you write”, “computer memory is like a processors scratch-pad for work”, etc..)

So, onto the solution! It is 6 instructions long and uses two programming primitives: the if-else conditional block, and a while-true loop (or infinite loop). The first step (instruction 1) moves both robots left. If this new position (instruction 2) is on a platform, we execute instruction 3, else, instruction 1. This simple fork moves us to two different blocks of code: if true (i.e. we are on a platform), we execute line 3 which moves us to the block 5 and 6. These two instructions are an infinite loop: move right, and repeat. If we weren’t on a platform, we are told to jump to the top of the program, move left again, and repeat…

  3. GOTO 5
  4. GOTO 1
  6. GOTO 5
Why this infinite loop going right? It isn’t hard to understand at all: when both robots start, they keep moving left. The left-most robot  will never touch another platform again, so it can continue going left because the second platform is on its right. The second robot who did start on the right platform will eventually touch the left platform, simply because it started on the right. Since it does touch the platform, the robot now knows that the left robot is going left, so it must now only go right. We enter this “right only” infinite loop because we don’t want to check for other platforms (the right robot will eventually tough the right platform, its starting poing, again at some point again). Also note that the first instruction always moves the robots left, because if we immediately checked for platform existence, then both robots would go infinitely right, which is an incorrect behavior. Finally, there are technically two solutions, but the second one is where you interchange all move-left to move-right, and move-right to move-left. The starting directions are arbitrary, as long as the opposite-direction loop is set in the opposite direction as the robots start.
Pretty neat question to ask non-programmer friends, one of my favorites!
This entry was posted in News & Updates. Bookmark the permalink.

One Response to Mars Rover Programming Challenge for Non Programmers

Leave a Reply

Your email address will not be published. Required fields are marked *


Sites map