rotate_left([],[]).
rotate_left([X],[X]).
rotate_left([X|Y],L) :- append(Y,[X],L).

sum_last_three([],0) :- !.
sum_last_three([X],X) :- !.
sum_last_three([X,Y],N) :- N is X + Y, !.
sum_last_three([X,Y,Z],N) :- N is X + Y + Z, !.
sum_last_three([_|L],N) :- sum_last_three(L,N), !.

flatten1([],[]).
flatten1([X|L],[X|F]) :- atomic(X), flatten1(L,F).
flatten1([X|L],F) :- not atomic(X), flatten1(X,F1), flatten1(L,F2), 
                    append(F1,F2,F).

double([],[]).
double([X|L],[X,X|D]) :- double(L,D).

count_atoms([],0).
count_atoms([X|L],N) :- atomic(X), count_atoms(L,M), N is M + 1.
count_atoms([X|L],N) :- not atomic(X), count_atoms(X,M1), count_atoms(L,M2), 
                    N is M1 + M2.

nth_member(1,[X|_],X).
nth_member(N,[_|L],Y) :- M is N - 1, nth_member(M,L,Y).

frequencies(L,X) :- mergesort(L,S), freq(S,0,[],X).

freq([],_,X,X).
freq([X],N,T,F) :- M is N + 1, append(T,[[X,M]],T2), freq([],0,T2,F), !.
freq([X,X|L],N,T,F) :- M is N + 1, freq([X|L],M,T,F), !.
freq([X,Y|L],N,T,F) :- M is N + 1, append(T,[[X,M]],T2),
                       freq([Y|L],0,T2,F), !.

mergesort([],[]) :- !.
mergesort([X],[X]) :- !.
mergesort(X,Z) :- msplit(X,L1,L2),
                  mergesort(L1,M1),
                  mergesort(L2,M2),
                  merge(M1,M2,Z).

msplit([],[],[]) :- !.
msplit([X],[X],[]) :- !.
msplit([X,Y|Z],[X|L1],[Y|L2]) :- msplit(Z,L1,L2).

merge([],X,X) :- !.
merge(X,[],X) :- !.
merge([X|L],[Y|M],[X|N]) :- X @=< Y, !, merge(L,[Y|M],N).
merge([X|L],[Y|M],[Y|N]) :- Y @=< X, merge([X|L],M,N).

hanoi(N) :- nl, nl, move(N,left,centre,right).
move(0,_,_,_) :- !.
move(N,A,B,C)
  :- M is N - 1,
     move(M,A,C,B),
     inform(A,B),
     move(M,C,B,A).
inform(X,Y) :- write('move disc from '),write(X),write(' pole to the '),
               write(Y),write(' pole.'),nl.




%
% A program to solve the Zebra Puzzle.
%

zebra(Zebraowner,Drinkswater) :- 
	houses(s(s(s(s(s(zero))))), List),
	member(house(  red,  englishman,    _,      _,       _) ,List),
	member(house(    _,    spaniard,  dog,      _,       _) ,List),
	member(house(green,           _,    _, coffee,       _) ,List),
	member(house(    _,   ukrainian,    _,    tea,       _) ,List),
      sublist([house(ivory,           _,    _,      _,       _) ,
	       house(green,           _,    _,      _,       _)],List),
	member(house(    _,           _,snail,      _,old_gold),List),
	member(house(yellow,          _,    _,      _,   kools),List),
	eq([_,_,house(    _,           _,    _,   milk,      _),_,_], List),
	     eq([house(    _,   norwegian,    _,      _,       _)|_], List),
	nextto(house(    _,           _,    _,      _,chesterfield),
	       house(    _,           _,  fox,      _,           _),List),
	nextto(house(    _,           _,    _,      _,     kools),
	       house(    _,           _,horse,      _,         _),List),
	member(house(    _,           _,    _, orange,lucky_strike),List),
	member(house(    _,    japanese,    _,      _,parliaments),List),
	nextto(house(    _,   norwegian,    _,      _,          _),
	       house( blue,           _,    _,      _,          _),List),
	member(house(    _, Drinkswater,    _,  water,          _),List),
	member(house(    _,  Zebraowner,zebra,      _,          _),List).

eq(X, X).

houses(zero, []).
houses(s(N), [house(_,_,_,_,_)|List]) :- houses(N, List).

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

sublist(S, L) :- append(S, _, L).
sublist(S, [_|T]) :- sublist(S, T).

append([], L, L).
append([X|R], Y, [X|T]) :- append(R, Y, T).

nextto(H1, H2, L) :- sublist([H1, H2], L).
nextto(H1, H2, L) :- sublist([H2, H1], L).

go :-
	zebra(Zebraowner, Drinkwater),
	write('Zebra Owner is '), write(Zebraowner), nl,
	write('Drinks Water is '), write(Drinkwater), nl.

% Answer:
%  Zebraowner = japanese, Drinkwater = norwegian

% ?- printf("\n>>> Sample goal: go/0\n", []).


%