/* ***************************************************************** */
/* CSE 428 - Assignment 6 - Solution                                 */
/* File S6.pl                                                      */
/* ***************************************************************** */


/* ***************************************************************** */
/* Exercise 1                                                        */
/* ***************************************************************** */
/* definition of sub_ord                                             */

sub_ord(K,L) :- /* first case: L is the same as K */
    L = K, ordered(L), !. /* the cut here is only for optimization:
 Clearly, if K is ordereded then there are no other maximal sublists */

sub_ord(K,L) :- /* second case: L is a prefix of K */
    L = [_,_|_], append(L,[X|_],K), ordered(L), last(L,Y), Y > X.

sub_ord(K,L) :- /* third case: L is internal to K */
    L = [X,_|_], append(M,[Y|_],K), append(_,[Z|L],M), Z > X, 
    last(L,W), W > Y, ordered(L).

sub_ord(K,L) :- /* fourth case: L is a postfix of K */
    L = [X,_|_], append(_,[Y|L],K), ordered(L), Y > X.

/* ***************************************************************** */
/* definition of ordered(L)  (true iff the list L is ordered)        */

ordered([]).
ordered([_]).
ordered([X,Y|L]) :- X =< Y , ordered([Y|L]).

/* ***************************************************************** */
/* definition of last(L,X) (true iff X is the last element in L)     */

last([X],X).
last([_|L],X) :- last(L,X).

/* ***************************************************************** */
/* Note: the above solution is "declarative" but not very efficient, 
because the sublist candidate is first generated and then tested.
A more efficient solution for this problem, although less declarative,
would be the following: 

sub_ord([X,Y|L],K) :- X > Y, sub_ord([Y|L],K).
sub_ord([X,Y|L],K) :- X =< Y, sub_ord_aux([X,Y|L],M,R), (K=M ; sub_ord(R,K)).

sub_ord_aux([],[],[]).
sub_ord_aux([X|[]],[X],[]).
sub_ord_aux([X,Y|K],[X],[Y|K]) :- X > Y.
sub_ord_aux([X,Y|K],[X|T],Q) :- X=<Y, sub_ord_aux([Y|K],T,Q).

This solution is linear on the lenght of the input list K.

*/
/* ***************************************************************** */

/* ***************************************************************** */
/* Exercise 2                                                        */
/* ***************************************************************** */

branch(leaf(X),[X]).

branch(node(T,X,_),[X|L]) :- branch(T,L).

branch(node(_,X,T),[X|L]) :- branch(T,L).



/* ***************************************************************** */
/* Exercise 3                                                        */
/* ***************************************************************** */

can_exit(M,N) :- aux(M,N,[]).

/* ***************************************************************** */
/* Definition of the auxiliary predicate  aux(X,Y,L): check whether  */
/* there is an exit from (X,Y), avoiding the positions in the list L */
/* (which represent the positions already visited)                   */

aux(1,_,_).  /* border left */
aux(_,1,_).  /* border top  */
aux(9,_,_).  /* border right */
aux(_,9,_).  /* border bottom */

aux(M,N,L) :- move(M,N,M1,N1), not(member((M1,N1),L)), aux(M1,N1,[(M1,N1)|L]).

/* ***************************************************************** */
/* Definition of the predicate  memb(X,L):  holds iff X occurs in L  */

memb(X,[X|_]).
memb(X,[_|L]) :- memb(X,L).

/* ***************************************************************** */
/* Definition of the predicate  move(X,Y,Z,W):  holds iff it is      */
/* possible to move in one step from position (X,Y) to position      */
/* (Z,W) in the maze                                                 */

move(M,N,M,N1) :- N1 is N - 1, m(M,N1). /* move north  */
move(M,N,M1,N) :- M1 is M + 1, m(M1,N). /* move east  */
move(M,N,M,N1) :- N1 is N + 1, m(M,N1). /* move south */
move(M,N,M1,N) :- M1 is M - 1, m(M1,N). /* move west  */

/* ***************************************************************** */
/* Note: this solution could be made more efficient by using the 
predicate assert to state which positions have already been visited in 
any of the branches of the computation. (Each branch represents an 
attempt to build a path which takes to the exit.)
*/
/* ***************************************************************** */


