seg( lga, ord, 600, 100).
seg(lga, mia, 450, 90).
seg(lga, hou, 850, 350).
seg(lga, lax, 1200, 275).
seg(ord, lga, 450, 120).
seg(ord, mia, 525, 80).
seg(ord,lax, 700, 150).
seg(mia, hou, 250, 75).
seg(mia, lga, 400, 80).
seg(hou, lga, 750, 300).
seg(lax, lga, 1300, 310).
seg(mia, ord, 500, 70).
seg(lax, ord, 600, 175).
seg(hou, mia, 250, 75).
seg(lax, jpn, 3500, 750).


/*Split the main predicate into oneway and roundtrip versions   */
/*  Note:  This predicate also returns the cities in the route. */
/*         This was not required, but made debugging easier!    */


flight(Depart, Destin, oneway, Segments, Cost, Route) :- 
    onewayflight(Depart, Destin, Segments, Cost, Route).
 
flight(Depart, Destin, roundtrip, Segments, Cost, Route) :- 
    roundtripflight(Depart, Destin, Segout, Cout, Rout),
    roundtripflight(Destin, Depart, Segin, Cin, Rin),
    append(Rout,Rin,Route),
    Segments is Segout + Segin,
    Cost is Cout + Cin.

/*Main data structure is the compound term path(O,R,T).                 */
/*   Where T is the flight path so far (list of cities called the trail)*/
/*   Where O is the sum of the oneway fares in the trail                */
/*   Where R is the sum of the roundtrip fares in the trail             */

    
onewayflight(Depart, Destin, Segments, Cost, Route) :- 
    go(Depart, Destin, path(0,0,[]), path(Cost,_,R)), 
    reverse(R, Route),
    length(R, SegmentsPlusOne),
    Segments is SegmentsPlusOne - 1.

roundtripflight(Depart, Destin, Segments, Cost, Route) :- 
    go(Depart, Destin, path(0,0,[]), path(_,Cost,R)), 
    reverse(R, Route),
    length(R, SegmentsPlusOne),
    Segments is SegmentsPlusOne - 1.

/*go enlarges the trail from Place, trying to reach Destin */

go(X, X, path(A,B,C), path(A,B,[X|C])).
go(Place, Destin ,path(CurCostOW,CurCostRT,Trail), R) :-
    legalnode(Place, path(CurCostOW,CurCostRT,Trail), Next, NewCostOW, NewCostRT), 
    go(Next, Destin ,path(NewCostOW,NewCostRT,[Place|Trail]), R).

/*legalnode checks for a city we haven't been to and adds its cost to the path() */

legalnode(From,path(CurCostOW,CurCostRT,Trail),To,NewCostOW,NewCostRT) :- 
    seg(From,To,CostOneWay,CostRoundTrip), 
    legal(To,Trail), 
    NewCostOW is CurCostOW + CostOneWay,
    NewCostRT is CurCostRT + CostRoundTrip.

/*legal actually searches the trail to see if we've been to city X before */

legal(_,[]).
legal(X,[H|T]) :- X \== H, legal(X,T).


/* Helper functions */

reverse([],[]).
reverse([H|T],L) :- reverse(T,Z), append(Z,[H],L).

append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).