% COMP 280, Hwk 9 : Airline information system
% Kathi Fisler
% April 7, 2000

%%%%%%%% Problem 1 : Create a database

% data organization:
%
%   flight(number, airline, from, to, departure time, arrival time)
%
% where times are two element lists [hour, minutes]

% Sample Database

flight(1, sw, austin, houston, [13,00], [13,45]).
flight(2, sw, austin, dallas, [15,15], [16,05]).
flight(3, sw, dallas, houston, [17,30], [18,25]).
flight(4, sw, houston, austin, [9,00], [9,45]).

flight(25, am, dallas, chicago, [12,30], [15,40]).
flight(26, am, chicago, dallas, [13,10], [14,50]).
flight(27, am, chicago, boston, [10,30], [13,20]).
flight(28, am, boston, newyork, [8,30], [9,10]).
flight(47, am, newyork, dallas, [11,10], [15,00]).
flight(92, am, dallas, boston, [13,30], [17,50]).

flight(155, co, austin, houston, [10,13], [11,00]).
flight(122, co, houston, austin, [12,23], [13,10]).
flight(92, co, providence, houston, [6,18], [10,00]).
flight(93, co, houston, newyork, [11,22], [15,43]).
flight(167, co, newyork, providence, [14,21], [15,10]).
flight(89, co, newyork, boston, [17,13], [18,25]).
flight(223, co, boston, providence, [15,15], [16,00]).

%%%%%%%%% Helper rules

% direct_flight(fromcity, tocity)
% true when the database contains a flight from fromcity to tocity

direct_flight(FromCity, ToCity) :- flight(_, _, FromCity, ToCity, _, _).

% services(airline, city)
% true when there is a flight into or out of city on airline

services(Airline, City) :- flight(_, Airline, City, _, _, _).
services(Airline, City) :- flight(_, Airline, _, City, _, _).

% service_with(airline, city1, city2)
% true when airline has a flight between city1 and city2

service_with(Airline, City1, City2) :- 
  flight(_, Airline, City1, City2, _, _).

service_with(Airline, City1, City2) :- 
  flight(_, Airline, City2, City1, _, _).

% hour_time_diff(t1, t2)
% true when there is an hour time difference between t1 and t2

hour_time_diff([Hour1, _Min1], [Hour2, _Min2]) :-
  H is Hour1 + 1,
  Hour2 > H.
  
hour_time_diff([Hour1, Min1], [Hour2, Min2]) :-
  H is Hour1 + 1,
  Hour2 = H,
  Min2 >= Min1.

% length(L, num)
% true when num is the length of list L.

length([],0).

length([_|T],N) :-
  length(T, N1),
  N is N1 + 1.

% is_Last(elt, list)
% true when element is the last item in list

is_Last(E, [E]).
is_Last(E, [_H | T]) :- is_Last(E, T).

% member(Element, List)
% true if Element is in List

member(E, [E|_]).
member(E, [_|T]) :- member(E,T).

% no_duplicates(list)
% true if list has no duplicated elements

no_duplicates([]).
no_duplicates([H | T]) :- 
  \+ member(H, T),
  no_duplicates(T).

%%%%%%% Question 2
  
% has-route (from_city, to_city)
% determines whether there exist flights from first city to second
% does not expect the two cities to be the same

:- table has_route/2.

has_route(FromCity, ToCity) :- direct_flight(FromCity, ToCity).

has_route(FromCity, ToCity) :- 
  direct_flight(FromCity, I),
  has_route(I, ToCity).

%%%%%%% Question 3

% produce_route (from_city, to_city, route)
% route is list of cities on route from first city to second city

:- table produce_route/2.

produce_route(FromCity, ToCity, [FromCity, ToCity]) :-
  direct_flight(FromCity, ToCity).

produce_route(FromCity, ToCity, [FromCity | Tail]) :-
  direct_flight(FromCity, I),
  produce_route(I, ToCity, Tail).

%%%%%%% Question 4

% produce_schedule(from_city, to_city, schedule) 
% schedule is a list of lists of airlines, flight numbers, arrival times, and
%  departure times.  There should be at least 1 hour between the 
%  arrival and departure times of consecutive flights

produce_schedule(FromCity, ToCity, [[Airline, Num, Dep, Arr]]) :-
  flight(Num, Airline, FromCity, ToCity, Dep, Arr).

produce_schedule(FromCity, ToCity, [[Air1, Num1, Dep1, Arr1], 
                                    [Air2, Num2, Dep2, Arr2] | SchedTail]) :-
  flight(Num1, Air1, FromCity, I, Dep1, Arr1),
  produce_schedule(I, ToCity, [[Air2, Num2, Dep2, Arr2] | SchedTail]),
  hour_time_diff(Arr1, Dep2).

%%%%%%% Question 5

% hub(airline, city)
% determines whether airline has flights between hub and half of
%   cities it services

hub(Airline, City) :- 
  setof(C, services(Airline, C), Cities),
  length(Cities, CityCount),
  setof(C, service_with(Airline, City, C), HubReach),
  length(HubReach, HubCount),
  DoubleCount is HubCount * 2,
  DoubleCount > CityCount.
 
%%%%%%% Question 6

% route_on_airline(Airline, FromCity, ToCity, Route) 
% true when Route goes from FromCity to ToCity via flights on airline

route_on_airline(Airline, FromCity, ToCity, [FromCity, ToCity]) :- 
  flight(_, Airline, FromCity, ToCity, _, _).

route_on_airline(Airline, FromCity, ToCity, [FromCity | IRoute]) :- 
  flight(_, Airline, FromCity, Intermed, _, _),
  route_on_airline(Airline, Intermed, ToCity, IRoute).

% is_tour(list)
% true when list has the same first and last elements and has no
% duplicated elements other than the first and last elements

is_tour([C1, C2, C3 | Rest]) :-
  is_Last(C1, [C3 | Rest]),
  no_duplicates([C2, C3 | Rest]).

% simple_tour(Airline, City, Route)
% true if can fly from City to itself via Route which repeats no
%   cities other than City in the first and last positions

simple_tour(Airline, City, Route) :-
  route_on_airline(Airline, City, City, Route),
  is_tour(Route).

%%%%%%% Question 7

% full_tour(Airline, City, Route)
% true if can fly from City to itself via Route which repeats no
%   cities other than City in the first and last positions and
%   contains all cities serviced by airline


full_tour(Airline, City, Route) :-
  simple_tour(Airline, City, Route),
  setof(C, services(Airline, C), AllCities),
  length(Route, Rlen),
  length(AllCities, Alen),
  Rlen is Alen + 1.