# Lab 2: Herbie the Room Cleaning Robot

## Objectives

• To practice problem solving and algorithm design
• To practice simulating an algorithm for correctness
• To see that you can solve a harder problem using the solutions to easier ones, rather than to try and solve a very difficult problem from the start.

## Introduction

When using the computer to solve a problem, we must first describe or model the problem in a form that the computer understands. A problem model can be expressed as a picture, diagram, chart or table, for example. Since a computer cannot think in the way we humans do, we need to devise and describe a well-specified plan of what we want the computer to do. It is important to give a clear, concise problem statement. Your problem statement should specify what information is available to the computer for solving the problem (input), and what you expect the computer to provide as a solution (output).

The procedure by which we go from input to output is called an algorithm. An algorithm is a set of ordered, step-by-step instructions to solve the problem. An algorithm may be expressed in plain English, in a formal programming language (a program), or in pseudocode, which is a simplified combination of the two. In this lab we will write our algorithms in pseudocode.

When designing an algorithm, we assign names to input values and intermediate values used for computation which contain information we want to remember for later on. The names we use are called variables. A variable type describes the roles the variable can play and/or the values it can take on. Some examples of variable types are integers (int) and booleans (boolean). Boolean variables have two possible values: true or false. As you develop more complex algorithms, you will find it useful to write subroutines (or methods) that describe how to do one component of your main algorithm - think of a subroutine as a "sub-algorithm". Subroutines are generally used for a computation or function that is used several times by the main algorithm, and we assign names to subroutines just as we do for variables. We give a name to our main algorithm as well - we might end up using it as a subroutine when solving an even harder problem.

# Herbie

Herbie is a robot whose job is to walk around a room collecting dirty laundry. He must make sure that he has picked up all the dirty laundry in the whole room. Think about all the things that a real robot with this job would need to be able to do to accomplish this seemingly simple task.

For instance, how does Herbie know what laundry is? How does he know he has been all over the room? How does he deal with furniture in the room? What happens when his arms are full? We will consider much easier problems in this lab! The room that Herbie is in charge of will be modeled as a grid of squares surrounded by four walls. You can visualize the room as a three-dimensional checkerboard. We make the following assumptions:

• Herbie is in exactly one square of the room at a time.
• Herbie can only move forward one square at a time.
• Herbie can turn left and right.
• Herbie can only "see" the square immediately in front of him.
• Herbie is able to "see" if there is laundry in the square he is currently in, and if so, to pick it up and carry it with no problems.
• Herbie can distinguish if there is a wall in front of him instead of an empty square.
• There are no obstacles in the room.

We can define subroutines for Herbie's actions and senses given the above assumptions. You can use these subroutines when solving the problems below.

 These are the actions Herbie can perform: walk_forward() turn_left() turn_right() pick_up_laundry() These are the objects Herbie can sense or "see" boolean sees_wall() - returns true if Herbie is facing a wall and false otherwise (in which case there is an empty square in front of him) boolean sees_laundry() - returns true if there is dirty laundry in the square Herbie is standing in and false otherwise

Now let's write some room-cleaning algorithms for Herbie. Here is a example to get you started.

Example: Assume that Herbie is positioned in the upper left square of a 10x10 grid facing East. Write an algorithm that lets Herbie walk forward 5 steps, picking up any dirty laundry he encounters along the way.

Solution: Let's call our algorithm walk_five_steps()

walk_five_steps() { for k = 1 to 5 { if(sees_laundry() == true) pick_up_laundry(); walk_forward(); } }

As you can see, the algorithm is fairly simple. What particular information were we given in this particular problem that made the algorithm easy to formulate? For example, why didn't we have to worry about Herbie running into the wall? What would happen to poor Herbie if the room were of dimensions 4x4? Would the problem be harder if we had less information? Why or why not?

## Problems

For each of the following, write an algorithm to solve the problem. Do the problems in order, as you may find you can use your algorithm from a previous problem as a subroutine in the current problem. You may also write new subroutines if you like. Make sure that your main algorithm and all subroutines are well-specified. Identify what information you are given that is necessary to solve the problem, the variables you may require, and the condition(s) in which the algorithm terminates. Remember that a computer only knows what you tell it!

 Problem 1: Herbie is in a rectangular room of unknown dimensions and in some unknown part of the room, facing an unknown direction. Write an algorithm walk_to_wall() that makes Herbie walk forward until he sees a wall, picking up all the laundry he sees on the way. Make sure to consider as many possible cases that you can think of, for example, what if Herbie is in a 1x1 room? What if Herbie starts out facing the wall? Problem 2: Herbie is in a rectangular room of unknown dimensions, and he begins in the upper left hand corner facing East. Write an algorithm called oriented_cleansweep() for Herbie to clean the room of dirty laundry. In other words, Herbie should that visit every square in the room, picking up laundry as he goes. Problem 3: Herbie is in a rectangular room of unknown dimensions, and he begins in the upper left hand corner. The direction he is facing is unknown. Write an algorithm called unoriented_cleansweep() to have Herbie clean the room of dirty laundry. Hint: The only difference between this problem and the previous one is that we don't know which direction Herbie is facing. If you write a subroutine to first have Herbie turn and face East, you can then call your oriented_cleansweep() algorithm from Problem 2. Problem 4: Herbie is in a rectangular room of unknown dimensions and in some unknown part of the room, facing an unknown direction. Write an algorithm called cleanroom() for Herbie to clean the room of dirty laundry. Hint: Write a subroutine to have Herbie go to a corner, and use your algorithm from Problem 3. Extra Credit: Herbie is in a rectangular room of unknown dimensions and in an unknown part of the room, facing an unknown direction. Write an algorithm called smart_cleanroom() for Herbie to clean the room of dirty laundry and go back to the same place he started. This smart Herbie knows how to put himself away! Sorry, no hints for extra credit :-)