Home‎ > ‎CIS 98‎ > ‎

Lab 3: Understanding Algorithms


The purpose of this lab is to program Frodo, an imaginary robotic Hobbit with a limited instruction set, to perform simple tasks in an elegant manner.

Introduction

In this lab you will use two new concepts, function libraries and conditional execution. 

Function Libraries

A function library is code you have written that can be used by multiple programs. It's boring to rewrite your functions in every program so you should avoid it. Creating a function library is easy. Simply create a new file (in your lab directory) with a name of your choosing. In that file add your functions. For example:

# ~/lab3/functions
# This is Mike's function library
# turnleft - a function that turns Frodo to his left
turnleft() {
  turnright
  turnright
  turnright
}

Now that you have your function library you must include it when you run your lab program. This assumes the function library is in the same directory as your program. That is important because of the way the grading program works. 

# ~/lab3/prog3.1
# This is Mike's Lab 3 Problem 1

# Include my functions
. functions

turnleft 
turnleft 

When you execute your program the functions in your function library are available!

frodo -m map3.1 prog3.1

Conditional Execution 

So far your programs have not had to make any decisions. They've run from beginning to end the same way every time. This is not normal for programs which usually make zillions decisions. In this lab I introduce the most basic syntax for decision making. You will have to use this syntax in the third part of the lab. In order to understand decision making you must first understand the computer's logical operators AND and OR. 

Logical Operators

The computer uses logical operators to make decisions. Logical operators are described by truth tables. Below are the truth tables for AND and OR, two of the three fundamental logical operations:

Logical AND
 Input A Input B Output 
 false false  false 
 false true false
 true false   false 
 true   true true

Logical OR
 Input A Input B Output 
 false false  false 
 false true true
 true false   true 
 true   true true

Programming with Logic

Frodo is a machine and he's compelled to try make statements true. Frodo also has basic functions that can ask true or false questions:
  • is_clear Frodo uses his forward camera to tell if the path is clear or blocked. The instruction returns "true" or "success" if the way is clear, and "false" if the way is blocked. This instruction takes an argument of RIGHT or LEFT to determine if the path is clear to his immediate right or left respectively.
  • next_to_ring Frodo uses a metal detecting sensor to tell if there are any rings located on the block where he is standing. The instruction returns "true" or "success" if there is at least 1 ring for him to pick up, and returns "false" if there are no rings within his reach.
  • any_rings Frodo uses a sensor to tell if there are any rings located in his ring-bearing bag. The instruction returns "true" or "success" if there is at least 1 ring in his bag, and returns "false" if there are no rings in his bag.
  • at_origin Returns success (true) if Frodo is at the origin, Square (0,0); otherwise, failure.
Frodo can use his next_to_ring sensor to make a logical decision: 

next_to_ring && <some-command-here> 

You read this statement like, "Next to ring AND move." Frodo will determine if he is next to a ring, if so he will make the statement true by executing whatever command is on the right side of &&. If he is not next to a ring there is no way to make the statement true so Frodo will give up and not execute the command. Here's how to do the opposite:

next_to_ring || <some-command-here>

You read this statement like, "Next to ring OR move." Frodo will determine if he is next to a ring, if not he will make the statement true by executing whatever command is on the right side of ||. If Frodo is next to a ring then the OR statement is already true so Frodo will save effort and not execute the command. 

Problem 1

Frodo is faced with Mt. Doom again. But this time, Frodo must gather up all the rings on the mountain and deposit them at the foot of Mt. Doom in square x=1, y=0. After putting the rings down, Frodo must go back to the origin (square 0, 0) and turn himself off. In writing this program, use a function library and include appropriate functions that will reduce the repetitive nature of this task. 

$ frodo -m map3.1


Problem 2

This is the Field of Rings problem. Frodo must gather up all the rings and then turn himself off. The challenge in this program is to keep the body of the program small and easy to understand what the program is doing. You do this by making appropriate functions. Try for no more than a dozen instructions in the body of your program. You may use your function library. Notice the starting point and direction of Frodo.

$ frodo -m map3.2

Problem 3

Modify the Field of Rings program from above so that it will not execute any error shutoffs if some of the rings happen to be missing. I reserve the right to decide which rings I will remove from the field; your program should go to completion regardless of the number of rings actually present.

Example: An Incomplete Harvest

$ frodo -m map3.3

Turn In

When you are done with your programs, copy prog3.1 and prog3.2 to a subdirectory named lab3 in your home directory. Be sure your function library is in there!

Grading

You programs are graded on clarity, completeness and correctness. 
  • 10 points for prog3.1
  • 10 points for prog3.2
Comments