/********************************** Listen ***********************************/
/* append, reverse und member sind bereits in PROLOG vordefiniert            */

my_append([], YS, YS).
my_append([X | XS], YS, [X | ZS]) :- my_append(XS, YS, ZS).

my_reverse([], []).
my_reverse([X | XS], ZS) :- reverse(XS, YS), my_append(YS, [X], ZS).

my_member(X, [X | XS]).
my_member(X, [Y | XS]) :- my_member(X, XS).


/******************************* Erfuellbarkeit ******************************/

boolean(var(true)).
boolean(var(false)).
boolean(and(F,G)) :- boolean(F), boolean(G).
boolean(or(F,G)) :- boolean(F), boolean(G).
boolean(not(F)) :- boolean(F).

sat(var(true)).
sat(and(F,G)) :- sat(F), sat(G).
sat(or(F,G)) :- sat(F), boolean(G).
sat(or(F,G)) :- sat(G), boolean(F).
sat(not(F)) :- unsat(F).

unsat(var(false)).
unsat(or(F,G)) :- unsat(F), unsat(G).
unsat(and(F,G)) :- unsat(F), boolean(G).
unsat(and(F,G)) :- unsat(G), boolean(F).
unsat(not(F)) :- sat(F).


/********************************** Zahlen ***********************************/

le(X, X).
le(X, suc(Y)) :- le(X, Y).

gt(suc(X), X).
gt(suc(X), Y) :- gt(X, Y).

add(zero, Y, Y).
add(suc(X), Y, suc(Z)) :- add(X, Y, Z).

sub(Y, zero, Y).
sub(zero, suc(X), zero).
sub(suc(X), suc(Y), Z) :- sub(X, Y, Z).

mul(zero, Y, zero).
mul(suc(X), Y, Z) :- mul(X, Y, W), add(W, Y, Z).

div(X, Y, zero) :- gt(Y, X).
div(X, Y, suc(Z)) :- le(Y, X), sub(X, Y, W), div(W, Y, Z).


/****************************** Permutation Sort *****************************/

insert(X, [], [X]).
insert(X, [Y | YS], [X, Y | YS]).
insert(X, [Y | YS], [Y | ZS]) :- insert(X, YS, ZS).

permute([], []).
permute([X | XS], ZS) :- permute(XS, YS), insert(X, YS, ZS).

sorted([]).
sorted([X]).
sorted([X, Y | XS]) :- le(X, Y), sorted([Y | XS]).

psort(XS, YS) :- permute(XS, YS), sorted(YS).


/********************************** Quicksort ********************************/

part(A, [], [], []).
part(A, [B | BS], [B | CS], DS) :- le(B, A), part(A, BS, CS, DS).
part(A, [B | BS], CS, [B | DS]) :- not(le(B, A)), part(A, BS, CS, DS).

qsort([], []).
qsort([A | AS], FS) :-
  part(A, AS, BS, CS),
  qsort(BS, DS),
  qsort(CS, ES),
  append(DS, [A | ES], FS).


/********************************* Labyrinth *********************************/

door(a,b).
door(b,c).
door(b,f).
door(c,g).
door(d,e).
door(d,h).
door(g,k).
door(h,i).
door(h,l).
door(i,m).
door(j,k).
door(j,n).
door(l,p).
door(m,q).
door(n,o).
door(o,p).
door(q,r).

maze2(X, X, VS, [X]).
maze2(X, Y, VS, [X | YS]) :-
  (door(X, Z); door(Z, X)), not(member(Z, VS)), maze2(Z, Y, [X | VS], YS).

maze(X, Y, XS) :- maze2(X, Y, [], XS).
