JAVA CODE

You need to implement a simulation/scoring system, which given

• an input data set file, which contains the world parameters and the requested rides, and
• a submission file, which contains the allocation of rides to vehicles

outputs an integer that represent the scoring of the allocation contained in the submission file, according to the Scoring section of the specification document.

As part of this task you need to write tests for your application based on the problem specification starting with the examples provided in the text specification, but not limiting yourself to them.

You can develop a graphical front-end for the simulation, e.g. showing cars and passengers with pixel of different colors (keep in mind that simulation scenarios could be large, up to 10000x10000).

This is a large scale test to test your simulation, the two input files are d_metropolis.in (world and rides) and d_metropolis.out (allocation). The resulting score should be 5265681.

Task composed of three stages

Stage 1 develop a program that given a problem and a solution computes the quality of the solution

Stage 2/3 develop a program that given a problem computes a solution of high quality

Classes - edit code for the following classes:

Main Class - get the name of the two files from the command line and creates/run the simulation

Simulation Class - creates a WorldAndRides and Allocation from the files

WorldAndRides Class - read information about the world and the rides from the file storing them into internal data-structures

This class should check the format of the file and read values are according to the specifications

Allocation Class - reads information about the allocation of rides to cars and stores them in internal data-structures

This class should check format, values, and and that they are consistent with information from the world

FileFormatException Class - used to signal that there is a problem with the files

You need to keep the Main class as it is (it is needed for the automated system to work)

Where to go from here

First you need to write some code to read the WorldAndRidesfile to

Set up the parameters of the world

Store the list of rides in a data structure

Second you need to write some code to read the Allocation file and store the list of rides allocated to each vehicle

Then you need to think how to compute the score, there are two ways about this:

A simpler way that goes through what happens to each vehicle separately as it moves around according to the car movement rules, computing the points for the vehicle

after a vehicle has completed the list of rides, the points get added to the total, clock is reset to 0 and the simulation restarts for the next vehicle

A more complex way in which there is a single clock and all vehicles move in a single simulation adding points as they go

This takes substantially longer but it can be helpful to develop strategies in Stage2/3 as it is easy to know where every vehicle is at a specific point in time

The problem

A fleet of self-driving cars get passengers around

passengers pre-book their rides beforehand

to each self-driving car is allocated a sequence of rides to complete in order, according to a pre-defined set of rules

cars get points if they start/finish rides on time

In Stage 1 you have to develop a simulation/scoring system that reads two input files

World and Rides: a description of the city and the rides booked,

Allocation: a list of rides allocated to each car;

and prints how good that allocation is, i.e. the total number of points obtained.

In Stage 2/3 you will instead read the World and Rides file, allocate rides to cars to obtain as many points as possible, and then print out the resulting Allocation.

The World

The city is represented by a rectangular grid of streets, with R horizontal streets (rows) and C vertical streets (columns).

Street intersections are referenced by integer, 0-based coordinates of the horizontal and the vertical street.

For example, [r, c] means the intersection of the r-th horizontal and the c-th vertical street ( 0 r < R, 0 c < C ).

Time and distance

The time proceeds in T steps, from 0 to T 1.

The distance between two intersections is defined as the minimum total number of city blocks (cells in the grid) that a vehicle has to pass in each direction to get from one intersection to the other. That is, the distance between intersection [a, b] and intersection [x, y] is equal to |a x| + |b y| .

The number of steps required to drive between two intersections is equal to the distance between them.

The Rides

There are N pre-booked rides.

Each ride is characterized by the following information:

start intersection to begin the ride, the vehicle must be in this intersection.

finish intersection to end the ride, the vehicle must be in this intersection. Finish intersection is always different than start intersection.

earliest start the earliest step in which the ride can start. If the ride starts at that time the car gets B bonus points, but it can also start at any later step.

latest finish the latest step by which the ride must finish to get points for it. Rides finishing in time get a number of points equal to the distance between the start and the end intersections.

e.g. ride 1 1 2 3 2 7

will start from (1,1)

will go to (2,3)

can start from T=2

gets points if it finishes by T=7

so if it starts

at T=2 B+3 points

from T=3 to T=4 3 points

from T=5 0 points

World and Rides file: The World

The first line of the file contains the following integer numbers separated by single spaces:

R number of rows of the grid (1 R 10000)

C number of columns of the grid (1 C 10000)

F number of vehicles in the fleet (1 F 1000)

N number of rides (1 N 10000)

B per-ride bonus for starting the ride on time (1 B 10000)

T number of steps in the simulation (1 T 10^9 )

