Everything's Beta

%%This program is free software: you can redistribute it and/or modify
%%it under the terms of the GNU General Public License as published by
%%the Free Software Foundation, either version 3 of the License, or
%%(at your option) any later version.
%%This program is distributed in the hope that it will be useful,
%%but WITHOUT ANY WARRANTY; without even the implied warranty of
%%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%%GNU General Public License for more details.
%%For a copy of the license see <http://www.gnu.org/licenses>
 
%Very simple prolog interpreter for a language described like so :
/* <program>         --> <block_stmt>
 
    <statement>       --> <assignment_stmt>
                        | <block_stmt>
                        | <if_stmt>
                        | <while_stmt>
                        | \[ \]
 
    <assignment_stmt> --> \[ <variable>, :=, <expression> \]
 
    <block_stmt>      --> \[ \]
                        | \[ <statement> {, <statement> } \]
 
    <if_stmt>         --> \[ if, <expression>, then, <statement>, else, <statement> \]
 
    <while_stmt>      --> \[ while, <expression>, do, <statement> \]
 
    <expression>      --> <operand> {, ( + | - ), <operand> }
 
    <operand>         --> <variable>
                        | <integer>
 
    <variable>        --> a | b | c | d | e
 
    <integer>         --> any integer, as prolog understands it
*/
 
%==================================================================
% <program>         --> <block_stmt>
%  Parameters:
%      Code   :  The list that holds the input program
%      Vars   :  The state of the variables when the program starts
%      NewVars:  The state of the variables after the program runs
%------------------------------------------------------------------
program(Code, Vars, NewVars) :-
    allNum(Vars),                     %validate input arg. list
    blockStmt(Code, Vars, NewVars).
 
 
%==================================================================
% <statement>       --> <assignment_stmt>
%                        | <block_stmt>
%                        | <if_stmt>
%                        | <while_stmt>
%                        | \[ \]
%    Parameters:
%      Code   :  The list that holds the statement to evaluate
%      Vars   :  The state of the variables before the statement evals
%      NewVars:  The state of the variables after the statement evals
%------------------------------------------------------------------
statement(Code, Vars, NewVars) :-
    assignmentStmt(Code, Vars, NewVars);
    ifStmt(Code, Vars, NewVars);
    whileStmt(Code, Vars, NewVars);
    blockStmt(Code, Vars, NewVars).
 
 
%==================================================================
% <assignment_stmt> --> \[ <variable>, :=, <expression> \]
%    Parameters:
%      1stParam:  The list that holds the statement to evaluate
%                  For it to be an assignment statement
%                  format : Variable, :=, and the expression
%      Vars    :  The state of the variables before the statement evals
%      NewVars :  The state of the variables after the statement evals
%------------------------------------------------------------------
assignmentStmt([Variable, :=|Expression], Vars, NewVars):-
    atom(Variable),
    expression(Result, Expression, Vars),
    integer(Result),
    variable(Variable, Result, NewVars, Vars).
 
 
%==================================================================
% <variable>        --> a | b | c | d | e
% Set & get the value of a valid variable
%     Parameters:
%       1st Param: the variable
%       2nd Param: the value to set the variable to
%       3rd Param: the new variable list
%       4th Param: the old variable list.
% Note: I could have done a list index
%  based approach so that it would be more easily scalable.
%  But I grew attached to this snippet's simplicity and it works
%  good enough for this.
%------------------------------------------------------------------
variable(a, A, [A, B, C, D, E], [_, B, C, D, E]).
variable(b, B, [A, B, C, D, E], [A, _, C, D, E]).
variable(c, C, [A, B, C, D, E], [A, B, _, D, E]).
variable(d, D, [A, B, C, D, E], [A, B, C, _, E]).
variable(e, E, [A, B, C, D, E], [A, B, C, D, _]).
 
 
%==================================================================
% <expression>     --> <operand> {, ( + | - ), <operand> }
%   Parameters:
%      Result    : the result of the expression
%      Expression: the expression to eval
%      Vars      : the value of the variables
%------------------------------------------------------------------
expression(Result, Expression, Vars):-
    expressionHelper(Result, [+|Expression], Vars, 0).
 
 
%==================================================================
% Evaluates the value of the expression.
%   Parameters:
%      Result    : the result of the expression
%      2nd Param : the expression left to eval
%      Vars      : the value of the variables
%      Accum     : accumulator to keep rack of the value
%------------------------------------------------------------------
expressionHelper(Result, [], _, Accum):-
    Result is Accum.
expressionHelper(Result, [+, Left|Others], Vars, Accum):-
    operand(Left, NumLeft, Vars),
    expressionHelper(Result, Others, Vars, Accum + NumLeft).
