CS21 Lab 8: Searching

Written portion: due in class Thursday, April 5 or Friday, April 6

Programming portion: due Saturday night, April 7, before midnight

Make sure all programs are saved to your cs21/labs/08 directory. Files outside this directory will not be graded.

$ update21
$ cd ~/cs21/labs/08

Goals

practice reading data from a file
use a list of lists to store the data
understand when linear and binary searches should/can be used

Topics for this assignment

linear search and binary search
top-down design
reading from files
lists of lists

1. Searching worksheet

The first part of the lab involves you tracing linear and binary searches on a list. This is excellent practice for what will almost certainly be a question on quizzes and the final exam!

Download the PDF, print it out, and turn it in at the start of class on either Thursday (Meeden) or Friday (Fontes/Soni).

2. Zoo information

Overview

This week's lab involves zoo animals. Your program zoo-info.py will help the user learn interesting information about animals they might see at a zoo.

The file /usr/local/doc/animals.data contains data about animals often seen at zoos. (It is a simplified and edited version of this dataset.)

Here are the first few lines:

aardvark,1,0,0,1,0,0,4,0
antelope,1,0,0,0,0,0,4,1
bass,0,0,1,1,0,1,0,1
bear,1,0,0,1,0,0,4,0

Each line contains the information for some creatures you might see in a zoo. The lines in the file are in alphabetical order based on the name of the creature.

Here's a handy chart for what the different data entries mean:

animal name
has hair? 1 if yes, 0 if no
has feathers? 1 if yes, 0 if no
makes eggs? 1 if yes, 0 if no
predator? 1 if yes, 0 if no
venomous? 1 if yes, 0 if no
fins? 1 if yes, 0 if no
number of legs? (an integer from the set {0,2,4,5,6,8})
tail? 1 if yes, 0 if no

You will write a program (zoo-info.py) that reads in the animal data and allows the user to explore this dataset, to learn in preparation for a visit to the zoo. You will implement a simple text-based menu system that allows the user to search through the data for either the name of the animal (exact match), or any animal with a number of legs in a user-chosen range (e.g., 4-6 legs). When the program quits, it should list all the highly dangerous animals (those that are predators and venomous --- this is a warning for the user!).

Sample output for `zoo-info.py`

Here is an example of the program (another, longer example is at the bottom of the page):

$ python3 zoo-info.py
======= Information on Animals at the Zoo =======

=================================================
(1) Animal name (2) Number of legs (3) Quit : 1
search for: leopard

            name: leopard
            hair: True
        feathers: False
            eggs: False
        predator: True
        venomous: False
            fins: False
  number of legs: 4
            tail: True
       dangerous: medium

=================================================
(1) Animal name (2) Number of legs (3) Quit : 2
Minimum number of legs: 5
Maximum number of legs: 8

    animal  # legs
    ------  ------
 butterfly   6
  crayfish   6
      flea   6
      gnat   6
  honeybee   6
  housefly   6
  ladybird   6
   lobster   6
      moth   6
   octopus   8
  scorpion   8
    spider   8
     squid   8
  starfish   5
   termite   6
      wasp   6

=================================================
(1) Animal name (2) Number of legs (3) Quit : 1
search for: seaSNAKE

            name: seasnake
            hair: False
        feathers: False
            eggs: False
        predator: True
        venomous: True
            fins: False
  number of legs: 0
            tail: True
       dangerous: high

=================================================
(1) Animal name (2) Number of legs (3) Quit : 3

=================================================
Warning! The following animals are very dangerous,
do not attempt to hug them at the zoo:
      centipede
      frog
      jellyfish
      pitviper
      scorpion
      seasnake
      seawasp
      spider
      stingray

Have a fun visit to the zoo!

To get the information required in this program, you will (obviously) have to search through the animal information. For the first type of search (searching for data about a specific animal), you can (and should!) use binary search. For many of the other parts, since the data is only sorted alphabetically by animal, you will have to use a linear search. You are not allowed to use any of Python's built-in search functions to do the animal search or the search by number of legs.

Requirements and tips

Here are the specifications for this program and a few helpful tips. Make sure your program meets all of these specifications.

You should use top-down design for this program! Design your main() function and any helper functions. Your main() function should be relatively short and easy to read. Implement and test the program one function at a time. A good program design and good use of functions is part of the grade.
Read in all the data for all animals and store it in a list-of-lists, like this:
```
[[data for animal 1], [data for animal 2], ...]
```
Here's what the inner lists for each animal should contain:
```
[animal name, hair, feathers, eggs, predator, venomous, fins, number
of legs, tail, dangerous]
```
The data for each animal should be stored in the correct format. For example, the name should be a string, the number of legs should be an integer, and the "feathers" attribute should be a boolean value (True if the animal has feathers, False otherwise).

Here's a real example:
```
['giraffe', True, False, False, False, False, False, 4, True, 'low']
```
You need to figure out how to calculate the "dangerous" item in the list using the other information. The dangerous attribute should be:
- 'high' if the animal is a predator and venomous
- 'medium' if the animal is only a predator
- 'medium' if the animal is only venomous
- 'low' otherwise
Refer to your class notes, exercises, and the assigned reading for tips about storing and retrieving data in a list of lists, and reading and parsing data from files.
You are free to format the output of your program any way you want, but it should be clear, concise, and easy to read.
When asking the user for an animal, your program should display all information for the user-chosen animal. This should work independent of case (i.e., "kiwi" or "Kiwi" or "KIWI"). If the animal is not listed in the data, your program should say that.

To convert a string to a different case, you can use the .lower() or .upper() methods, which convert the string to all lower or upper case, respectively.
You are not allowed to use any of Python's built-in search functions to do the animal search or the search by number of legs.

We highly recommend that you show your design to an instructor or ninja before you start to implement this lab. You don't need to submit your design as a separate document.

Here is another example run of the program, with a variety of user inputs.

Submit

Once you have fully tested all your functions and are confident your program works, fill out the questionnaire in QUESTIONS-08.txt. Then run handin21 a final time to make sure you have submitted the most recent version of your file.