CSCI 1110: Assignment 4
Due: 8:00 am, Tuesday, November 24, 2020
The purpose of this assignment is to reinforce your understanding of linear data
structures such as lists and queues. For this problem you will be provided with sample
tests in Mimir. All input is done via the console and all output is to be done to
the console as well. You must submit your assignment via Mimir, and you can test
it by submitting your code. Note: for this assignment you are expected to install
and use an IDE (other than Mimir) to develop your code. The problem in this assignment
is described in three stages. Each stage builds on the next. Each stage
subsumes the previous stage. I.e., if completing Stage III, means completing Stage II and Stage I.
The Halifax International Airport is redesigning their Airport Security Screening facilities and are trying to
determine how many security check stations are needed. To determine this, they have hired you to write
a simulation to determine how long it takes passengers to get through a security check. In real life, the
total time depends on many factors, such as the number of stations there are, the number of bags a
passenger has, the number of passengers arriving at security, and whether some passengers pack prohibited
items, requiring a manual search of their bags. To keep things simple, you have decided to start with
a simple simulation and increase its complexity from one stage to the next. You have noted that the
factors that contribute most to the wait time are: waiting to enter the station and waiting to collect the
bags after they have gone through the scanner, with the occasional manual inspection to slow things
down. Naturally, a passenger cannot collect their bags until the passenger ahead of them has done so.
Write a program called AirportSecuritySim.java that simulates an Airport Security Checkpoint.
Each simulation consists of several rounds. In each round zero or more passengers arrive at the airport
security checkpoint, each carrying zero or more bags. They are assigned to a screening station with the
shortest line. They then wait zero or more rounds for their turn to place their bags on the conveyor belt,
walk through the scanner, and collect their bags on the other side before leaving to catch their flight. Your
program will simulate this process, outputting when the passengers arrive and when they leave.
Stage I: Airport Security Simplified
In this stage, all passengers will be travelling light, i.e., they will have no bags and there is only one screening
station that is operational.
Input
The input is divided into two parts: (i) a list screening stations that are open at the security check point
and (ii) a list of passengers arriving in each round. The first part of the input isthe list of screening stations.
The first part is a single line that contains an integer denoting the number of stations (S), followed by S
integers encoding the stations numbers that are open. For example, this input
3 2 4 8
means there are 3 open screening stations: 2, 4, and 8. In Stage 1, only one station will be open.
The second part of the input is the list of the passengers and their bags arriving in each round. The first
line contains a single integer (R) denoting the number of rounds in which passengers may be arriving. This
is followed by R sections, one section per round. Each section begins with a line containing a single integer
(P) denoting the number of passengers arriving at the security check point in this round. This is followed
by P lines encoding each passenger and their bags. In Stage 1, each passenger is encoded by a single
word, denoting the passenger’s name followed by a 0, indicating the passenger has 0 bags. E.g., the input
5
2
Alice 0
Bob 0
0
1
Carol 0
3
Dave 0
Eve 0
Fred 0
1
Ginny 0
means there are 5 rounds: In round 1, Alice and Bob arrive, each carrying 0 bags; in round 2, no passengers
arrive; in round 3, Carol arrives, with no bags; in round 4 Dave, Eve, and Fred arrive; and in round 5, Ginny
arrive, also with no bags. In Stage 1 all passengers carry 0 bags, which makes the screening a little faster.
Processing
Your program should simulate the operations of the security checkpoint. The main loop performs one
round per iteration. The pseudocode for your main program is:
1. Read in the screening stations and the number of rounds
2. Loop for the specified number of rounds:
a. Read in the passengers arriving in this round. For each passenger
i. Read in the bags that they are carrying (in Stage 1 no one has bags)
ii. Assign each passenger to a screening station.
iii. Generate the required output for the passenger (see Output Section).
b. For each screening station
i. The passenger at the head of the line proceeds through the screening and leaves
ii. Generate the required output for the passenger (see Output Section)
3. Loop until all the passengers have left the security checkpoint
a. For each screening station
i. The passenger at the head of the line proceeds through the screening and leaves
ii. Generate the required output for the passenger (see Output Section)
Output
When a passenger enters a screening station line, the program should output:
Name(B) enters station N in round T
where
• Name is the passenger’s name
• B is the number of bags the passenger has
• N is the station they have been assigned to
• T is the current round. Rounds are numbered 1, 2, 3, … R
When a passenger leaves a screening station line, the program should output:
Name(B) leaves station N in round T
The output should be to the console, and each line terminated by a newline. If two passengers are arriving
or leaving at the same time, the output should be the same as the input order.
Alice(0) enters station 7 in round 1
Bob(0) enters station 7 in round 1
Alice(0) leaves station 7 in round 1
Bob(0) leaves station 7 in round 2
Carol(0) enters station 7 in round 3
Carol(0) leaves station 7 in round 3
Dave(0) enters station 7 in round 4
Eve(0) enters station 7 in round 4
Fred(0) enters station 7 in round 4
Dave(0) leaves station 7 in round 4
Ginny(0) enters station 7 in round 5
Eve(0) leaves station 7 in round 5
Fred(0) leaves station 7 in round 6
Ginny(0) leaves station 7 in round 7
Hints and Suggestions
You can implement this assignment as you wish, however, the following design is recommended:
• Passenger class
o – name : String passenger’s name
o + Passenger(String) sets the name of the passenger
o + getName() : String returns the name of the passenger
o + toString() : String returns a String of the form “Name(numberOfBags)”
• ScreeningStation class
o – lineup : Queue
queue of passengers waiting to be screened
o – stationNumber : int number of screening Station
o + ScreeningStation(int) sets the station number
o + addPassenger(Passenger) : void adds passenger to lineup
o + getStationNumber() : int returns station number
o + getLineUpSize() : int : returns number of passengers in line-up
o + isPasengersInStations() : boolean returns true if there are passengers in the station
o + doStep() : Passenger returns a passenger that has just left the station, or null if no passenger
has left the station.
• AirportSecuritySim class Implements the pseudocode in the Processing section
o Create Passenger objects as you are reading in the arriving passengers in the main loop.
Stage II: Multiple Screening Stations
Extend your program from Stage I to handle multiple screening stations.
Input
The input format is the same as in Stage I.
Processing
Your program should perform the same task as in Stage I with the following assumptions
• The number of screening stations may be greater than 1.
• For each passenger select the station with the fewest number of passengers. If there is a tie, the
order of the stations breaks the tie.
• In the main loops, stations are processed in the order that they were read in.
Output
The output format is the same as in Stage I.
Hints and Suggestions
To extend Stage 1 the following design additions are recommended:
• AirportSecuritySim class : add functionality to create and store multiple ScreeningStation objects
o Use an array or an ArrayList to store the ScreeningStation objects
Stage III: The Full Program
Extend your program from Stage II to handle baggage. Passengers can bring zero or more bags. While
most bags will pass through the screening station’s X-ray machine untouched, some bags will need to be
examined by security personnel before being collected by the passenger. This will result in delays.
Input
The input format is the same as in Stage I. Additionally, if a passenger has more than 0 bags, the format
for the passenger is:
Name B M1 M2 … MB
where
• Name is the name of the passenger
• B is the number of bags
• Mi is a boolean value indicating if the ith bag requires manual screening. The value false means
that no manual inspection is needed and the value true means that a manual screening is
needed. (See example.)
Processing
Your program should perform the same task as in Stage II with the following additions
• When a passenger is screened, the passenger’s bags are screened as well.
• For each bag that requires manual screening, the passenger is delayed a round and cannot leave.
• No following passengers can leave the same station until the passenger whose bags are being
manually screened leaves.
Output
The output format is the same as in Stage I and II.
Examples
Example 1
Input Output
2 7 42
5
2
Alice 2 true true
Bob 1 false
0
1
Carol 3 true true true
3
Dave 2 false true
Eve 1 false
Fred 0
1
Ginny 0
Alice(2) enters station 7 in round 1
Bob(1) enters station 42 in round 1
Bob(1) leaves station 42 in round 1
Carol(3) enters station 42 in round 3
Alice(2) leaves station 7 in round 3
Dave(2) enters station 7 in round 4
Eve(1) enters station 7 in round 4
Fred(0) enters station 42 in round 4
Ginny(0) enters station 7 in round 5
Dave(2) leaves station 7 in round 5
Eve(1) leaves station 7 in round 6
Carol(3) leaves station 42 in round 6
Ginny(0) leaves station 7 in round 7
Fred(0) leaves station 42 in round 7
Hints and Suggestions
To extend Stage 2 to Stage 3 the following design additions are recommended
• Bag class
o – manualScreening : boolean does the bag require manual screening
o + Bag(boolean) sets whether the bag requires manual screening
o + isManualScreening() : boolean returns whether the bag requires manual screening
• Passenger class : add the following attributes
o – bags : List a list used to store the passenger’s bags (used in later
o + addBag(Bag) : void adds a bag to the passenger (will not be needed until Stage 2)
o + getNumberOfBags() : int returns the number of bags a passenger has
o + getBags() : List returns the list of bags a passenger has
• ScreeningStation class
o + doStep() : Passenger this method will need to be modified to deal with passengers that
have bags.
• AirportSecuritySim class : add functionality to read in the bags for each passenger
o Use the Scanner’s nextBoolean() method to read the Boolean values of the bags
Grading
The assignment will be graded based on three criteria:
Functionality: “Does it work according to specifications?”. This is determined in an automated fashion by
running your program on a number of inputs and ensuring that the outputs match the expected outputs.
The score is determined based on the number of tests that your program passes. So, if your program
passes t/T tests, you will receive that proportion of the marks.
Quality of Solution: “Is it a good solution?” This considers whether the approach and algorithm in your
solution is correct. This is determined by visual inspection of the code. It is possible to get a good grade
on this part even if you have bugs that cause your code to fail some of the tests.
Code Clarity: “Is it well written?” This considers whether the solution is properly formatted, well documented,
and follows coding style guidelines. A single overall mark will be assigned for clarity. Please see
the Java Style Guide in the Assignment section of the course in Brightspace.
If your program does not compile, it is considered non-functional and of extremely poor quality, meaning
you will receive 0 for the solution.
The following grading scheme will be used:
Task 100% 80% 60% 40% 20% 0%