Section 0

To me programming is more than an important practical art. It is also a gigantic undertaking in the foundations of knowledge. — Grace Hopper

Agenda

• Introductions
• How to contact the course staff
• Highlight practice tests on the Lectures page
• Exercises

Practice with Picobot

1. Open the Picobot simulator, and replace the default program with the following program:

   0 ***x -> S 0
   0 ***S -> X 1
   1 **x* -> W 1
   1 **W* -> X 1
   

2. Press the button labeled Enter rules for Picobot.

3. Do not press Go! Rather, press the Step button repeatedly. As you do so, watch what happens to Picobot, as well as to the values shown in the State and Surroundings boxes that appear below the control buttons.

   As you do so, come up with answers to the following questions:

   1. When does the State change from 0 to 1? Why does this make sense?

      The state changes from 0 to 1 when Picobot reaches the wall at the bottom of the room. That makes sense because the first rule only applies when there is no obstacle to the south (since there is an x for south), and thus when it reaches the wall at the bottom, it follows the second rule (which has an S for south), which causes it to transition to state 1.

   2. What happens if you continue pressing Step after the State changes to 1?

      It moves west, following the third rule, until it reaches the West wall.

   3. When does Picobot stop moving completely, even if you keep pressing Step?

      It stops in the lower-left corner.

   4. What does this program do in general? (You may want to try re-running it a few times by pressing Reset and then either Step or Go.)

      It brings Picobot down to the South wall and then over to the lower-left corner.

4. Let’s say that we want to modify the previous program so that Picobot will: (1) perform the same initial motions as before, and (2) continue moving until it reaches the upper-left corner of the room.

   Your classmate suggests adding the following rule after the existing ones:

   1 x*W* -> N 1
   

   However, the resulting program is not valid for two reasons:

   • There is a repeat rule.
   • Picobot will not actually make it to the upper-left corner.

   Add this new rule after the existing ones and click Enter rules for Picobot. Read the error in the Messages pane. Why is this error occurring – in other words, what is a repeat rule?

   A repeat rule is a rule that applies in circumstances where a previous rule would also apply.

5. Fix the program so that it is valid (so that there are no repeat rules) and has the desired behavior.

   Here is the fixed program, with changes to the last two rules:

   0 ***x -> S 0
   0 ***S -> X 1
   1 **x* -> W 1
   1 N*W* -> X 1
   1 x*W* -> N 1
   

6. Write a Picobot program that makes Picobot trace a border around the edge of the map (it should look like a gray border inside of the blue border, perhaps with some additional gray lines).

   There are potentially many answers to this problem. One way of drawing a border around the map is to use the following algorithm:

   1. Regardless of where Picobot begins, move it to the east wall.

   2. Move Picobot all the way north along the east wall.

   3. Move Picobot all the way west along the north wall.

   4. Move Picobot all the way south along the west wall.

   5. Move Picobot all the way east along the south wall.

   6. Move Picobot all the way north along the east wall.

   Note that since we don’t know where Picobot begins, we need to move Picobot all the way north in both steps (b) and (f) to make sure a border is created all the way along the east wall.

   One Picobot program that accomplishes this task is:

   # Move all the way east.
   0 *x** -> E 0
   0 *E** -> X 1
   
   # Move all the way north, and continue.
   1 x*** -> N 1
   1 N*** -> X 2
   
   # Move all the way west.
   2 **x* -> W 2
   2 **W* -> X 3
   
   # Move all the way south.
   3 ***x -> S 3
   3 ***S -> X 4
   
   # Move all the way east.
   4 *x** -> E 4
   4 *E** -> X 5
   
   # Move all the way north, and stop.
   5 x*** -> N 5
   5 N*** -> X 5
   

Last updated on June 23, 2025.