expressionHelper(Result, [-, Left|Others], Vars, Accum):-
    operand(Left, NumLeft, Vars),
    expressionHelper(Result, Others, Vars, Accum -  NumLeft).
 
 
%==================================================================
%  <operand>       --> <variable>
%                    | <integer>
%   Set Val as the numerical value of V
%   i.e if V is an integer, set V = V
%       if V is a variable, set Val = value of the variable
%   Parameters:
%      1st Param: the variable to set
%      2nd Param: the value to set variable to
%      3rd param: the variable list
%------------------------------------------------------------------
operand(V, V, _):-
    integer(V).
operand(V, Val, Vars):-
    atom(V),
    variable(V, Val, Vars, _).
 
 
%==================================================================
% <block_stmt>     --> \[ \]
%                    | \[ <statement> {, <statement> } \]
%    Parameters:
%      1stParam:  The list that holds the statement to evaluate
%      Vars    :  The state of the variables before the statement evals
%      NewVars :  The state of the variables after the statement evals
%------------------------------------------------------------------
blockStmt([], Vars, Vars).
blockStmt([Stmt|Rest], Vars, NewVars):-
    compound(Stmt),    %make sure the statement is a list
    statement(Stmt, Vars, NVars),
    blockStmt(Rest, NVars, NewVars).
 
 
%==================================================================
% <if_stmt>  --> \[ if, <expression>, then, <statement>, else, <statement>\]
%    Parameters:
%      1stParam:  The list that holds the statement to evaluate,
%                 if stmt format starts with if
%      Vars    :  The state of the variables before the statement evals
%      NewVars :  The state of the variables after the statement evals
%------------------------------------------------------------------
ifStmt([if|Rest], Vars, NewVars):-
    pos(Rest, then, Index),
    split(Rest, Index, Expr, [then, ThenStmt, else, ElseStmt]),
    expression(Result, Expr, Vars),
    ( Result > 0
    -> statement(ThenStmt, Vars, NewVars),
       statement(ElseStmt, Vars, _)  %  run to make sure else stmt is valid
    ;  statement(ElseStmt, Vars, NewVars),
       statement(ThenStmt, Vars, _)  % run to make sure then stmt is valid
    ).
 
 
%==================================================================
% <while_stmt>     --> \[ while, <expression>, do, <statement> \]
%    Parameters:
%      1stParam:  The list that holds the statement to evaluate
%                 while stmt format starts with while
%      Vars    :  The state of the variables before the statement evals
%      NewVars :  The state of the variables after the statement evals
%------------------------------------------------------------------
whileStmt([while|Rest], Vars, NewVars):-
    pos(Rest, do, Index),
    split(Rest, Index, Expr, [do|Stmt]),
    expression(Result, Expr, Vars),
    (Result >0
    -> statement(Stmt, Vars, NVars),
       whileStmt([while|Rest], NVars, NewVars)
    ;  statement(Stmt, Vars, _) % run to make sure its valid
    ).
 
 
%==================================================================
% Find first position Item occurs in the list
%    Parameters:
%      1st Param: the list to search
%      Item     : the element to find
%      C        : this is set to the position of the item, if found.
%------------------------------------------------------------------
pos([H|T], Item, C) :-
    len(T, L),
    (L > 0),
    (H \= Item
    -> pos(T, Item, P), C is P+1
    ;  C is 0
    ).
 
 
%==================================================================
% Length of a list
%    Paramters:
%      1st Param: The list to find length of
%      2nd Param: the length of the list
%------------------------------------------------------------------
len([], 0).
len([_|T], N) :-
    len(T, X), N is X+1.
 
 
%==================================================================
% Split a list by position
%    Parameters:
%      1st Param: the list to split
%      2nd Param: the position to split the list on
%      3rd Param: the first partition
%      4th Param: the second partition
%------------------------------------------------------------------
split(A, 0, [], A).
split([H|T], Index, [H|Rest], TL) :-
    I is Index - 1,
    split(T, I, Rest, TL).
 
 
%==================================================================
% Make sure all elements in a list are numbers
%  Used to validate the incoming argument list
%    Parameter:
%       1st Param: the lsit to check
%------------------------------------------------------------------
allNum([]).
allNum([H|T]):-
    number(H),
    allNum(T).

%%This program is free software: you can redistribute it and/or modify
%%it under the terms of the GNU General Public License as published by
%%the Free Software Foundation, either version 3 of the License, or
%%(at your option) any later version.
%%This program is distributed in the hope that it will be useful,
%%but WITHOUT ANY WARRANTY; without even the implied warranty of
%%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%%GNU General Public License for more details.
%%For a copy of the license see <http://www.gnu.org/licenses/>.
%%
%%   Prolog route planner.
 
