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.

Figure 1: Example of a roundabout.

Input

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:

T P A D

where

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-

ure 1 by 0 , 1 , 2 , and 3 . Each position can hold at most one car.

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.

If a car is in branch B and has the earliest arrival time and A car may en- ter the round-

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

about if there is no car to the left of it.

its departure (D) branch is B + 1 mod 4, A car departs the round-

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

about from the position to the left of the departing branch.

its departure (D) branch is not B + 1 mod 4, A car moves to the next

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

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 Sample Output

1

1 HELLO 0 1

Car HELLO departed at time 2

2

1 L8ER 2 0

2 ABC123 0 1

Car Car

ABC123 departed at time 3 L8ER departed at time 3

2

1. HELLO 0 1

2. BYEBYE 1 2

Car Car

HELLO departed at time 2 BYEBYE departed at time 4