World and Rides file: The Rides

N subsequent lines of the file describe the individual rides, from ride 0 to ride N 1 . Each line contains the following integer numbers separated by single spaces:

a the row of the start intersection (0 a < R)

b the column of the start intersection (0 b < C)

x the row of the finish intersection (0 x < R)

y the column of the finish intersection (0 y < C)

s the earliest start(0 s < T)

f the latest finish (0 f T) , (f s + |x a| + |y b|)

note that f can be equal to T this makes the latest finish equal to the end of the simulation The finish intersection is always different from the start intersection (the two can be in the same column, or in the same row, but not in the same column and in the same row).

Vehicles and Allocation

Vehicles

There are F vehicles in the fleet. At the beginning of the simulation, all vehicles are in the intersection [0, 0]. There is no limit to how many vehicles can be in the same intersection.

For stage 1/2 each vehicle can carry only one passenger at a time

Vehicles are programmed with a list of rides they need to carry out (in order), this is called an Allocation

Allocation File

The allocation file contains F lines, one for each vehicle in the fleet.

Each line describing the rides of a vehicle must contain the following integers separated by single spaces:

M number of rides assigned to the vehicle (0 M N)

R0 , R1 , ..., RM-1 ride numbers assigned to the vehicle, in the order in which the vehicle will perform them (0 Ri < N)

Any ride can be assigned to a vehicle at most once. That is, it is not allowed to assign the same ride to two or more different vehicles. It is also not allowed to assign the same ride to one vehicle more than once.

It is not required to assign all rides to vehicles some rides can be skipped.

Vehicle movement

Once the allocation is decided each vehicle carries out its allocated rides in a pre-defined order:

first, the vehicle drives from its current intersection ([0,0] at the beginning of the simulation) to the start intersection of the next ride (unless the vehicle is already in this intersection)

then, if the current step is earlier than the earliest start of the next ride, the vehicle waits until that step

then, the vehicle drives to the finish intersection

the vehicle does this even if the arrival step is later than the latest finish; but no points are earned by such a ride

then, the process repeats for the next assigned ride, until the vehicle handles all scheduled rides or the simulation reaches its final step T (whichever comes first)

any remaining assigned rides are simply ignored

Example

World: 4 rows, 6 columns, 1 vehicle, 1 ride, 3 bonus and 10 steps

Rides: 1 Ride (id=0) with the following parameters:

start intersection: [1, 2]

finish intersection: [1, 4]

earliest start: 5

latest finish: 8

First vehicle has 1 ride in total in the allocation: the one with id=0

Then the simulation proceeds as follows:

in steps 0, 1 and 2 the vehicle drives to [1, 2]

in steps 3 and 4 the vehicle waits until the earliest start in step 5

in steps 5 and 6 the vehicle drives to the finish intersection

in step 7 the ride is finished, one step before the deadline

the score is: 2 (ride length) + 3 (bonus) = 5

WorldAndRide file:

4 6 1 1 3 10

1 2 1 4 5 8

Allocation file:

1 0

Scoring

Remember goal of Stage 1

you have to develop a simulation/scoring system that reads the two input files

World and Rides: a description of the city and the rides booked,

Allocation: a list of rides allocated to each car;

and prints how good that allocation is, i.e. the total number of points obtained.

Scaffolding Code

Classes

Main, get the name of the two files from the command line and creates/run the simulation

Simulation, creates a WorldAndRides and Allocation from the files

WorldAndRides read information about the world and the rides from the file storing them into internal data-structures

Should check the format of the file and read values are according to the specifications

Allocation reads information about the allocation of rides to cars and stores them in internal data-structures

Should check format, values, and and that they are consistent with information from the world

FileFormatException used to signal that there is a problem with the files

You need to keep the Main class as it is (it is needed for the automated system to work)

Rest of the code is not mandatory, just to get you started

Where to go from here

First you need to write some code to read the WorldAndRidesfile to

Set up the parameters of the world

Store the list of rides in a data structure

Second you need to write some code to read the Allocation file and store the list of rides allocated to each vehicle

Then you need to think how to compute the score, there are two ways about this:

A simpler way that goes through what happens to each vehicle separately as it moves around according to the car movement rules, computing the points for the vehicle

after a vehicle has completed the list of rides, the points get added to the total, clock is reset to 0 and the simulation restarts for the next vehicle

A more complex way in which there is a single clock and all vehicles move in a single simulation adding points as they go

This takes substantially longer but it can be helpful to develop strategies in Stage2/3 as it is easy to know where every vehicle is at a specific point in time