% Bauer, Wolf, Ziege und Kohlkopf wollen gemeinsam ueber einen Fluss
% es gibt nur ein Boot, in dem der Bauer hoechstens ein Ding transportieren kann
% Wolf frisst Ziege; Ziege frisst Kohl, wenn allein gelassen

% --------------------------------------------------------------------------------------

% kommt X mindestens einmal in Liste vor?
mitglied(X, [X|_]).
mitglied(X, [_|L]) :- mitglied(X, L).

% loesche X genau 1x aus Liste
loesche(X, [X|S], S).
loesche(X, [Y|S], [Y|S1]) :- loesche(X,S,S1).

% Liste + Liste = Liste
konk([],L,L).
konk([X|L1], L2, [X|L3] ) :- konk( L1, L2, L3 ).

% kommt jedes Element aus L1 in L2 vor, also "Subliste"
mitgliedL([X], L) :- mitglied(X, L).
mitgliedL([X | Rest], L) :- mitglied(X, L), mitgliedL(Rest, L).

% loesche jedes Element einer Liste aus anderer Liste (1x)
loescheL([X], L2, L) :- loesche(X, L2, L).
loescheL([X| Rest], L2, L) :- loesche(X, L2, ListeohneX), loescheL(Rest, ListeohneX, L).

% wahr, wenn zwei Listen mengengleich sind
elementgleich([], []).
elementgleich([X | L1], L2) :- mitglied(X, L2),
                               loesche(X, L2, L2neu),
                               elementgleich(L1, L2neu).

% --------------------------------------------------------------------------------------

% State repraesentiert durch Zustand der beiden Uferseiten
state(_,_).

% brauchen wg. Verhindern eines Zyklus' eine Liste der besuchten States

% kommt state(X,Y) in Liste von states vor?
state_bekannt(state(X1, _), [ state(X2, _) | _ ]):- elementgleich(X1, X2).  % redundant: , elementgleich(Y1,Y2).
state_bekannt(State, [ _ | L ]) :- state_bekannt(State, L).

% pack besuchte States vorn an Liste ran
addState(State, States, [State | States]).

% --------------------------------------------------------------------------------------

% hoechstens 2 passen ins Boot; der Bauer ist dabei...
boot([b]).
boot([b,k]).
boot([b,z]).
boot([b,w]).

% wann gilt eine Uferseite als sicher?
bewacht(Liste) :- mitglied(b, Liste).     % ist der Bauer dabei, frisst keiner keinen
bewacht([]).                              % niemand vorhanden -> niemand kann fressen
bewacht([_]).                             % i am so alone...
bewacht([w,k]).                           % der Wolf mag keinen Kohl fressen
bewacht([k,w]).                           % der kohl mag keinen Wolf fressen ;)

% verschiedene mögliche Züge
% von links nach rechts
paddeln(state(Linksalt, Rechtsalt), Boot, state(Linksneu, Rechtsneu), StateList, StateListNeu) :-
             boot(Boot),                               % waehle Besatzung
             mitgliedL(Boot, Linksalt),                % diese muss links da sein
             loescheL(Boot, Linksalt, Linksneu),       % danach nicht mehr
             bewacht(Linksneu),                        % war gueltig?
             konk(Boot, Rechtsalt, Rechtsneu),         % kommt rechts an

             not(state_bekannt(state(Linksneu,Rechtsneu), StateList)), % mach nur weiter, wenn state neu
             addState(state(Linksneu,Rechtsneu), StateList, StateListNeu).

%             write('Boot '), write(Boot), write('\tfährt von links nach rechts,\t'),
%             write(state(Linksneu,Rechtsneu)), nl.


% von rechts nach links
paddeln(state(Linksalt, Rechtsalt), Boot, state(Linksneu, Rechtsneu), StateList, StateListNeu) :-
             boot(Boot),                                 % waehle Besatzung
             mitgliedL(Boot, Rechtsalt),                 % diese muss rechts da sein
             loescheL(Boot, Rechtsalt, Rechtsneu),       % danach nicht mehr
             bewacht(Rechtsneu),                         % war gueltig?
             konk(Boot, Linksalt, Linksneu),             % kommt links an

             not(state_bekannt(state(Linksneu,Rechtsneu), StateList)),     % mach nur weiter, wenn state neu
             addState(state(Linksneu,Rechtsneu), StateList, StateListNeu). % aktualisiere StateList

%             write('Boot '), write(Boot), write('\tfährt von rechts nach links,\t'),
%             write(state(Linksneu,Rechtsneu)), nl.


% Ziel erreicht?
ueberquert(state([],R)) :- elementgleich([b,w,k,z], R).


% Ziel erreichbar?
fahren(state(Lalt, Ralt), _Statelist, []) :-
                   ueberquert(state(Lalt, Ralt)).
                   
fahren(state(Lalt, Ralt), Statelist, BootAusgabe) :-
                   paddeln(state(Lalt, Ralt),  Boot, state(Lneu, Rneu), Statelist, Statelistneu),
                   konk([Boot], BootAusgabeneu, BootAusgabe),
                   fahren(state(Lneu, Rneu), Statelistneu, BootAusgabeneu).


go(State, BootAusgabe) :- fahren(State , [State], BootAusgabe).

% Anfrage:
% ?- fahren(state([b,w,k,z],[]), [state([b,w,k,z],[])], Bootliste).
% ?- go(state([b,w,k,z],[]), Bootliste).