CSCI2110 Assignment 1
Instructor: Alex Brodsky
Due∗: 12:00 noon, Thursday, January 24, 2019
The purpose of this assignment is to refresh your programming skills and get you pro- gramming as quickly as possible. As discussed in class and the first tutorial, for each problem you will be provided with a description of the problem and a set of tests. These tests can be run on the submission system (Mimir) or on the unix server for this course. You can also use these tests on your own computer as illustrated in the first tutorial. Your code must compile. If it does not compile, you will receive a 0 on the assignment.
Problem: Simulating a Roundabout
Roundabouts, as shown in Figure 1 are a popular al- ternative to traffic intersections. According to stan- dard traffic rules, a car entering a roundabout must yield to cars already in the roundabout. That is, if a car wishes to enter the roundabout, there should be no car to the left of it. A car continues around the roundabout in a counterclockwise direction until it reaches the desired exit and departs the roundabout.
A roundabout simulator is a program that sim- ulates a roundabout one second at a time. For each second, the simulator uses the current position of each car to compute each car’s position one second later. The simulation continues until there are no more cars.
Write a simulator called Roundabout.java that reads in a stream of cars and outputs when each car departs the roundabout.
Input
Figure 1: Example of a roundabout.
Your program should read in the input using a Scanner object, which is instantiated with System.in. The input will contain one or more lines of text. The first line will contain a single integer, N, denoting the number of cars to simulate. This is followed by N lines. Each line denotes an arriving car and will be of the form:
TPAD
where
∗Latest version generated on: January 9, 2019
1
CSCI2110 Winter 2019 Assignment 1
T is the time in seconds (int) of a car’s arrival at a branch leading to the roundabout. All cars will be in chronological order.
P is a licence plate of the car. This is a single alphanumeric word (String). A is the arrival branch, denoted by one of 0, 1, 2, or 3 (int).
D is the departure branch, denoted by one of 0, 1, 2, or 3 (int).
For example, a car with license plate ABC123 that arrives at 30942 seconds on branch 2 and departs on branch 1 is denoted:
30942 ABC123 2 1
Hint: Use the Scanner object to easily parse the input. For this assignment you only need to use the nextInt() and next() methods. It may be easier to read in all the input first and store the cars in a list. There are more examples on the next page.
Processing
The simulatiion consists of zero or more rounds where each round represents one (1) second of time. (Hint: you will need a main loop, where each iteration of the loop simulates one round.) Round R refers to the round that takes place in second R of the simulation. The simulation ends when all N cars have departed the roundabout.
A roundabout has four branches, numbered 0,1,2,3, through which cars enter and depart the roundabout. Multiple cars may be in a branch at the same time. The cars are ordered by their arrival time. All arrival times in a branch will be unique.
The roundabout has four positions, also numbered 0, 1, 2, 3, which are depicted in Fig- ure1by , , ,and . Eachpositioncanholdatmostonecar.
Each round R consists of two (2) phases:
Phase 1: All cars (T, P, A, D) with arrival time T = R are added to branch A.
Phase 2: The following actions all take place at the same time. If a car is in branch B and has the earliest arrival time and
there is no car in the roundabout at position B − 1 mod 4,
then the car moves to position B. If a car is at position B and
its departure (D) branch is B + 1 mod 4,
then it is removed from position B and the simulator outputs the cars identifier (P) and R.
If a car is at position B and
its departure (D) branch is not B + 1 mod 4,
then it moves to position B + 1 mod 4.
If two or more cars depart the roundabout at the same time, the output should be ordered by the car’s current position in the rounadbout. E.g., If car J is at position 1 and car K is at position 3, and both cars depart the roundabout via branches 2 and 0, respectively, then
A car may en- ter the round- about if there is no car to the left of it.
A car departs the round- about from the position to the left of the departing branch.
A car moves to the next roundabout position.
0
1
2
3
2
CSCI2110 Winter 2019 Assignment 1
the output for car J should precede the output for car K. Hint: this is a natural outcome of processing the cars in the order of their position: 0, 1, 2, 3.
Hints: You can use four lists to keep track of cars in branches and a four-element array to keep track of cars in the roundabout. To simulate actions that take place at the same time, use two four-element arrays. One array stores the state of the roundabout at the beginning of the round, and the second array stores the state at the end of the round. The actions in Phase 2 use the state of the first array to compute the new positions and store the results in the second array. At the end of round, the second array is copied to the first and -initialized.
Output
The simulator should output to the console (System.out) when a car leaves the roundabout. The output should have the following format:
Car P departed at time R
where P is the car’s unique identifier, and R is the current round.
Examples Sample Input
1
1 HELLO 0 1
2
1 L8ER 2 0
2 ABC123 0 1
2
1 HELLO 0 1
2 BYEBYE 1 2
Sample Output
Car HELLO departed at time 2
Car ABC123 departed at time 3
Car L8ER departed at time 3
Car HELLO departed at time 2
Car BYEBYE departed at time 4
Hints and Suggestions
• Your code must compile. If it does not compile, you will receive a 0 on the assignment.
• Your code must be well commented and indented. Please see the Assignments section
for this course on Brightspace for Code Style Guidelines.
• You may assume that all input will be correct. You do not need to handle incorrect
input, for now.
• The problem in this assignment has a short solution (≈ 170 lines of code).
• Be sure to test your programs using the provided tests or via Mimir. To test without
Mimir, see the README.txt file in the provided tests zip file. 3
CSCI2110 Winter 2019 Assignment 1 What to Hand In
Submit the source files for your program via Mimir as described in the first tutorial. A link to Mimir is available on Brightspace. At least one of the submitted files must be Roundabout.java, which is where the main program starts to run.
Grading
The assignment will be graded based on three criteria:
Functionality “Does it work according to specifications?”. This is determined in an auto-
mated 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 tests, you will receive T
that proportion of the marks.
Quality of Solution “Is it a good solution?” This considers whether the solution is correct,
efficient, covers boundary conditions, does not have any obvious bugs, etc. This is determined by visual inspection of the code. Initially full marks are given to each solution and marks are deducted based on faults found in the solution.
Code Clarity “Is it well written?” This considers whether the solution is properly format- ted, well documented, and follows coding style guidelines.
If your program does not compile, it is considered non-functional and of extremely poor quality, meaning you will receive 0 for the solution.
Marks
Functionality Quality of Solution Code Clarity
20 20 10
Total
50
4