The objective is to write a program tripView.c that generates an optimal trip on (a part of) Sydney's railway network based on user preferences.
The objective is to write a program tripView.c that generates an optimal trip on (a part of) Sydney's railway network based on user preferences.
Input
Railway stations
The first input to your program consists of an integer n > 0, indicating the number of railway stations on the network, followed by n*2 lines of the form:
railway-station
transfer-time
where the first line is the name of a station and the second line denotes the time in minutes it takes to transfer to a different train at that station.
Here is an example:
./tripView
Size of network: 3
HarrisPark
1
TownHall
3
NorthSydney
2
You may assume that:
The input is syntactically correct.
The maximum length (strlen()) of the name of a railway station is 16 and will not use any spaces.
The transfer time will be a positive integer.
No name will be input more than once.
Hint:
To read a single line with a station name you should use:
scanf("%s", name);
where name is a string, i.e. an array of chars.
Timetables
The next input to your program is an integer m > 0, indicating the number of trains on any day, followed by m timetables. Each timetable starts with the number s > 1 of stops followed by s*2 lines of the form:
station
hhmm
meaning that you can get on or off the train at that station at the given time (hh hour, mm minute).
Here is an example:
Number of timetables: 2
Number of stops: 3
HarrisPark
0945
TownHall
1020
NorthSydney
1035
Number of stops: 2
TownHall
1024
NorthSydney
1033
You may assume that:
The input is syntactically correct.
All times are given as 4 digits and are valid, ranging from 0000 to 2359.
Only train stations that have been input earlier as part of the network will be used.
The stops are input in the correct temporal order.
All trains reach their final stop before midnight.
Trip View
The final input to your program are user queries:
From: HarrisPark
To: NorthSydney
Arrive at or before: 1200
As before, you may assume that the input is correct: Two different valid railway stations followed by a valid time in the form of 4 digits.
Your program should terminate when the user enters "done" when prompted with From:
From: done
Bye
For the next stage, your program should find and output a connection from FromStation to ToStation that:
may involve one or more train changes;
arrives at ToStation no later than ArrivalTime ; and
leaves as late as possible.
Note that you can get onto a different train at any station, but it is necessary to take into account the time it takes to change trains at that station.
In all test scenarios for this stage there will be at most one connection that satisfies all requirements.
Here is an example to demonstrate the expected behaviour of your program for this stage:
./tripView
Size of network: 6
Ashfield
5
Central
8
HarrisPark
1
NorthSydney
2
Redfern
5
TownHall
3
Number of timetables: 2
Number of stops: 5
HarrisPark
0945
Ashfield
0955
Redfern
1006
TownHall
1020
NorthSydney
1035
Number of stops: 3
HarrisPark
0950
Central
1010
TownHall
1017
From: HarrisPark
To: NorthSydney
Arrive at or before: 1040
0950 HarrisPark
1010 Central
1017 TownHall
Change at TownHall
1020 TownHall
1035 NorthSydney
From: done
Bye
If there is no connection that satisfies the requirements, then the output should be: No connection.
From: HarrisPark
To: TownHall
Arrive by: 1015
No connection.
For the final stage, if there are multiple possible connections with the same latest departure time, your program should take into account the additional user preference that:
among all the connections with the latest possible departure time, choose the one with the shortest overall travel time.
You may assume that there will never be more than one connection with the latest possible departure time and the shortest overall travel time. Note also that travel time includes the time it takes to change trains and the waiting time if applicable.
Here is an example to demonstrate the expected behaviour of your program for stage 3:
./tripView
Size of network: 3
HarrisPark
1
NorthSydney
2
TownHall
3
Number of timetables: 2
Number of stops: 3
HarrisPark
0945
TownHall
1020
NorthSydney
1035
Number of stops: 2
TownHall
1024
NorthSydney
1033
From: HarrisPark
To: NorthSydney
Arrive at or before: 1040
0945 HarrisPark
1020 TownHall
Change at TownHall
1024 TownHall
1033 NorthSydney
From: done
Bye
Complexity Analysis
You should include a time complexity analysis for the asymptotic worst-case running time of your program, in Big-Oh notation, depending on the size of the input:
the size of the network, n
the number of timetables, m
the maximum number of stops on any one timetable, s.