%% operator symbol for time structure
:-  op( 50, xfy, : ).
 
%% Paths between cities
path(lp1211, columbus,   charlotte,  11:10,  12:20,  [mon, tue, wed, fri, sun ]).
path(lp1212, charlotte,  columbus , 13:20, 16:20, [mon, tue, wed, fri, sun ]).
path(lp1322, columbus, pittsburgh, 11:30,12:40,[tue, thu ]).
path(lp1323, pittsburgh, columbus , 13:30, 14:40,  [tue, thu ]).
path(lp1458, roanoke, charlotte , 09:10, 10:00, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1459, charlotte, roanoke , 11:00, 13:50, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1472, columbus, charlotte,  20:30, 21:30, [mon, wed, thu, sat]).
path(lp1473, charlotte, columbus , 16:30, 19:30, [mon, wed, thu, sat]).
path(lp1510, charlotte, roanoke , 08:30, 11:20, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1511, roanoke, charlotte , 12:20, 13:10, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1613, pittsburgh, charlotte , 09:00, 09:40, [mon, tue, wed, thu, fri, sat]).
path(lp1614, charlotte, pittsburgh, 09:10, 11:45, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1620, pittsburgh, roanoke , 07:55, 08:45, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1621, roanoke , pittsburgh, 09:25, 10:15, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1623, roanoke , pittsburgh, 12:45, 13:35, [mon, tue, wed, thu, fri, sat, sun]).
path(lp1805, charlotte,  pittsburgh, 14:45, 17:20, [mon, tue, wed, thu, fri, sun]).
path(lp1806, pittsburgh, charlotte , 16:10, 16:55, [mon, tue, wed, thu, fri, sun]).
path(lp4732, charlotte , raleigh , 09:40, 10:50, [mon, tue, wed, thu, fri, sat, sun]).
path(lp4733, raleigh , charlotte,  09:40, 10:50, [mon, tue, wed, thu, fri, sat, sun]).
path(lp4752, charlotte,  raleigh , 11:40, 12:50, [mon, tue, wed, thu, fri, sat, sun]).
path(lp4773, raleigh , charlotte,  13:40, 14:50, [mon, tue, wed, thu, fri, sat, sun]).
path(lp4822, charlotte,  raleigh , 18:40, 19:50, [mon, tue, wed, thu, fri]).
path(lp4833, raleigh , charlotte,  19:40, 20:50, [mon, tue, wed, thu, fri]).
 
%% Tests to see H2:M2 is atleast 45 minutes later than H1:M1
canTransfer( H1:M1, H2:M2):-
((60 * (H2 - H1) + ( M2 - M1))  >= 45).
 
%% Valid times are initialized variables
%% that are number values
validTime(H1:M1):-
nonvar(H1),
nonvar(M1),
number(H1),
number(M1).
 
%% is H1:M1 earlier than H2:M2 ?
isEarlierThan(H1:M1, H2:M2):-
(validTime(H2:M2)
-> ((H2 == H1 , M1 < M2) ;
(H1 < H2 ))
;  (H2 = H1 , M2 = M1)
).
 
%% is H1:M1 later than H2:M2 ?
isLaterThan(H1:M1, H2:M2):-
(validTime(H2:M2)
-> ((H2 == H1 , M1 > M2) ;
(H1 > H2 ))
;  (H2 = H1, M2 = M1)
).
 
%% Base case: next node is the destination
route(From,To,DeptTime,ArrTime,Day,[FlNum],Visited):-
findPath(FlNum,From,To,Dept1,Arr1,Day),
not(member(To,Visited)),
isLaterThan(Dept1,DeptTime),
isEarlierThan(Arr1,ArrTime).
 
%% Recursive case: the destinaion may be somewhere out there.
route(From,To,DeptTime,ArrTime,Day,[FlNum|Route], Visited):-
findPath(FlNum,From,StopOver,Dept1,Arr1,Day),
not(member(StopOver,Visited)),
route(StopOver,To,Dept2,Arr2, Day,Route,[StopOver|Visited]),
isLaterThan(Dept1,DeptTime),
isEarlierThan(Arr2,ArrTime),
canTransfer(Arr1,Dept2).
 
%% A valid path exists in the same day
findPath(FlNum,From,To,FromTime,ToTime,Day):-
path(FlNum,From,To,FromTime,ToTime,Days),
member(Day,Days).
 
%% plan_route( From_City, To_City, From_Time, To_Time, Day, Route)
%% route is list of flight nums, [] is visited flight nums
%% Note, actual from_time can be later than From_Time,
%%       actual to_time can be earlier than To_Time
plan_route(From_City,To_City,From_Time,To_Time,Day, Route):-
route(From_City,To_City,From_Time,To_Time,Day,Route,[From_City]).