PA3: FoneDrone

Programming Assignment 3

Learning Objectives

This homework/programming assignment is designed to help you learn about recursion. It is also designed to help you think about what it means for code to be correct, and why programmers shouldn’t be satisfied with code that is “almost correct”.

Overview

Old people, like one of the professors teaching CS159 this semester, have a tendency to lose their cell phones (and to have problems with their beepers, fax machines, and land-line phones). While there are currently tools that help people find lost phones, they seem to be beyond the capabilities of old people. This has led to the development of FoneDrone, an “intelligent” drone that can fly around inside of a building and find cell phones.

The drone itself uses short range transmitters/receivers (e.g., bluetooth or near-field communications) to identify phones. Hence, the drone must be directly over a phone to identify it.

The people that developed the FoneDrone hardware have little or no experience developing software, so they have contracted with you to develop the “intelligence” for FoneDrone.

Background

Rather than have you work with an actual drone, you have been provided with a drone simulator and several simulated rooms. The simulation is in the following .jar file (that contains .class files only, no .java files):

• 🫙pa3.jar

and the simulated rooms (that are used by the simulation) are in the following “human-readable” text files:

• familyroom.txt
• firstfloor.txt
• halls.txt

You should download all of these files into the downloads directory/folder that you created for this course.

The simulator consists of one enum, Direction, and two classes, Drone and DroneController. You must write the FoneDroneController class. The capabilities of these components and the relationships between them are illustrated in the following UML class diagram.

Specifications for the FoneDroneController Class

In addition to the specifications in the UML class diagram, your implementation of the FoneDroneController class must conform to the following specifications.

1. You may add private attributes and methods to the FoneDroneController class as needed.

2. The explicit value constructor in the FoneDroneController class is passed the phone number to look for.

3. The drone need not search every location (i.e., it may stop searching when it has found the phone it is looking for), but it may.

4. The drone starts (i.e., is “powered on”) at a particular location. When it is done searching, it must return to that location.

5. When the drone first searches a particular location it should check to see if the desired phone is at that location. This can be accomplished by having the FoneDroneController invoke the drone object’s checkForPhone() method (which returns the location as an int[] if the phone is at that location, or null if the phone is not at that location). The FoneDroneController should keep track of the location of the phone in its location attribute (and return it when the getLocationOfPhone() method is invoked).

6. The getLocationOfPhone() is a simple accessor. It must return the location attribute, it should not do the work of finding the phone. The work of finding the phone should be done in the start() method or a private method that is invoked by the start() method.

Testing

You may use the following main class to test your code:

package app;

import java.lang.reflect.InvocationTargetException;
import javax.swing.SwingUtilities;

import controller.*;
import simulator.*;

/**
 * A driver for running FoneDroneController.
 */
public class FoneDrone {

	/**
	 * The entry-point of the application.
	 * 
	 * @param args The command line arguments (which are ignored)
	 * @throws InterruptedException If something goes wrong with the GUI
	 * @throws InvocationTargetException If something goes wrong with the GUI
	 */
	public static void main(String[] args) throws InterruptedException, 
		InvocationTargetException {
		
		Drone drone;
		FoneDroneController controller;

		controller = new FoneDroneController("540-568-1671");
		drone = new Drone(controller, "halls.txt");
		controller.setDrone(drone);
		SwingUtilities.invokeAndWait(drone);
	}

}

It constructs a Drone (for a particular room) and a FoneDroneController and makes them aware of each other.

When running, the drone simulator looks something like the following (for the file named "halls.txt"):

The black areas indicate walls (or other places where the drone can’t go), the gray areas indicate rooms (or other places where the drone can go), the white areas indicate locations that have already been searched, and the * indicates the drone.

Since you are viewing the simulator from above and the drone does not change its orientation, Direction.FORWARD is always toward the top of the window, Direction.BACKWARD is always toward the bottom of the window, Direction.RIGHT is always toward the right of the window, and Direction.LEFT is always toward the left of the window.

