/*
 * Gaurav S. Kc
*/

?- use_module(library(lists)).
?- use_module(library(system)).



/* ----------------------------------------------------------------------- */

load :- consult('u2').

/* Starting state, limit on maximum time allowed */
start(0, [t,1,2,5,10], 20).
start(1, [t,1,2,5,10,12,15], 100).
start(2, [t,1,2,5,10,12,15,20], 100).
start(3, [t,1,2,5,10,12,15,20], 68).


/*
 * Hill-climbing search is not implemented here because
 *   i: it will never find a solution,
 *  ii: cannot start from random states; there is only one
 *        well-defined start state.
 *
 * For all 3 types of searches, the predicate 'search' returns a single
 * solution in 'Soln'. Modifying the code to return multiple solutions
 * is very straightforward and simple, cf. body of 'search' below.
 *
 * One major limitation of this implementation is that it is *not* designed
 * to succeed in cases when multiple members of the band take the same
 * amount of time to cross the bridge. Enabling the program to handle this
 * will require more work to determine the possible combinations of people
 * crossing the bridge during any transition.
 *
 * In this implementation, each node in the search tree is represented as
 *    a list of configurations -- this is the list of states that were
 *    passed before reaching that particular point. Each configuration,
 *    however, is also accompanied by 2 numbers -- the second one is the
 *    cost-so-far, and the first one has a different meaning in each of 
 *    the differennt search algorithms:
 *             - depth  - nothing
 *             - greedy - heuristic of newest state
 *             - A*     - heuristic of newest state + cost-so-far.
 *
 * In case of 'greedy' and 'A*' transitions, this first number is what
 *    determines how the 'queue' is ordered. The implementation of Prolog
 *    is such that when it orders a list of data structures, the ordering
 *    is according to the first ordinal value it sees, and in this case,
 *    I have taken measures to ensure that it is the correct value for
 *    both greedy and A* searches.
*/


main :-
  tell('output.txt'),
  datime(D1_1), d(1), datime(D1_2), write(D1_1), 
  write(' -- '), write(D1_2), nl, nl, nl, nl,
  datime(G1_1), g(1), datime(G1_2), write(G1_1), 
  write(' -- '), write(G1_2), nl, nl, nl, nl,
  datime(A1_1), a(1,a), datime(A1_2), write(A1_1), 
  write(' -- '), write(A1_2), nl, nl, nl, nl,
  datime(A2_1), a(1,b), datime(A2_2), write(A2_1), 
  write(' -- '), write(A2_2), nl, nl, nl, nl,
  datime(A3_1), a(1,c), datime(A3_2), write(A3_1), 
  write(' -- '), write(A3_2), nl, nl, nl, nl,
  datime(D2_1), d(2), datime(D2_2), write(D2_1), 
  write(' -- '), write(D2_2), nl, nl, nl, nl,
  datime(G2_1), g(2), datime(G2_2), write(G2_1), 
  write(' -- '), write(G2_2), nl, nl, nl, nl,
  datime(D3_1), d(3), datime(D3_2), write(D3_1), 
  write(' -- '), write(D3_2), nl, nl, nl, nl,
  datime(G3_1), g(3), datime(G3_2), write(G3_1), 
  write(' -- '), write(G3_2), nl, nl, nl, nl,
  datime(A4_1), a(2,b), datime(A4_2), write(A4_1), 
  write(' -- '), write(A4_2), nl, nl, nl, nl,
  datime(A5_1), a(2,c), datime(A5_2), write(A5_1), 
  write(' -- '), write(A5_2), nl, nl, nl, nl,
  told.


/* Depth first search */
d(N) :-
  start(N, S, L),
  search(depth, L, [[ (0-0, S-[]) ]], Soln),
  write('Solution found by (d)epth-first search'), nl,
  write('  starting state: '), write(S-[]), nl,
  write('  with a limit of '), write(L), write(' steps.'), nl,
  write('    steps            *states* '), nl,
  gPrint(Soln).

/* Greedy search with heuristic 'a' */
g(N) :-
  start(N, S, L),
  heuristic(a, H, S-[]),
  search(greedy, L, [[ (H-0, S-[]) ]], Soln),
  write('Solution found by (g)reedy search'), nl,
  write('  starting state: '), write(S-[]), nl,
  write('  with a limit of '), write(L), write(' steps.'), nl,
  write('    steps            *states* '), nl,
  gPrint(Soln).

/* A* search with all three heuristics */
a(N, Heur) :-
  start(N, S, L),
  heuristic(Heur, H, S-[]),
  search(astar(Heur), L, [[ ( H-0 , S-[] ) ]], Soln),
  write('Solution found by A* search using heuristic '), write(Heur), nl,
  write('  starting state: '), write(S-[]), nl,
  write('  with a limit of '), write(L), write(' steps.'), nl,
  write('    steps            *states* '), nl,
  gPrint(Soln).

