PROGRAMMIERAUFGABE 9.1

reach(N1,N2,Path) :-
  reach1(N1,[N1],N2,RevPath),
  reverse(RevPath,Path).

reach1(N1,Visited,N1,Visited).
reach1(N1,Visited,N2,RevPath) :- 
  e(N1,N0),
  notin(N0,Visited),
  reach1(N0,[N0|Visited],N2,RevPath).

notin(_,[]).
notin(X,[X|_]) :- 
  !,
  fail.
notin(X,[_|L]) :-
  notin(X,L).

reverse(X,XR) :-
  reverse1(X,[],XR).

reverse1([],Accum,Accum).
reverse1([X|XL],Accum,Result) :-
  reverse1(XL,[X|Accum],Result).


PROGRAMMIERAUFGABE 9.2

matches([],[]).
matches([*|XL],YL) :- 
  matches(XL,YL).
matches([*|XL],[_|YL]) :-
  !,
  matches([*|XL],YL).
matches([?|XL],[_|YL]) :-
  !,
  matches(XL,YL).
matches(['['|XL],[Y|YL]) :-
  !,
  getRange(XL,R,XRest),
  member(Y,R), 
  matches(XRest,YL).
matches([X|XL],[X|YL]) :-
  matches(XL,YL).

getRange([],[],[]).
getRange([']'|XL],[],XL) :-
  !.
getRange([X|XL],[X|YL],ZL) :-
  getRange(XL,YL,ZL).

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


AUFGABE 9.3

a1([],0).
a1([_|_],1).

a2([],0) :- !.
a2([_|_],1).

a3([],0).
a3(L,1) :- not(L = []).

a4([],0) :- !.
a4(_,1).

a5([],Y) :- Y = 0, !.
a5(_,1).

a6([],Y) :- !, Y = 0.
a6(_,1).


% ?- a1(b,X).
% ?- a2(b,X).
% 
% => Fehlschlag
% 
% ?- a3(b,X).
% ?- a4(b,X).
% ?- a5(b,X).
% ?- a6(b,X).
% 
% => X = 1
% 
% 
% ?- a1(X,Y).
% 
% => zwei Lösungen:
%    X = []  Y = 0
%    X = [_G250|_G251]  Y = 1
% 
% ?- a2(X,Y).
% ?- a3(X,Y).
% ?- a4(X,Y).
% ?- a5(X,Y).
% ?- a6(X,Y).
% 
% => eine Lösung:
%    X = []  Y = 0
% 
% 
% ?- a1([],1).
% ?- a2([],1).
% ?- a3([],1).
% ?- a6([],1).
% 
% => Fehlschlag
% 
% ?- a4([],1).
% ?- a5([],1).
% 
% => Erfolg
% 
% 
% a3 und a6 unterscheiden sich nicht,
% a4 und a5 unterscheiden sich nicht.


AUFGABE 9.4

r(a1,b11).
r(a1,b12).
r(a2,b21).

s(b12,c12).
s(b21,c21).

t(a3,c3).

p1(X,1,Y) :- !, r(X,Z), s(Z,Y).
p1(X,_,Y) :- t(X,Y).

p2(X,1,Y) :- r(X,Z), !, s(Z,Y).
p2(X,_,Y) :- t(X,Y).

p3(X,1,Y) :- r(X,Z), s(Z,Y), !.
p3(X,_,Y) :- t(X,Y).

p4(X,1,Y) :- !, r(X,Z), s(Z,Y), !.
p4(X,_,Y) :- t(X,Y).

% ?- p1(X,W,Y).
% 
% X = a1
% W = 1
% Y = c12 ;
% 
% X = a2
% W = 1
% Y = c21 ;
% 
% No
% 
% ?- p2(X,W,Y).
% 
% No
% 
% ?- p3(X,W,Y).
% 
% X = a1
% W = 1
% Y = c12 ;
% 
% No
% 
% ?- p4(X,W,Y).
% 
% X = a1
% W = 1
% Y = c12 ;
% 
% No
% 
% ?- p3(a3,1,Y).
% 
% Y = c3 ;
% 
% No
% ?- p4(a3,1,Y).
%
% No