100 points
Due: 11/13

LP Airlines is a small, private airline company that flies routes between a number of small cities, including Roanoke, VA. Here is a sample of part of LPA's flight timetable and route map:

Flight No.	From	To	Departs	Arrives	Days
lp1211	Columbus	Charlotte	11:10	12:20	Mon Tue Wed Fri Sun
lp1212	Charlotte	Columbus	13:20	16:20	Mon Tue Wed Fri Sun
lp1322	Columbus	Pittsburgh	11:30	12:40	Tue Thu
lp1323	Pittsburgh	Columbus	13:30	14:40	Tue Thu
lp1458	Roanoke	Charlotte	09:10	10:00	Mon Tue Wed Thu Fri Sat Sun
lp1459	Charlotte	Roanoke	11:00	13:50	Mon Tue Wed Thu Fri Sat Sun
lp1472	Columbus	Charlotte	20:30	21:30	Mon Wed Thu Sat
lp1473	Charlotte	Columbus	16:30	19:30	Mon Wed Thu Sat
lp1510	Charlotte	Roanoke	08:30	11:20	Mon Tue Wed Thu Fri Sat Sun
lp1511	Roanoke	Charlotte	12:20	13:10	Mon Tue Wed Thu Fri Sat Sun
lp1613	Pittsburgh	Charlotte	09:00	09:40	Mon Tue Wed Thu Fri Sat
lp1614	Charlotte	Pittsburgh	09:10	11:45	Mon Tue Wed Thu Fri Sat Sun
lp1620	Pittsburgh	Roanoke	07:55	08:45	Mon Tue Wed Thu Fri Sat Sun
lp1621	Roanoke	Pittsburgh	09:25	10:15	Mon Tue Wed Thu Fri Sat Sun
lp1623	Roanoke	Pittsburgh	12:45	13:35	Mon Tue Wed Thu Fri Sat Sun
lp1805	Charlotte	Pittsburgh	14:45	17:20	Mon Tue Wed Thu Fri Sun
lp1806	Pittsburgh	Charlotte	16:10	16:55	Mon Tue Wed Thu Fri Sun
lp4732	Charlotte	Raleigh	09:40	10:50	Mon Tue Wed Thu Fri Sat Sun
lp4733	Raleigh	Charlotte	09:40	10:50	Mon Tue Wed Thu Fri Sat Sun
lp4752	Charlotte	Raleigh	11:40	12:50	Mon Tue Wed Thu Fri Sat Sun
lp4773	Raleigh	Charlotte	13:40	14:50	Mon Tue Wed Thu Fri Sat Sun
lp4822	Charlotte	Raleigh	18:40	19:50	Mon Tue Wed Thu Fri
lp4833	Raleigh	Charlotte	19:40	20:50	Mon Tue Wed Thu Fri

The goal of this assignment is to create a simple route planner that can be used in making flight reservations. Given constraints on a passenger's itinerary--such as a chosen starting point and ending point, for example--your program should find and display all possible routes meeting those constraints.

The constraints that may be specified by a passenger are:

• City departing from
• City traveling to
• Departure time
• Arrival time
• Day of week for flight

All of these constraints are optional; the traveller is free to specify only those that are appropriate. Your route planner should find all possible flight plans that satisfy the constraints given. Further, the flight plans generated by your route planner should obey these common sense restrictions for connecting flights:

• There must be at least 45 minutes between the arrival time of one flight and the departure time of the next, to allow the passenger to de-plane, locate the appropriate gate, and board the second aircraft.

• All travel must be completed on the same day.

For this half of the assignment, the implementation language is Prolog. You will be programming in a logical programming style, as described in Chapter 16 of the text book. Since this program must be written in Prolog, appropriate use of logic language features is expected. In particular, you may not use any versions of assert, retract, record, erase, flag, or any of the other database features of Prolog.

As with prior programs, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, predicate length, commenting, headers for each predicate, etc.

As you work through this assignment, you may find the following resources useful:

• Prolog Tutorial
• Prolog Tutorial Section 2.7: Lists and Sequences
• SWI-Prolog Reference Manual Section 4.29: List Manipulation
• SWI-Prolog Reference Manual

In order to construct a solution, one must first devise a representation scheme for encoding flight data stored in the flight timetable. You will end up with a more readable (and easier to write) solution if you use a simple prolog structure to represent time information. If you place the following goal at the top of your program, you will introduce a new "operator symbol" that you can use later in your code:

:-  op( 50, xfy, :).

