Department of Mathematics and Computer Science

Machine Problem 1

Math 61 D. C. Smolarski, S.J. Winter, 2000

Data Structure Concept: ARRAYS

30 points
DUE: Noon, Thursday, January 20, 2000

+-----+-----+ | | | | 1 2 | | | | +-----+- -+- -+-----+ | | | | | | 3 4 5 6 | | | | | | +-----+- -+-----+-----+ | | | 7 | | | +-[D]-+

The floor plan for the Insect Lab of a school's Biology Building is shown on the left. A mad professor let his experiment get out of hand, and the entire lab has been infested with billions and billions of killer bees, which must be exterminated.

Two senior biology majors, lovingly known as "Bee Busters," have been assigned the job, and they stand ready to enter the lab. The only way into the lab is via the door to cubicle 7 ([D]). The exterminators carry a great deal of paraphernalia, so THEY CANNOT SIMULTANEOUSLY OCCUPY THE SAME ROOM.

The door is opened, and one of the exterminators rushes through room 7 and into room 4, while the second exterminator follows behind, into room 7. The door is slammed shut behind them. The first exterminator sprays his room (4) and the second sprays his (7), immediately killing all of the bees in those two rooms. (Both of the "Bee Busters" are understandably frightened, and after either one sprays a room they are sometimes both heard to mutter, "Look out! I hear something").

For this problem, you are to read a list of proposed moves for the exterminators. Each move is given as a pair of room numbers, <old room number> <new room number>. The list may, however, include some illegal moves. The illegal moves are of two kinds: (1) an attempt to move from one room to another which is not adjacent (as from from 3 to room 7), or (2) an attempt to move into the room which is occupied by the other exterminator. Your program must reject these illegal moves (and print something appropriate). You should assume that the exterminators start out in rooms 4 and 7, respectively. The input list is in file bees.inp, available at this link or found in my Ma61 subdirectory on math, via the following command:

     math 34:cp /home/dsmolars/ma61/bees.inp .

This program should be written in C++ and should represent the biology lab using several elementary data structures, namely ARRAYS.

My suggestion is that you use the following structures. The first, representing the passages from room to room, is an adjacency matrix, i.e. a two-dimensional array, e.g., passage[7][7] which is either of type bool or int. It is initialized so that passage[i][j] = true or 1 if there is a passage from room i+1 to room j+1. (Note, since the array can NOT have the subscript 7 and there is no room 0, it is best to associate room i+1 with subscript i.) The second data structure, representing the locations of the bees, is merely a vector, i.e., a one-dimensional array, e.g., room[7], which also is either of type bool or int. It is initialized so that room[i] = true or 1, if there are bees in the room. Initially, there are bees in all the rooms, but as soon as the "Bee Busters" enter the Lab, the bees in room 7 and 4 are eliminated. It might also be helpful to have a data structure to keep track of the location of the "Bee Busters," iextrm[2], a one-dimensional array (vector), whose value indicates the room an exterminator is in, e.g., iextrm[1] equaling 4 indicates the 2nd (i.e., 1+1) exterminator is in room 4.

The "Bee Busters" communicate with the outside world via one-way radio. As they move from room to room, they call out their movements. Your output should provide a transcript of the utterances of the Bee Busters, and should also report on the status of the bees.

Turn in your program and output with the burst sheet. Your program should follow contemporary rules of style, i.e., indent, have (plenty of) comments, mnemonic variable names, and good structured forms.

The output should look something like the following:

*****  There are bees in rooms 1 2 3 5 6
"I'm moving from room 4 to room 1."
"Look out!  I hear something."
*****  There are bees in rooms 2 3 5 6
"I'm moving from room 1 to room 2."
"Look out!  I hear something."
---- illegal move attempted:
---- Bee Buster attempting to jump from room 2 to room 3
*****  There are bees in rooms 3 5 6
...
*****  There are no more bees.

The following are some suggestions to assist you in writing your program. YOU DO NOT HAVE TO USE THESE SUGGESTIONS. However, they may be quite helpful to get you started, especially if it has been a while since you wrote a program. A program written using some of these suggestions was less than 3 pages long (excluding the comments).

	     cin >> ifrom >> ito ;
	//---WHILE NOT EOF
	     while (!cin.eof())
	     {
		if(legal(ifrom,ito,passag,iextrm))
		{ 
		   report(room,nbeerm);
		   radio(ifrom,ito,iextrm,room,nbeerm);
		   cout << "Look out! I hear something." << endl;
		}
		cin >> ifrom >> ito ;
	     }

	//---FINAL REPORT
	     report(room,nbeerm);
	     return 0;
	  }

Boolean function legal determines whether a suggested move is actually legal. It checks (1) whether there is a passage between the two indicated rooms, and (2) if there is an exterminator already in the "destination" room. legal then writes out,

Void function report reports which rooms have bees in them (by writing "**** There are bees in ...") or indicates there are no more bees.

Void function radio "moves" a Bee Buster to another room, and "clears" the room of bees. (It also can adjust nbeerm accordingly.)

This page is maintained by Dennis C. Smolarski, S.J., dsmolarski@math.scu.edu. Last changed: 6 December 1999.