Laboratory Exercise 2
An Intelligent Tram Timetable
Programmeringsteknik, del A.

Introduction

In this exercise you will program a route finder for the bus and tram system. Your goal is to define a function which, given the time you want to travel, the name of the stop you want to leave from, and the name of the stop you want to travel to, produces instructions telling you which bus or tram to take, which stops to change at, and what times each tram on your journey departs and arrives. For example, if you want to travel from Chalmers to Saltholmenat 3:30p.m., then the output might be

Tram 7 towards Tynnered	
	dep. Chalmers 15:30		arr. Marklandsgatan 15:39
Tram 3 towards Kålltorp
	dep. Marklandsgatan 15:45	arr. Mariaplan 15:49
Tram 4 towards Saltholmen
	dep. Mariaplan 16:01		arr. Saltholmen 16:15

A more ambitious system of this sort is provided on the web at http://www.vasttrafik.se/

Simplications

You will need to obtain copies of the tram timetables and type them into the computer. This is a lot of information. To keep it manageable,

• you need only use timetables for two or three tram lines,
• you need only consider week-days, so the timetables for Saturday and Sunday can be ignored,
• you need only consider the mornings,
• you may ignore the few trams which do not start at the beginning or finish at the end of their route,
• you may share the work of typing in the timetables with another group, if you agree on a format for the data.

Strategy

Try to gather related functions together, so that your program is broken up into collections of functions that work together. You might even place each collection in a module of its own. For example, you will need to manipulate times of day in various ways. Decide how to represent a time, and then define functions to compare two times and decide which is the later, format a time for output, perhaps add a given number of minutes to a time, and so on. You will need to manipulate tram timetables: decide how you will represent a timetable, and then define functions to create them, find the next tram from a particular stop, and so on. Include comments to explain what each group of functions does, and how they work.

In previous examples, I have argued that data, such as timetable information, should be stored in a separate file rather than as a part of a program. But in this case, I recommend you include the timetables in your program. If you study the way timetables are presented, you will see that GL do not provide a complete timetable, only a way to construct one. For example, when the timetable for several hours in a row is the same, then GL give the times each tram arrives only once. Similarly, the time of arrival is given only at a few stops, and you are left to work out for yourself when the tram arrives at other stops by using a separate table of travel times between stops. In effect, GL give you a simple `program´ to work out when your tram will come. If you write this program in Haskell, then you can construct a complete timetable with relatively little work. Working out the complete timetable by hand and typing it into a file would be too much work.

There are various ways to plan your tram journey, but all of them involve recursion. One way is to note that if you are at Chalmers at 15:30, then you can (among other places) reach Marklandsgatan by 15:39 on tram 7. You can collect all of the places and times that you can reach on tram 7 in a list. Now, from each one of them you can potentially travel further on other trams; you can work out the list of places and times you can reach with one change. Keep on going recursively, and sooner or later you will find a way to reach Saltholmen, which you can then present to the user. More ambitiously, you might first plan which trams to take, and only later consult the timetable to see when you will arrive at each intermediate stop. If you can find the quickest route between two stops, that would of course be an advantage.

Grades

You can earn a grade of Pass or Excellent on this lab. To earn Excellent,

• Your program should (in principle) be able to cope with any number of tram lines, even though you only include timetables for a few.
• There should be no assumptions about the network built into your program (for example, that all trams go through Brunnsparken!).
• Your program should complete searches within one minute.
• You should divide your program into separate modules, each containing logically related definitions grouped together.
• Your code should be readable and laid out carefully, and function definitions should be preceded by a comment explaining what they do.

Deadline

You should hand in the code of your solution to your group tutor at the group meetings in the week beginning October 14th, and also submit it electronically using the link on the course home page. You should also give your tutor instructions to enable him or her to run your program.