/* Pretty-printing sub-routines */
gggPrint((X,Y)) :-
  write('    ('), write(X),
  write(') -- '), write(Y), nl.
ggPrint([]).
ggPrint([X|Xs]) :-
  ggPrint(Xs),
  gggPrint(X).
gPrint([]).
gPrint([X|Xs]) :-
  write('---------------------------------------'), 
  nl, ggPrint(X), gPrint(Xs), nl.

/* ----------------------------------------------------------------------- */




/* ----------------------------------------------------------------------- */

/* -- heuristic(type, HEURISTIC_VALUE, LEFT_SIDE-RIGHT_SIDE) -- */

/* Heuristic-value of goal state is '0' */
heuristic(_, 0, []-[_GoalState|_RestGoalState]).

/* Heuristic 'a': time reqd for slowest person yet to cross */
heuristic(a, Z, [t|X]-Y) :- is_list(Y), max_list(X, Z).
heuristic(a, Z, X-[t|_Y]) :- max_list(X, Z).

/* Heuristic 'b': time reqd for every other person [decreasing order] */
heuristic(b, Z, [t|X]-Y) :- is_list(Y), sumAlt(X, Z).
heuristic(b, Z, X-[t|_Y]) :- sumAlt(X, Z).

/*
 * Heuristic 'c': same as 'b' plus time reqd for fastest person to bring
 *   back the torch iff torch is on the 'other' side, otherwise just 'b'
*/
heuristic(c, Z, [t|X]-Y) :-
  is_list(Y), sumAlt(X, Z).
heuristic(c, Z, X-[t|Y]) :-
  sumAlt(X, X2), min_list(Y, Y2),
  Z is X2 + Y2.

/* X is in increasing order, use sumAlt2(RevX) to get decreasing order */
sumAlt(X, S) :-
  reverse(X, RevX),
  sumAlt2(RevX, S).

/* sums every alternate element of list */
sumAlt2([], 0).
sumAlt2([X], X).
sumAlt2([X,_Y|Z], S) :-
  sumAlt2(Z, S2),
  S is S2 + X.

/* ----------------------------------------------------------------------- */




/* ----------------------------------------------------------------------- */

/* Stop searching when no more states can be expanded */
search(_S_Method, _MaxCost, [], []).

/* If 'Soln' matches pattern of goal state ... */
search(S_Method, MaxCost, [Soln|Paths], [Soln|Solns]) :-
  Soln = [ (_Heur-Cost, []-_GoalPath) |_RestOfPath],
  MaxCost >= Cost, !, 
  (Solns = []
  /* To exit after a single solution is found */
  ;
  /*
   * Modify code so that the following line executes
   * in case more than one solution is required.
  */
  (false, search(S_Method, MaxCost, Paths, Solns))).

/* Solution not found yet; make transitions and store in Newpaths */
search(S_Method, MaxCost, [Path|Paths], Solns) :-
  transition(S_Method, [Path|Paths], NewPaths),
  search(S_Method, MaxCost, NewPaths, Solns).

/* ----------------------------------------------------------------------- */




/* ----------------------------------------------------------------------- */

/* Some sub-routines to determine set differences/unions/intersections */ 

difference(XS, YS, Z) :-
  findall(X, (member(X, XS), \+ member(X, YS)), Z).

merge([], X, X).
merge(X, [], X).
merge([X|Xs], [Y|Ys], [X|Zs]) :-
  X < Y, merge(Xs, [Y|Ys], Zs).
merge([X|Xs], [Y|Ys], [Y|Zs]) :-
  Y < X, merge([X|Xs], Ys, Zs).
  
/* pairs(..) ignores the case when 2 values in All are equal */
pairs(All, Pairs) :-
  findall([X,Y],
    (member(X, All),
     member(Y, All),
     X < Y),
  Pairs).

/* ----------------------------------------------------------------------- */





/* ----------------------------------------------------------------------- */

/* 
 * Append new paths to the front of the list for
 *   transitions in which the torch is carried
 *   back across the bridge by 1 person coming
 *   back for the rest.
*/
transition(depth, [ Path | Paths ], TotalPaths) :-
  Path = [C_State|_Rest],
  C_State = (_Heur-Cost, W-[t|X]),
  findall( (_Heur-NewCost, [t|P_W]-X_P) ,
    (member(P, X),
     difference(X, [P], X_P),
     merge([P], W, P_W),
     NewCost is Cost + P),
    NewFringe),
  findall([F|Path], member(F, NewFringe), NewPaths),
  append(NewPaths, Paths, TotalPaths).
     

