PUZZLER:
In this section, you'll meet a highly-simplified computer. It can be
programmed to perform a variety of tasks within limited capabilities.
The instruction set for the ROBOT computer severely restricts the kinds of movements it can make.
Nonetheless, you can create a sequence of instructions causing the ROBOT to move diagonally across its domain. Here is the ROBOT puzzler.
Write a program for the ROBOT that will cause it to begin at the upper right corner of the domain and proceed diagonally across the room until it reaches the lower left corner. The ROBOT should stop there with its arms down, facing a wall. Assume the room is square (x tiles by x tiles) and that there are no doorways.
|
|
| The ROBOT in It's Domain |
Most of the ROBOT's movements and capabilities are closely related to the characteristics of its domain. For example, when the ROBOT takes a step, it moves from one square floor tile to an adjacent tile. When it turns, it pivots its body but remains standing on the same tile. The ROBOT can never straddle two tiles or come to a stop standing on a line. Likewise, the walls limit certain activities of the ROBOT. They determine how far it can go in any one direction. Because the ROBOT's arms are exactly as long as the side of a tile, the ROBOT is unable to raise its arms if it is standing next to the wall it is facing. It cannot take a step if it is facing a wall and right up against it, unless it is in a doorway. A step through a doorway leads to destruction.
Although the ROBOT's room is always rectangular, its size is unknown to us at any given time. Itcan be any number of square tiles wide by any number of square tiles long. The rectangle may be a different size and shape for every different problem the ROBOT faces. The doors in the walls may be positioned differently, depending on the room's size. We can be certain in advance of only two things: first, that the room's dimensions will not change during the execution of the program and, second, that any doors present will never be located in the exact corners of the room.
The ROBOT's capabilities are defined by its hardware. For example, the ROBOT has no eyes or cameras built in; therefore, it cannot "see" its surroundings. It has no numerical capacity; therefore, it cannot count the number of squares or steps needed to reach a wall. This is a very minimal ROBOT - we cannot use it to perform a task that is beyond its capabilities.
External Hardware Features
The ROBOT is equipped with a special locomotion device at its bottom, where it comes in contact with the floor of its domain. This device allows the ROBOT to move from one square to an adjacent square within its domain. We refer to a single such action as a step. All steps are taken in a direction parallel to two walls of the room and in the direction that the ROBOT faces. Diagonal and reverse steps are not possible, nor can the ROBOT step sideways. The ROBOT can also pivot, but only to the right and only 90 degrees at a time - no more and no less.
The ROBOT has two mechanical arms - one at each side of its torso. An arm can be raised in front to shoulder height and lowered back to the ROBOT's side. When raised, the arm is at a right angle to the ROBOT's torso and parallel to the floor of the room. When the ROBOT's arm is extended, it reaches to the far edge of the next square in front of the ROBOT. (That is, the ROBOT technically occupies two squares when its arm is extended.) A consequence of this is that if the ROBOT is facing a wall and one square back from the wall, it cannot take a step forward because its arm is touching the wall in front of it. In fact, when the ROBOT occupies a square that is immediately adjacent to a wall, it is impossible for it to raise its arm. There just isn't enough room!
The ROBOT is equipped with special sensors, located at the ends of its arms. These devices are capable of sensing the presence of a wall when the ROBOT is positioned facing the wall, but one square back from it, with an arm touching the wall. The sensors activate if the ROBOT is directed to carry out the comand SENSE, which causes it to try to sense the wall.
Robot Characteristics
The ROBOT has no intelligence. It cannot think or plan its own activities. The ROBOT is capable only of ollowing a program of instructions that it retrieves from its memory and then executes, one instruction at a time.
The last sentece sounds simple enough but contains several difficult - and important - concepts. Let's analyze the internal hardware of the ROBOT a little more closely in terms of that statement. The ROBOT has a memory. In that memory are stored the instructions that make up a program. In addition the ROBOT is equipped with circuits, which enable it to fetch instructions from its memory, interpret or decode their meaning, and execute them. Let's define further all the terms printed in boldfaced type.
Memory - The ROBOT's built-in memory is quite tiny. It contains 32 memory locations, numbered consecutively from 0 to 31. Each memory location is capable of storing a single ROBOT instruction.
Instructions - The ROBOT does not understand human speech or any written language. It responds only to binary numbers, each eight bits (binary digits) in length. Each possible combination of the eight digits is a meaningful instruction to the ROBOT.
Fetch - The ROBOT's electronic circuits cause it to fetch (or retrieve) its instructions from memory, one at a time, and usually in the order in which they are stored. The only exception to this rule involves the GOTO command from the ROBOT's instruction set. For the full story, see the explanations of the individual ROBOT commands and the sample programs.
Decode - The ROBOT knows what action to carry out for a given binary number because the ROBOT's hardware contains an instruction decoder. Such a unit is present in one form or another in all digital computers. The instruction decoder is a set of circuits that causes the appropriate actions to be taken based on the particular binary number instruction that is received as input.
In most cases, the decoder circuits may be required to split apart a given binary number into two or more parts in order to interpret the instruction represented by the number. Each ROBOT instruction must be split into two segments. The first is the operation code or command part of each instruction is represented by the first three binary digits, starting from the left. The remaining five bits are ignored by the ROBOT except when used with the GOTO command.
Execute - The ROBOT executes the instructions by carrying out the action or command that each individual instruction represents. Each instruction has its own particular purpose and characteristics. Some instructions cause the ROBOT to take an observable action. For example, 00000000 causes the ROBOT to take one step forward. Instructions of this type may cause different results depending upon where the ROBOT is located; this is what makes programming the ROBOT both interesting and a little tricky. For example, if the ROBOT is directly in front of a wall, the 000000 instruction causes it to spin its wheels and wear them out, much to the detriment of the ROBOT and the wall!
Each ROBOT instruction consists of an eight-bit binary number. Up to 32 ROBOT instructions may be stored in the ROBOT's memory, one in each memory location. Thus, the maximum number of statements in any one ROBOT program is 32.
|
| A ROBOT Instruction |
Each ROBOT instruction consists of two separate portions or fields. The first three bits form the command, or opcode field. The opcode, or operation code, dictates the action to be taken by the ROBOT as a result of the instruction. The last five bits are almost always ignored, except in one instruction. These last five bits form the so-called argument or operand field, which is the address of a position in the memory. This argument or operand is extra information required in order to carry out the action indicated.
Robot Programs
The list of instructions, which the ROBOT has stored in its memory, can be determined and changed by the person who operates the ROBOT. The particular list of instructions that is currently stored is referred to as the ROBOT's program, and it must be placed into the ROBOT's memory before any execution can take place.
To place programs into the ROBOT, you must have some sort of access to the ROBOT's memory. On our ROBOT, the memory unit is located on the left side of its torso. A door on that side opens to allow access. Each memory location is represented by a row of eight toggle switches, in which one eight-bit binary number representing an instruction can be stored. When one of these switches is turned on, the bit in that position has a value of 1; when the switch is off, the bit has a value of 0 (zero). In this case, a bit is on when the switch is up and off when the switch is down.
< Need figure of switch panel here >
The process of setting the value in each memory location to conform to a particular program is referred to as loading the program. All computers must load programs before they can execute commands. When all the instructions of a program are loaded, the programmer close the door to the memory bay and presses the ROBOT's START button. The ROBOT can then begin to execute the program.
As noted earlier, there are exactly 32 memory positions. They are numbered from 0 to 31, using the binary numerals 00000 to 11111. The memory position numbers in the ROBOT's memory back start in the upper-left corner and are numbered down the first column and then onto the second column. When a program is executed, the instructions are performed in the order of step number, starting with the instruction stored at location 00000.
One of the ROBOT commands - the GOTO command - is designed to allow the ROBOT to take instructions out of normal order. This command or opcode has the binary code 101. When used within an instruction, its operand (the last five bits of the instruction) indicates the step number (memory location) from which the next instruction is to be taken.
Below is a table listing each value possible for the three-bit opcode of an instruction along with a single English word that suggests the action taken by the ROBOT command. Opposite each opcode is an explanation of the possible actions that can result from using that command in an instruction. We will refer to this set of commands as the ROBOT's instruction set.
Finally, the ROBOT is equipped with a special red warning light on top of its head. When the ROBOT's power switch is activated, the warning light is off, but certain situations cause it to be turned on. When the warning light is on, the ROBOT ignores all instructions except one, the one containing the LIGHT command. As we shall see, this feature gives the ROBOT a limited decision-making capability.
| Command | (English) | Action |
| 000 | (STEP) | The ROBOT takes a step forward if possible. If not, the ROBOT remains where it is. A step is considered to be impossible if the ROBOT faces a wall and is up against it with arms lowered or if ROBOT faces a wall and is one step away with arms raised. |
| 001 | (TURN) | The ROBOT turns 90 degrees to the right if it is able. It is considered unable to turn if there is a wall to its immediate right and its arms are raised. |
| 010 | (RAISE) | The ROBOT raises its arms if possible. If it cannot raise its arms, it turns on its warning light. If its arms are already raised, it does nothing. |
| 011 | (LOWER) | The ROBOT lowers its arms if they are raised; otherwise it does nothing. |
| 100 | (SENSE) | If the ROBOT's arms are raised and it is a step away from the wall it is facing, then this command will cause it to turn on its warning light. (It senses the wall.) In any other circumstances, the command is ignored. |
| 101 | (GOTO) | The ROBOT will take its next command out of normal order. (The last five bits of this command tell it from which memory location to take the command.) |
| 110 | (LIGHT) | If the warning light is on, this command causes the ROBOT to turn it off. Important note: When the warning light is on, the ROBOT ignores every instruction except LIGHT. Also, when the ROBOT first has its power switch turned on, the warning light is set to off. |
| 111 | (STOP) | The ROBOT shuts off its own power. |
| The ROBOT's Instruction Set | ||
The ROBOT languageis an example of a low-level language, also known as machine language. You should notice two distinctive features of this type of language:
PUZZLER HINT:
As you develop the algorithm for the ROBOT puzzler, remember that the
room could be eny size, so long as its square. So it might be 1 square
by 1 square, or 7 squares by 7 squares, or 23 squares by 23 squares.
Your solution must be general enough to accommodate any square room.
Don't forget to check for a wall before every step.
A good way to proceed is to use graph paper and draw your solution to help visualize the actions of the ROBOT. Remember that for our ROBOT to turn left, it must make three right turns.
A problem in the context of this discussion is a well-defined task to be performed by the computer.
An algorithm is a step-by-step process used to solve a problem. Essentially, the algorithm is the solution to the problem and is usually implemented by a program.
Now, let's first review a few key ideas from previous chapters: A program is a sequence of instructions designed to carry out a task. Well refer to a potential task for the ROBOT as a problem. The solution to the problem is provided by the program. However, to arrive at the program, we must proceed through fairly detailed logical thinking, and in so doing, devise a general method for approaching the problem. Such a method, expressed in clear and precise logical steps is called an algortithm. This term is one of the words most commonly used by computer scientists and programmers.
To illustrate these ideas, let's examine a series of problems for the ROBOT and then plan their solutions (algorithms). Finally, we will write the program that follows each algorithm.
Problem 1. Cause the ROBOT to walk to the wall it is initially
facing and then stop with its arms lowered and facing against the wall.
Assume the ROBOT is not initially facing an open doorway.
A few thoughts may occur to you during the process of solving this problem, or as we should say, creating the algorithm to solve the problem. Does stop mean turn off power or just come to a halt? Should we assume that the ROBOT's arms are lowered to begin with? How far is the ROBOT from the wall to begin with?
If you thought of any of these, pat yourself on the back! You are properly analytical. Let's establish some of the necessary ground rules by answering these questions:
Let us begin our problem analysis by addressing the last point: We don't know how far the ROBOT is from the wall. The obvious way to solve this problem is to count the number of squares to the nearest wall and then enter the program with the correct number of steps. A program that causes the ROBOT to stop at the wall if it is three squares away would be:
Binary Mnemonic -------- -------- 00000000 STEP 00000000 STEP 00000000 STEP 11100000 STOPIn other words, we could just instruct the ROBOT to take the correct number of steps and then stop. There are at least two difficulties with this: First, it won't work if the ROBOT is more than 31 steps from the nearest wall and second it it not very general. It will work only with a specified number of steps. We would have to write a separate program for every possible number of steps the ROBOT can be from the wall. A good algorithm or solution to the problem should be general.
What we are after is a single program that will work in all circumstances. Let's attack the problem of not knowing how many steps from the wall the ROBOT is to begin with. What if we could put one 00000000 (STEP) instruction in the program and get the ROBOT to repeat STEP until it gets to the wall? That way we wouldn't need to know exactly how far from the wall the ROBOT is to begin with. We need a way to make the ROBOT repeat an instruction. What we have in mind is called a loop.
The ROBOT has an instruction that will cause it to repeat some earlier instructions in a program. The opcode 101 (GOTO), followed by a five-bit address, causes the ROBOT to repeat a sequence of instructions starting at that address. Let's try the following program.
Memory Location Instruction Mnemonic Explanation -------- ----------- -------- --------------------------------------------- 00000 00000000 STEP Move forward one tile 00001 00000000 GOTO The next instruction is memory location 00000 00010 11100000 STOP Power-off
It certainly is short! The instruction at 00000 caused the ROBOT to step (does it always?), and the instruction at 00001 caused the ROBOT to go back and do step 00000 over again. Then the instruction at 00010 causes the ROBOT to stop. Well it sounds good. What's wrong with this program? Hint: There is more than one thing wrong!
Our second try certainly overcomes the objection to our first try regarding the distance to the wall. The second program does not put a limit on the number of times the 00000000 (STEP) instruction is carried out - and there is its difficulty. The first two instructions in this trial solution will be executed over and over and over and over and... This is an example of an infinite loop. There is no way to escape from the loop. Running this program is going to be hard on the ROBOT's batteries! Besides, when the ROBOT does reach a wall (and it could do that at any time), it will wear out its wheels tryin trying to take steps that are impossible.
We now seem to be caught in a dilemma. We need a loop to account for different distances to the wall, yet our proposed solution loops forever! We need some way to have the ROBOT stop as soon as it reaches the wall. Let's look back at everything we know about the ROBOT and see if there is any way it can "know" when it gets to a wall.
Reviewing the commands or opcodes in the table of instructions given earlier, we see that the opcode 010 (RAISE) causes the ROBOT to turn on its light if it is against the wall - just what we're after! In describing the ROBOT's characteristics, we promised that the ROBOT's warning light would give it a decision-making capability. Great, that's just what we need - a way to identify the wall and a way to decide when to escape from the loop.
Recall the way the warning light works: Once the light is turned on, the ROBOT ignores all instructions except for 11000000 (LIGHT). The 110 opcode tells the ROBOT to turn off the light. If the warning light is on for any reason, this is the only opcode that has any effect.
Getting the ROBOT Out of a Loop
Now, let's attack the problem again by using the 010 (RAISE) opcode to solve our dilemma. To get the ROBOT out of its deadly loop, one of the instructions inside the loop must sooner or later cause the warning light to be turned on. That instruction contains the 010 (RAISE) command. The ROBOT tries to raise its arms and cannot (because it is up against a wall), so the light goes on. When that occurs, the 101xxxxx (GOTO) instruction, which normally causes the ROBOT to begin repeating the loop (assuming the loop begins at a step number xxxxx), will be ignored because the light is on. The ROBOT will then execute the instruction following the 101xxxxx instruction, thereby escaping from the loop!
Here's the new program with both the binary machine language and the English language explanation about what the instructions do.
Memory Location Instruction Mnemonic Explanation -------- ----------- -------- --------------------------------------------- 00000 01000000 RAISE Try to raise the ROBOT's arms 00001 01100000 LOWER If it can, lower the arms 00010 00000000 STEP Move forward one tile 00011 10100000 GOTO The next instruction is memory location 00000 00100 11000000 LIGHT Turn off the light 00101 11100000 STOP Power-off, stop