/* Faerben von Landkarten */

/* Hauptpraedikat: faerbe(Landkarte,Farben,Farbzuordnung) */
/* Format fuer Landkarte: Liste von Regionen der Form */
/*                        region(Name,Farbe,ListeVonNachbarn) */
/* Als Nachbarbezeichnung dienen nicht die Namen sondern die Farbvariablen. */


faerbe([Region|Restkarte],Farben,[Paar|L]) 
          :- faerbe_region(Region,Farben,Paar), faerbe(Restkarte,Farben,L). 
faerbe([], _Farben,[]).

/* Faerbung einer Region plus Faerbung von Nachbarn mit Restfarben */

faerbe_region(region(Name,Farbe,Nachbarn), Farben,(Name,Farbe))
       :-  select(Farbe,Farben,Restfarben), sublist(Nachbarn,Restfarben).


/* Hilfspraedikate */

select(X,[X|Ys],Ys). 
select(X,[Y|Ys],[Y|Zs]) :-  select(X,Ys,Zs). 

sublist([X|Xs],Ys)  :-  member(X,Ys), sublist(Xs,Ys). 
sublist([],_Ys). 

%member(X,[X|_Xs]).
%member(X,[_Y|Ys]) :- member(X,Ys).

/* Testaufrufe fuer 3 und 4 Farben und die Laenderkarte von Deutschland*/

test3(L) :- 
    faerbe([region(schleswig-holstein,   SH,  [HH,N,MP]), 
            region(hamburg,              HH,  [SH,N]), 
            region(niedersachsen,        N,   [SH,HH,SA,TH,H,NRW,HB]), 
            region(bremen,               HB,  [N]), 
            region(nordrhein-westfalen,  NRW, [N,H,RP]),
            region(hessen,               H,   [NRW,RP,BW,BY,TH]),
            region(rheinland-pfalz,      RP,  [NRW,H,BW,SL]),
            region(saarland,             SL,  [RP]), 
            region(baden-wuerttemberg,   BW,  [RP,H,BY]), 
            region(bayern,               BY,  [H,BW,TH,S]), 
            region(thueringen,           TH,  [H,BY,N,S,SA]), 
            region(sachsen,              S,   [BY,TH,SA,BB]),  
            region(sachsen-anhalt,       SA,  [TH,N,MP,BB,S]), 
            region(brandenburg,          BB,   [B,MP,S,SA]), 
            region(berlin,               B,    [BB]), 
            region(mecklenburg-vorpommern,  MP,  [SH,N,SA,BB])
           ],
           [gruen,weiss,gelb],L).

test4(L) :- 
    faerbe([region(schleswig-holstein,   SH,  [HH,N,MP]), 
            region(hamburg,              HH,  [SH,N]), 
            region(niedersachsen,        N,   [SH,HH,SA,TH,H,NRW,HB]), 
            region(bremen,               HB,  [N]), 
            region(nordrhein-westfalen,  NRW, [N,H,RP]),
            region(hessen,               H,   [NRW,RP,BW,BY,TH]),
            region(rheinland-pfalz,      RP,  [NRW,H,BW,SL]),
            region(saarland,             SL,  [RP]), 
            region(baden-wuerttemberg,   BW,  [RP,H,BY]), 
            region(bayern,               BY,  [H,BW,TH,S]), 
            region(thueringen,           TH,  [H,BY,N,S,SA]), 
            region(sachsen,              S,   [BY,TH,SA,BB]),  
            region(sachsen-anhalt,       SA,  [TH,N,MP,BB,S]), 
            region(brandenburg,          BB,   [B,MP,S,SA]), 
            region(berlin,               B,    [BB]), 
            region(mecklenburg-vorpommern,  MP,  [SH,N,SA,BB])
           ],
           [gruen,weiss,gelb,rot],L).








% Dijkstras Dutch Flag Problem
% ============================
% Eine Liste mit rot, weiss oder blau gefaerbten Objekten 
% soll so umsortiert werden, dass zunaechst alle roten,
% dann alle weissen und schliesslich alle blauen Objekte
% auftreten. Dabei soll die relative Ordnung der gleichfarbigen
% Objekte untereinander erhalten bleiben.
%


dutch(Xs,RWB) :- distribute(Xs,R,W,B),
                 append(W,B,WB), 
                 append(R,WB,RWB).

distribute([red(X)|Xs],[red(X)|Rs],Ws,Bs)     :- distribute(Xs,Rs,Ws,Bs).
distribute([white(X)|Xs],Rs,[white(X)|Ws],Bs) :- distribute(Xs,Rs,Ws,Bs).
distribute([blue(X)|Xs],Rs,Ws,[blue(X)|Bs])   :- distribute(Xs,Rs,Ws,Bs).
distribute([],[],[],[]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Version mit Differenzlisten  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

dutchDL(Xs,RWB) :- distribute_dls(Xs,RWB,WB,WB,B,B,[]).

distribute_dls([red(X)|Xs],[red(X)|Rs],Rs1,Ws,Ws1,Bs,Bs1)  
                :- distribute_dls(Xs,Rs,Rs1,Ws,Ws1,Bs,Bs1).
distribute_dls([white(X)|Xs],Rs,Rs1,[white(X)|Ws],Ws1,Bs,Bs1) 
                :- distribute_dls(Xs,Rs,Rs1,Ws,Ws1,Bs,Bs1). 
distribute_dls([blue(X)|Xs],Rs,Rs1,Ws,Ws1,[blue(X)|Bs],Bs1) 
                :- distribute_dls(Xs,Rs,Rs1,Ws,Ws1,Bs,Bs1). 
distribute_dls([],Rs,Rs,Ws,Ws,Bs,Bs).