/*  Methods of Artificial Intelligence WS02/03
    1st Programming assignment

    *** Search Strategies ***

    authors: Robert Freund, Sebastian Bitzer

    possible callings:
    search_<S>(a,Path). where <S> is element of {'a','b','d','h','u'} e.g.: search_a for A*
    time((search_<S>(a,Path),write('----------'),nl,fail)).
    search(+Start,+EndP,+Expand,+Strategy,-Path)

    explanation of abbreviations:

        A       - agenda                format: [P1,P2,...,Pn]
        A_R     - rest of agenda        format: [P2,...,Pn]
        C       - costs                 format: [Fc,Gc] or [Gc,Gc] or [Hc,Gc] (according to strategy)
        C_L     - closed List           format: [N1,...,Nn]
        Fc      - overall costs from start node to end node (=Hc+Gc)
        Gc      - real costs            format: a real number (or integer)
        Hc      - heuristic costs       format: a real number (or integer)
        L       - list                  format: a list
        N       - node                  format: a single node, e.g. 'a'
        P       - path                  format: [C,N1,N2,...,Nn]
        P_L     - list of paths         format: [P1,P2,...,Pn]
        P_R     - rest of path          format: [N1,N2,...,Nn]
        R       - rest                  format: several
        Str     - strategy              format: 'A*', 'depth-first', 'breadth-first', 'hill-climbing', 'uniform-cost'
        Succ    - successor             format: [N,Gc,Successor]
        Succ_L  - list of successors    format: [Succ1,Succ2,...,Succn]


*/

%------------------------------------------------------------------------------
% build initial Path from start node
%------------------------------------------------------------------------------
start(N,Start_P):-
    h(N,Hc),
    Start_P = [[Hc,0],N].
    

%------------------------------------------------------------------------------
% graph, format: edge(N,Gc,Succ).
%------------------------------------------------------------------------------
edge(a,1,b).
edge(a,3,c).
edge(b,3,e).
edge(b,2,h).
edge(b,2,i).
edge(c,4,d).
edge(c,4,f).
edge(d,1,f).
edge(e,1,j).
edge(e,2,k).
edge(f,2,g).
edge(g,2,i).
edge(h,2,i).
edge(i,1,c).
edge(j,3,l).
edge(k,2,l).
edge(l,1,h).

%------------------------------------------------------------------------------
% definition of final node
%------------------------------------------------------------------------------
end(g).


%------------------------------------------------------------------------------
% find successor nodes, add heuristic
%------------------------------------------------------------------------------
succs(N,Succ_L) :-
   findall([Gc,Succ],edge(N,Gc,Succ),Succ_L1),
   add_h(Succ_L1,Succ_L).

% add heuristic
add_h([],[]).
add_h([[Gc,N]|R],[[Hc,Gc,N]|R1]) :-
   h(N,Hc),
   add_h(R,R1).


%------------------------------------------------------------------------------
% heuristic costs, format: h(N,Hc).
%------------------------------------------------------------------------------
h(a,7).
h(b,6).
h(c,5).
h(d,2).
h(e,4).
h(f,2).
h(g,0).
h(h,5).
h(i,5).
h(j,8).
h(k,7).
h(l,6).


%------------------------------------------------------------------------------
% auxiliary predicate for calling different search strategies
%------------------------------------------------------------------------------
search_a(Start_node,P) :-
   search(Start_node,end,succs,'A*',P),
   out(P).

search_b(Start_node,P) :-
   search(Start_node,end,succs,'breadth-first',P),
   out(P).

search_d(Start_node,P) :-
   search(Start_node,end,succs,'depth-first',P),
   out(P).

search_h(Start_node,P) :-
   search(Start_node,end,succs,'hill-climbing',P),
   out(P).

search_u(Start_node,P) :-
   search(Start_node,end,succs,'uniform-cost',P),
   out(P).

% -----------------------------------------------------------------------------
% definition of search (general search predicate)
% -----------------------------------------------------------------------------
search(Start,EndPr,Expand,Str,Path) :-
    start(Start,Start_P),                               %build starting path (root)
    search2([Start_P],EndPr,Expand,[Start],Str,Path).   %search!


search2([[C,N|P_R]|_R],EndPr,_Expand,_C_L,_Str,[C,N|P_R]) :-
    E =.. [EndPr,N],                                    %look if end node is reached
    E.

search2([[C,N|P_R]|A_R],EndPr,Expand,C_L,Str,Path) :-
    E =.. [Expand,N,Succ_L],                            %build predicate for finding successors
    E, !,                                               %find successors (and save them in Succ_L)
    expand([C,N|P_R],Succ_L,C_L,Str,C_L_new,New_P_L),   %build new paths
    add_to_agenda(New_P_L,A_R,Str,A),                   %update agenda
    %out2(A), nl,write('---------------------------------------------'),nl,
    search2(A,EndPr,Expand,C_L_new,Str,Path).           %continue search!

%if no end node and no successor, just remove path from Agenda (open list)
search2([_P|A_R],EndPr,Expand,C_L,Str,Path) :-
    search2(A_R,EndPr,Expand,C_L,Str,Path).