For testing and debugging purposes:

1. You can control the speed of the drone using the slider at the bottom of the window. You can change the speed before the simulation starts and while it is running. The smaller the delay (in milliseconds) between moves, the faster the drone travels.

2. You can start the drone by clicking on [Drone] and pulling down to [Start]. This causes the FoneDroneController object’s start() method to be invoked.

3. After the FoneDroneController object’s start() method returns, its getLocationOfPhone() method is invoked, and the result is displayed in the console. (Note: This is where the Drone thinks it found the phone; the Drone may not be correct.) Also, information about the drone’s final location is displayed in the console.

4. You should have the Drone search for Prof. Bernstein’s, Prof. Mayfield’s and Prof. Stewart’s phones (they all have been known to leave them behind) in all three rooms. Prof. Duan’s phone number has changed since the simulator was created, so her current phone number shouldn’t be found. (You can find all of their phone numbers in the JMU Directory ). You should also have the Drone search for your phone in all three rooms (which it shouldn’t find).

Submission

You must submit (using Gradescope) a .zip file named pa3.zip that contains:

1. FoneDroneController.java

packaged appropriately. The controller directory/folder must be at the top of the .zip file. (See the first programming assignment if you have forgotten how to do this.)

Do not submit any other classes (including any unit tests).

Your grade will be reduced by 5 points for each submission after the 10th submission. So, you should try to ensure that your code is correct before you submit it the first time.

Grading

Your code will first be graded by Gradescope and then by the Professor. The grade you receive from Gradescope is the maximum grade that you can receive on the assignment

Gradescope Grading

Your code must compile (in Gradescope, this will be indicated in the section on “Does your code compile?”) and all class names and method signatures must comply with the specifications (in Gradescope, this will be indicated in the section on “Do your class names, method signatures, etc. comply with the specifications?”) for you to receive any points on this assignment. Gradescope will then grade your submission as follows:

In other words, your code is either correct (i.e., the Drone finds all of the lost phones and doesn’t find any phones that aren’t lost) or it isn’t.

As discussed above, your grade will be reduced by 5 points for each submission after the 10th submission.

Manual Grading

After the due date, the Professor may manually review your code. At this time, points may be deducted for inelegant code, inappropriate variable names, bad comments, etc. Points may also be deducted for using randomization to choose directions.

If your solution is not recursive (in a meaningful way), you will receive a grade of 0.

Help

You should carefully consider all of the following topics before starting.

Help with Data Files

As discussed above, you should download the data files into the downloads directory/folder that you created for this course.

After you have downloaded the data files you must open a file explorer or finder, select all of the files, and drag them into the Eclipse graphical user interface. Specifically, you must drag them into the project (not the src directory/folder or anything underneath it). When you do so, make sure you select “Copy files” not “Link to files”. Then, when you construct a Drone, you must use only the file name (i.e., do not include a path) as in the example above.

You do not need to read these files, they are read by the simulation. You just need to tell the Drone which file to use.

Help Using .jar Files

As discussed above, you should download the .jar file into the downloads directory/folder that you created for this course.

Help incoroprating .jar files into an Eclipse project is available on the CS Wiki .

Help Allocating Time

Almost all of your time on this assignment should be spent thinking; very little time should be spent typing/compiling/etc. Indeed, the recursive method in the FoneDroneController class may contain as few as 20 lines of code.

Though it may have worked for you in the past, it is very unlikely that you will discover an algorithm that solves this problem using trial and error (i.e., trying something, compiling, testing, making a change, and repeating). You will need to think carefully about how to solve problems recursively in general, and how recursive thinking can be used to solve this problem in particular.

Help with Class Design

The start() method in your FoneDroneController class should not contain all of the control logic. It should call other methods (that you will need to write), at least one of which must be recursive.

Help Getting Started

