Project 5 - People in Purple Extra Terrestrial Locator
11 minute read
Learning Objectives
This assignment is designed to help you learn about recursive thinking, programming using recursion, and working with different kinds of Collections and other abstract data types.
Overview
As you may have heard, James Madison University has been working hard to give extraterrestrials (including Arcturans, Arquillians, Ballchinians, Boov, Colossi, Daleks, Druidians, Ewoks, Flora, Gorg, Hutts, Krylorians, Kylothians, Mawgs, Oods, Raxacoricofallapatorians, Remoolians, Sontarans, and Wookies) the opportunity to study on campus. However, for a variety of reasons related mostly to their psychologies, many extraterrestrials have a habit of getting lost on campus. So, JMU has created a super-secret group, named People in Purple, that monitors them (with their permission, of course).
Since their physiologies tend to interfere with the operation of both wearable devices and mobile telephones, PIP has purchased a remote sensor from the (fictitious) company Sciontific, that can determine if a particular extraterrestrial is in a given square area (of any size). They have asked you to create an algorithm that can use this sensor to determine a particular extraterrestrial’s location within a small tolerance, and to incorporate it into an application named the Extraterrestrial Locator.
The relationship between all of the components that comprise the Extraterrestrial Locator are illustrated in the following detailed UML class diagram.
Components in purple are part of the Java libraries, components in green were written by the GUI development team, components in orange were written by other developers, and components in black are to be written by you for this assignment. The Point class is in the package java.awt. All of the other classes are in the default package.
Background Information
Before you can start working on the components, you need to learn a little bit about the system.
Acronyms
- EL
- Extraterrestrial Locator
- JMU
- James Madison University
- PIP
- People in Purple
About the JMU Campus
People in Purple wants the system to work with the following area around and including the JMU campus.
About the Sensor
The sensor that People in Purple has purchased from Sciontific is very sophisticated, but has limitations.
First, though the sensor can determine if a particular extraterrestrial is in any square area, it can’t determine exactly where the extraterrestrial is. Hence, you must design and implement an algorithm that can identify the 1x1 cell that contains the extraterrestrial if it is, in fact, in the campus area. (Note: A particular extraterrestrial can be in at most one 1x1 cell.)
Second, it can only perform 50 scans on a single charge. Hence, since there are 262,144 cells on campus, the algorithm they originally thought they would use to locate an extraterrestrial (i.e., using a nested loop that scans all 262,144 of the 1x1 cells) does not work.
Provided Files
- pa5.jar
- this jar includes the
Sensor
andSensorDisplay
classes, but you will not see their source code. You don’t need to interact with theSensorDisplay
class yourself. You can find the documentation for theSensor
class below. - Remember, you’ll need to add the .jar to the build path: How to import .jar files
- this jar includes the
- ExtraterrestrialLocator.java
- jmu.png
- you should put this one in the eclipse project folder for your PA5, but unlike the
Extraterrestrial.java
file, this image should not be in thesrc
folder.
- you should put this one in the eclipse project folder for your PA5, but unlike the
The Existing Class: Sensor
Other programmers at People In Purple have created the Sensor
and SensorDisplay
classes that interact with the physical sensor and can be used to visualize the results. They are in the provided jar file.
You need only use the Sensor class (the Sensor
class uses the SensorDisplay
class). The scan()
method in this class is passed the square to scan (where x and y are the upper-left corner of the square and width is the width and height of the square). It returns -width
if the extraterrestrial is not in the square and width
if the extraterrestrial is in the square. The checkSystem()
method returns a two-line String that describes the result of the scan. The first line will be "Power constraint satisfied"
if 50
or fewer scans were used and will be "Power constraint violated"
otherwise. The second line will be "Strongest signal at location"
if your ELgorithm
found the extraterrestrial at the correct location and will be "No signal"
if your ELgorithm
does not find the extraterrestrial at the correct location.
They have also written the main class.
🏴☠️ARG!
As you saw in (all of the
🏷️ command line labs including:) the ArrayList Lab , the File I/O Lab , and the Enum Lab , you can configure Eclipse to provide command line arguments by modifying the run configuration as outlined on the wiki .The main method is passed one required and one optional argument. Argument 0, which is required, is a String containing the name of the extraterrestrial to search for. Argument 1, which is optional, is an integer that controls the amount of time between scans (in milliseconds), which is useful when visualizing the search process. If you want to visualize the results on the aerial photograph of the campus area, you will also need the aerial photo of the JMU campus (see provided files above), which must be in your project directory/folder. When searching for Stitch with a non-zero scan time, the application will look something like the following while it is in the process of searching.
In this visualization, the gray areas are those that did not contain the extraterrestrial of interest, the purple lines are used to delineate the area that is currently being scanned, and the purple square (which flashes briefly), indicates the area that is currently being scanned.
Part 1
The Class to be Written
You must write the ELgorithm
class.
The search()
method in this class is called by the main()
method in the (provided) ExtraterrestrialLocator
to initiate a search in the area defined by the parameters 0, 0, 512
. Hence, the search()
method is responsible for doing the work of locating the extraterrestrial (thought it can, of course, call other methods). This method must return null
if the extraterrestrial is not in the area of interest and must return a Point
object with the coordinates of the 1x1 cell containing the extraterrestrial if it is in the area of interest.
Submission
You must submit (using Gradescope):
- Your implementation of the ELgorithm class.
- You must not submit any other classes; the Sensor class will be available on Gradescope.
- There is no limit on the number of submissions and no penalty for excessive submissions.
Part 2
- Write the
Area
class. In addition to the specs implied by the UML diagram,- override
toString
to return aString
representation ofthis
Area
. If this Area had a startingx
of160
, a startingy
of192
, and awidth
(and height) of32
, then theString
representation would be (note the leading newline):+-------------------+ |(160, 192) + 32 | | (192, 224)| +-------------------+
- all 5 of the numbers displayed here are inserted into the
String
with a field width of3
(padded with spaces when necessary) - the commas always have at least 1 space after them regardless of the numbers that follow
- 3 spaces follow the width before the
|
- 9 spaces precede the opening parenthesis of the ending coordinates
- See below for examples where some of the numbers do not have 3 digits.
+-------------------+ |( 0, 0) + 512 | | (512, 512)| +-------------------+
+-------------------+ |(256, 320) + 64 | | (320, 384)| +-------------------+
- all 5 of the numbers displayed here are inserted into the
- override
- Create a new specialization of the
Sensor
class, called itLoggingSensor
- Its constructor (summarized in the UML diagram) should rely on its base class constructor to initialize most things, but it should also initialize the new instance variable
scanLog
to anew
HashMap
. - It should
override
thescan
method to call the base classscan
method, and then add the result to thescanLog
. - It should
override
toString
to return (only) aString
representation of thescanLog
.
- Its constructor (summarized in the UML diagram) should rely on its base class constructor to initialize most things, but it should also initialize the new instance variable
- Modify the
ExtraterrestrialLocator
class to:- use the
LoggingSensor
class (rather than the regular Sensor) - print the
toString
of theLoggingSensor
after the search is complete.
- use the
Submission
You must submit (using Gradescope):
- Your implementation of these classes:
Area
LoggingSensor
- You must not submit any other classes; the Sensor class will be available on Gradescope.
- There is no limit on the number of submissions and no penalty for excessive submissions.
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
Your code must compile, all class names and method signatures must comply with the specifications, and your code must have no style defects for you to receive any points on this assignment. Gradescope will then grade your submission as follows:
Part 1
Correctness (OfficialTests): 75 points (Limited Partial Credit Possible) Given the nature of this assignment, your grade from Gradescope will be either a 0, 37, or 75, and a 37 is fairly unlikely. In other words, your code must be correct for you to receive any points from Gradescope on this part of the assignment.
Part 2
Correctness (OfficialTests): 25 points (Partial Credit Possible)
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.
Suggestions
You may find the following suggestions helpful.
Allocating Time
Almost all of your time on this assignment should be spent thinking; very little time should be spent typing/compiling/etc. It is very unlikely that you will discover an algorithm that works through trial and error (i.e., try something, compile, test, make a change, repeat).
Getting Started
Before you start thinking about building a full-fledged ELgorithm, you might want to play around a little bit. For example, here’s a ELgorithm that scans the whole area and then scans some cells around I81. (Note: As it turns out, this algorithm will find Omastar.)
import java.awt.Point;
public class ELgorithm {
private Sensor sensor;
public ELgorithm(Sensor sensor) {
this.sensor = sensor;
}
public Point search(int x, int y, int width) {
int resultOfScan;
Point resultOfSearch;
resultOfSearch = null;
// Check the whole area
resultOfScan = sensor.scan(x, y, width);
if (resultOfScan < 0) // The extraterrestrial isn't in the area
{
resultOfSearch = null;
}
else // The extraterrestrial is in the area so let's search some more
{
// Try some cells around I81
for (int xx=300; xx<340; xx++)
{
resultOfScan = sensor.scan(xx, 323, 1);
if (resultOfScan == 1)
{
resultOfSearch = new Point(xx, 323);
break;
}
}
}
return resultOfSearch;
}
}
Approach
This assignment will be much easier to complete if your algorithm is recursive. Indeed, it is possible to write a recursive algorithm that contains surprisingly few lines (though your algorithm, like mine, may have more than that). Remember that there are two parts of a recursive algorithm:
- The part of the algorithm that handles the “easy” (or “base”) case.
- The part of the algorithm that moves “difficult” cases toward the “easy” case (i.e., the refinement part of the algorithm).
The first thing to think about is how to define the “easy”/“base” case. To do so, suppose your ELgorithm
calls the scan()
method in the Sensor
class. When is its job really easy? (Note: There may be more than one easy case.)
The second thing to think about is what you need to do to refine other cases (i.e., take hard cases and move them closer to the easy case).
Testing and Debugging
The visualization of the scanning process can both help and hinder testing and debugging. For your convenience:
- The scan time controls the speed of the visualization. Longer scan times will make it easier for you to see what your ELgorithm is doing, shorter scan times will make the program run faster.
- You can disable the GUI window completely with a scan time of 0.
The following extraterrestrials are known to frequent the JMU campus: Beeblebrox, Chewbacca, Fourarms, Groot, Kang, Neelix, Omastar, and Stitch. In other words, your ELgorithm must find all of these extraterrestrials. You can also test the system using UL, LL, UR and LR (fake extraterrestrials that are at the upper-left, lower-left, upper-right, and lower-right corners). Alf, on the other hand, is never on campus.
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.
- Why weren’t your required to find the exact location of the extraterrestrials (rather than the 1x1 cell containing them)?
- Could the search() method in the ELgorithm class return an int[] rather than a Point? What is the advantage of returning a Point?
- Why were square areas used rather than rectangular areas?
Looking Back - The Big Picture
By the time you complete this assignment you should have learned many things, including but not limited to the following “big picture” issues.
- Some problems are much easier to solve using recursion.
- Solving problems using recursion requires a different way of thinking.
Acknowledgements
Thanks to the CS 159 F'22 team (esp. Dr. Bernstein!) for their work in an earlier version of this assignment.
Change Log
Many software projects undergo changes over time. This section documents the changes made to this assignment over time. The most recent changes are listed first (this is called “reverse chronological order”).
- Added to spec for
Area.toString()
- - Corrected spec (and UML) for
Area
to useint
s rather thanPoint
-