%------------------------------------------------------------------------------
% expand existing paths by adding successors and calculating new costs
% the first element of the cost-list is chosen according to search strategy 
% this is preparatory work for later sorting
%------------------------------------------------------------------------------
expand(_P,[],C_L_new,_Str,C_L_new,[]).

% A* sorts according to overall costs
expand([[Fc_P,Gc_P]|P_R],[[Hc_New_P,Gc_N,N]|R],C_L,'A*',C_L_new,[[[Fc_New_P,Gc_New_P],N|P_R]|R1]) :-
    not(member(N,C_L)), !,                              %check if Successor is already in Closed List
    append(C_L,[N],C_L_new1),                           %append Node to Closed list
    Gc_New_P is Gc_P + Gc_N,                            %calculate real costs for new path
    Fc_New_P is Hc_New_P + Gc_New_P,                    %overall costs = heuristic costs + real costs
    expand([[Fc_P,Gc_P]|P_R],R,C_L_new1,'A*',C_L_new,R1).%continue with next successor

% uniform-cost sorts according to real costs
expand([[_Gc_P,Gc_P]|P_R],[[_Hc_New_P,Gc_N,N]|R],C_L_new,'uniform-cost',C_L,[[[Gc_New_P,Gc_New_P],N|P_R]|R1]) :-
    not(member(N,P_R)), !,                              %check if Successor is already in Path
    Gc_New_P is Gc_P + Gc_N,                            %calculate real costs for new path
    expand([[Gc_P,Gc_P]|P_R],R,C_L,'uniform-cost',C_L_new,R1).%continue with next successor
    
% hill-climbing sorts according to heuristic costs
expand([[Hc_P,Gc_P]|P_R],[[Hc_New_P,Gc_N,N]|R],C_L,'hill-climbing',C_L_new,[[[Hc_New_P,Gc_New_P],N|P_R]|R1]) :-
    not(member(N,P_R)), !,                              %check if Successor is already in Path
    Gc_New_P is Gc_P + Gc_N,                            %calculate real costs for new path
    expand([[Hc_P,Gc_P]|P_R],R,C_L,'hill-climbing',C_L_new,R1).%continue with next successor

% it is absolutely not necessary to calculate any costs for breadth- and
% depth-first search, so this is just for additional information
expand([[Fc_P,Gc_P]|P_R],[[_Hc_New_P,Gc_N,N]|R],C_L,'depth-first',C_L_new,[[[Fc_P,Gc_New_P],N|P_R]|R1]) :-
    not(member(N,P_R)), !,                              %check if Successor is already in Path
    Gc_New_P is Gc_P + Gc_N,                            %calculate real costs for new path
    expand([[Fc_P,Gc_P]|P_R],R,C_L,'depth-first',C_L_new,R1).%continue with next successor

expand([[Fc_P,Gc_P]|P_R],[[_Hc_New_P,Gc_N,N]|R],C_L,'breadth-first',C_L_new,[[[Fc_P,Gc_New_P],N|P_R]|R1]) :-
    not(member(N,P_R)), !,                              %check if Successor is already in Path
    Gc_New_P is Gc_P + Gc_N,                            %calculate real costs for new path
    expand([[Fc_P,Gc_P]|P_R],R,C_L,'breadth-first',C_L_new,R1).%continue with next successor

% if Node of Successor is already member of Path, neglect this Successor
expand(P,[_Succ|R],C_L,Str,C_L_new,R1) :-
    expand(P,R,C_L,Str,C_L_new,R1).                     %and continue with next successor


%------------------------------------------------------------------------------
% add new paths to agenda (according to search strategy)
%------------------------------------------------------------------------------
% sort whole agenda
add_to_agenda(New_P_L,A_R,'A*',A) :-
    sort(New_P_L,Sorted_P_L),
    merge(A_R,Sorted_P_L,A).

% sort whole agenda
add_to_agenda(New_P_L,A_R,'uniform-cost',A) :-
    sort(New_P_L,Sorted_P_L),
    merge(A_R,Sorted_P_L,A).
    
% just sort new paths and append to the front of the agenda
add_to_agenda(New_P_L,A_R,'hill-climbing',A) :-
    sort(New_P_L,Sorted_P_L),
    append(Sorted_P_L,A_R,A).
    
% sort nothing and append new paths to the front of the agenda
add_to_agenda(New_P_L,A_R,'depth-first',A) :-
    append(New_P_L,A_R,A).

% sort nothing and append new paths to the end of the agenda
add_to_agenda(New_P_L,A_R,'breadth-first',A) :-
    append(A_R,New_P_L,A).


% -----------------------------------------------------------------------------
% clear and structured output of the path
% -----------------------------------------------------------------------------
out([[_,Gc]|R]) :-
    out1(R),
    write('Costs: '),write(Gc),nl.
out1([]).
out1([X|R]) :-
    out1(R),
    write(X),nl.


out2([]).
out2([[X,Y,Z|_]|R]) :-
    write(X),write('-'),write(Y),write('-'),write(Z),write(', '),
    out2(R).