The people who developed FoneDrone originally contracted with students at another university in Virginia to develop the “intelligence”. They didn’t understand recursion and so were only able to develop a FoneDroneController that could search forward (in a stright line) from the Drone object’s original position. (We won’t mention which university so as not to embarass them.) The people who developed FoneDrone have provided you with this FoneDroneController in case it will help you get started (and help you understand what not to do). (Remember to edit the comments after you make changes.)

package controller;

import simulator.*;

/**
 * INCORRECT control logic for the PhoneDrone.
 *
 * @author A team of "hoakey" programmers at an un-named university in VA.
 * @version 1.0
 */
public class FoneDroneController extends DroneController {

    private int[] location;

    /**
     * Explicit Value Constructor.
     *
     * @param number The phone number to look for
     */
    public FoneDroneController(String number) {
        super(number);
        this.location = null;
    }

    /**
     * Get the location of the phone (or null if it hasn't been found).
     * 
     * @return The location of the phone (or null)
     */
    public int[] getLocationOfPhone() {
        return location;
    }

    /**
     * Start the FoneDrone.
     */
    @Override
    public void start() {
        search();
    }

    /**
     * Search for the phone.
     *
     * This method should be recursive but we couldn't figure
     * out how to do that. So, we did this instead. It's
     * close to correct because it does find the phone
     * sometimes. As a result, we think we should get at
     * least partial payment. In fact, because of the amount of
     * effort we devoted to it, we really think that we
     * deserve full payment.
     */
    private void search() {
        while (drone.canMove(Direction.FORWARD) && (location == null)) {
            drone.move(Direction.FORWARD);
            location = drone.checkForPhone(number);
        }

        while (drone.canMove(Direction.BACKWARD)) {
            drone.move(Direction.BACKWARD);
        }
    }
}

Help Writing a Recursive Algorithm

Remember that there are two parts of a recursive algorithm:

1. The part of the algorithm that handles the “easy” case.

2. The part of the algorithm that refines “difficult” cases.

The first thing to think about is how to define the “easy” case for this problem. To do so, suppose the drone is at a particular location and is told to search. When, in terms of the data (i.e., its location in the room, ignoring the location of the phone), is its job really easy?

After you have identified the “easy” case, think about how you can move the “difficult” cases (in terms of the data) to the “easy” case. In other words, how can you make progress (i.e., make the current situation “easier”) by calling methods in the Drone class like move(), canMove(), and hasBeen().

If you have trouble answering either of these questions after thinking about them for a few hours, ask your Professor for help (but make sure that you have evidence that you have thought seriously about answering these questions before you ask for help).

Thinking About Other Recursive Algorithms

Thinking about other recursive algorithms may help you write this one.

Finding the Factorial of n

The base case is when n is 1 (or 0) since all you have to do in this case is return the value 1. Refinement involves moving from the hard case toward the easy case (adjusting the answer accordingly). So, refinement involves reducing the value by 1.

Finding the Size of a Directory/Folder

A directory/folder can contain files and other directories/folders. The base case is when we you are examining a file since all you have to do in this case is return its size. Refinement involves moving from the hard case toward the easy case (adjusting the answer accordingly). So, refinement involves entering each directory/folder.

Questions to Think About

You don’t have to submit your answers to these questions, but you should try to answer them because they will help you determine whether or not you understand some of the important concepts covered in this assignment.

1. If your FoneDroneController works correctly and your phone is not found at a particular location, do you need to search at that location again? (You can assume that your phone does not move.)

2. If your FoneDroneController works “sometimes” and your phone is not found at a particular location, have you learned anything?

3. If the software in the air traffic control system works correctly and assures a pilot that there are no planes on the runway that they have been directed to, can the pilot land confidently?

4. If the software in the air traffic control system works “sometimes”, can a pilot ever land confidently?

5. Would you fly on an airplane if the software in the air traffic control system and the software in the plane’s avionics system work “sometimes”?

6. Would you complain if Canvas contained defects that led it to read and write grade files incorrectly every time it did so? Suppose it only read and wrote grade files incorrectly “sometimes”?