This is a goal rather tha a rule--the :- appearing without any lefthand side instructs the interpreter to execute the righthand side as it interprets the file, rather than to define a new rule (it means the same as ?-, which can also be used to include goals within a source file). This goal tells the interpreter that : (the colon) is a binary infix operator with a precedence level of 50. You can now use a colon between two data items in an argument position to create a two-field structure.

We can use our new operator in structuring the two parts of time values (the hours and the minutes) so that they can be extracted easily. Times constructed this way can be built or separated into their constituent elements through Prolog's pattern matching in predicate parameter positions. For example, consider this:

    write_time( Hours:Minutes ) :- /* Extract structure's parts using a pattern */
        write( Hours ),
        write( ' hours and ' ),
        write( Minutes ),
        write( ' minutes.' ),
        nl.

    /* It can also combine elements into a single structure */
    ?- write_time( 13:15 ).

We can then easily use this new operator to describe times in a convenient fashion in our timetable, which can be represented as a set of Prolog facts. Each "entry" in our timetable can be laid out as a 5-item list, consisting of the flight number, starting city, ending city, departure time, arrival time, and a list of days on which the flight flies:

    timetable( [lp1211, columbus, charlotte, 11:10, 12:20,
                               [ mon, tue, wed, fri, sun ] ] ).

It is then a simple matter to encode the flight timetable as a list of such facts.

You will notice that most of the data is represented in the form of atoms (identifiers that start with lower case letters). It is fine to convert any proper name in the assignment to all lower-case when representing it as an atom.

Write your program as a Prolog predicate called plan_routes that matches the following signature:

plan_routes( From_City, To_City, From_Time, To_Time, Day ) :-
    /* your definition goes here */.

This predicate could be called with specific values for any or all of the parameters, or "don't care" variables for unspecified constraints. If the departure time is specified, any flight plans beginning on or after that time should be included; if the arrival time is specified, any flight plans ending on or before that time should be included.

?- plan_routes( pittsburgh, columbus, _From_Time, 15:00, tue ).
All flight plans from pittsburgh any-time to columbus 15:0 on mon:

    - Plan -------------
    lp1323 from pittsburgh 13:30 to columbus 14:40 tue
    --------------------

?- plan_routes( roanoke, columbus, _From_Time, _To_Time, mon ).

All flight plans from roanoke any-time to columbus any-time on mon:

    - Plan -------------
    lp1458 from roanoke 9:10 to charlotte 10:0 mon
    lp1212 from charlotte 13:20 to columbus 16:20 mon
    --------------------
    - Plan -------------
    lp1458 from roanoke 9:10 to charlotte 10:0 mon
    lp1473 from charlotte 16:30 to columbus 19:30 mon
    --------------------
    - Plan -------------
    lp1458 from roanoke 9:10 to charlotte 10:0 mon
    lp4752 from charlotte 11:40 to raleigh 12:50 mon
    lp4773 from raleigh 13:40 to charlotte 14:50 mon
    lp1473 from charlotte 16:30 to columbus 19:30 mon
    --------------------
    - Plan -------------
    lp1511 from roanoke 12:20 to charlotte 13:10 mon
    lp1473 from charlotte 16:30 to columbus 19:30 mon
    --------------------

?- plan_routes( roanoke, columbus, 15:00, _To_Time, _Day ).

All flight plans from roanoke 15:0 to columbus any-time on any-day:

    no routes available.

In printing out flight data, remember that write and nl are the basic output primitives. write can display any Prolog data structure, including times using our custom : operator. In the header for the list of flight plans, use any-city, any-time, or any-day to indicate unspecified constraints.

Your Prolog implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Prolog predicate should be preceded by a comment block explaining its purpose, the meaning of each parameter, and the general strategy of its implementation if applicable.

Your program will be submitted electronically through the Curator for automatic grading against a randomly generated test suite. To submit your program, login to the Curator using your PID and password. Be sure to select the 91389-CS 3304 Comparative Languages section when logging in. Click on "Submit", choose 3-Prolog from the project drop-down list, click "Browse" to specify your solution, and then click "Upload."

In addition, you must also turn in a printed version of your program source in class according to the rules specified in the syllabus, which also describes the late policy. Your hardcopy printout must match the highest-scoring submission sent to the Curator earliest. In other words, you may not submit your program until it works, go back and add comments and documentation, and then make a final submission of the printable version of your program. Once you receive full credit from the Curator on a submission, that is the version you must print and hand in.