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!