/* 
 * Append new paths to the front of the list for
 *   transitions in which the torch is carried
 *   across the bridge by 2 people crossing over.
*/
transition(depth, [ Path | Paths ], TotalPaths) :-
  Path = [C_State|_Rest],
  C_State = (_Heur-Cost, [t|W]-X),
  pairs(W, Pairs),
  findall( (_Heur-NewCost, W_P-[t|W_P_X]) ,
    (member(P, Pairs),
     difference(W, P, W_P),
     merge(P, X, W_P_X),
     P = [_Small,Big],
     NewCost is Cost + Big),
    NewFringe),
  findall([F|Path], member(F, NewFringe), NewPaths),
  append(NewPaths, Paths, TotalPaths).

/* ----------------------------------------------------------------------- */




/* ----------------------------------------------------------------------- */

/* 
 * Append new paths [after sorting according to the heuristic] to 
 *   the front of the list for transitions in which the torch is 
 *   carried back across the bridge by 1 person coming back for 
 *   the rest.
*/
transition(greedy, [ Path | Paths ], TotalPaths) :-
  Path = [C_State|_Rest],
  C_State = (_Heur-Cost, W-[t|X]),
  findall( (NewHeur-NewCost, [t|P_W]-X_P) ,
    (member(P, X),
     difference(X, [P], X_P),
     merge([P], W, P_W),
     NewCost is Cost + P,
     heuristic(a, NewHeur, [t|P_W]-X_P)),
    NewFringe),
  findall([F|Path], member(F, NewFringe), NewPaths),
  append(NewPaths, Paths, TempTotalPaths),
  sort(TempTotalPaths, TotalPaths).
     

/* 
 * Append new paths [after sorting according to the heuristic] to 
 *   the front of the list for transitions in which the torch is
 *   carried across the bridge by 2 people crossing over.
*/
transition(greedy, [ Path | Paths ], TotalPaths) :-
  Path = [C_State|_Rest],
  C_State = (_Heur-Cost, [t|W]-X),
  pairs(W, Pairs),
  findall( (NewHeur-NewCost, W_P-[t|W_P_X]) ,
    (member(P, Pairs),
     difference(W, P, W_P),
     merge(P, X, W_P_X),
     P = [_Small,Big],
     NewCost is Cost + Big,
     heuristic(a, NewHeur, W_P-[t|W_P_X])),
    NewFringe),
  findall([F|Path], member(F, NewFringe), NewPaths),
  append(NewPaths, Paths, TempTotalPaths),
  sort(TempTotalPaths, TotalPaths).

/* ----------------------------------------------------------------------- */




/* ----------------------------------------------------------------------- */

/* 
 * Append new paths to the the list for transitions in which the torch is 
 *   carried back across the bridge by 1 person coming back for the rest.
 *   The whole list is then sorted by (heuristic+cost_so_far)
*/
transition(astar(H), [ Path | Paths ], TotalPaths) :-
  Path = [C_State|_Rest],
  C_State = (_Heur-Cost, W-[t|X]),
  findall( (TotalCost-NewCost, [t|P_W]-X_P) ,
    (member(P, X),
     difference(X, [P], X_P),
     merge([P], W, P_W),
     NewCost is Cost + P,
     heuristic(H, NewHeur, [t|P_W]-X_P),
     TotalCost is NewHeur + NewCost),
    NewFringe),
  findall([F|Path], member(F, NewFringe), NewPaths),
  append(NewPaths, Paths, TempTotalPaths),
  sort(TempTotalPaths, TotalPaths).
     

/* 
 * Append new paths the list for transitions in which the torch is
 *   carried across the bridge by 2 people crossing over.
 *   The whole list is then sorted by (heuristic+cost_so_far)
*/
transition(astar(H), [ Path | Paths ], TotalPaths) :-
  Path = [C_State|_Rest],
  C_State = (_Heur-Cost, [t|W]-X),
  pairs(W, Pairs),
  findall( (TotalCost-NewCost, W_P-[t|W_P_X]) ,
    (member(P, Pairs),
     difference(W, P, W_P),
     merge(P, X, W_P_X),
     P = [_Small,Big],
     NewCost is Cost + Big,
     heuristic(H, NewHeur, W_P-[t|W_P_X]),
     TotalCost is NewHeur + NewCost),
    NewFringe),
  findall([F|Path], member(F, NewFringe), NewPaths),
  append(NewPaths, Paths, TempTotalPaths),
  sort(TempTotalPaths, TotalPaths).

/* ----------------------------------------------------------------------- */
