Arctic Polar Explorer

The latest expedition to the North Pole has run into a problem. The autonomous Arctic Polar Explorer robot (APE) needs to reach a higher cliff, but it was never designed for that task. The scientists at mission control had to improvise, and they came up with a clever solution: the robot can climb the cliff by building its own staircase.

The APE's mission takes place in the Arctic Circle, where the terrain is covered with rocks, icebergs, and the occasional lost penguin. The APE has collected a number of rocks of different sizes, and its goal is now to move the rocks so that they become ordered by increasing size. The size of a rock is proportional to its weight. The rocks lie in a straight line, one rock per meter. The APE is currently standing next to the first rock, and the cliff is just past the last rock. The robot can move left and right, parallel to the line of rocks. Figure 3 shows one possible situation.

The only way to manipulate the outside world is through two arms with grippers that can pick up rocks. Unfortunately, there is no way to measure the weight of a rock. After another long brainstorming session, the scientists at mission control determined that the weights of the rocks in the grippers can be compared by measuring the tilt of the robot. If the robot tilts to the left, the left gripper holds the heavier rock, and if it tilts to the right, the right gripper holds the heavier rock.

Finally, the APE has very little memory, which makes writing programs for it rather difficult. All software for the robot is written in a specialized language, APECODE.

Figure 3: A sketch of one possible situation for the Arctic Polar Explorer. Here it holds a rock in the left gripper, while the right gripper is empty. There are five rocks, and the cliff is to the right.

You must write a program in APECODE. Other programming languages do not work on the Arctic Polar Explorer.