osoba(marko).
osoba(katarina).

ima_vozacku(marko).

vozi(marko).
vozi(X):-osoba(X),ima_vozacku(X).


bojenje(Srb,Mak,Cg,RS,Hrv,Madj,Bug,Rum):-
	sused(Srb,Mak),
	sused(Srb,Cg),
	sused(Srb,Hrv),
	sused(Srb,Madj),
	sused(Srb,Bug),
	sused(Srb,Rum),
	sused(Srb,RS),
	sused(Mak,Bug),
	sused(Cg,Hrv),
	sused(Cg,RS),
	sused(RS,Hrv),
	sused(Hrv,Madj),
	sused(Madj,Rum),
	sused(Rum,Bug).

boja(zuta).
boja(crvena).
boja(plava).
boja(zelena).

sused(X,Y):-boja(X),boja(Y),X\==Y.

% lista je:
% 1) []
% 2) [H|T] -> H - prvi el. liste, a T je rep (koji je takodje lista)
% [1,2,3]->[1|[2,3]]->[2|[3]]->[3|[]]->[]
% 3) [H1,H2|T]->[1,2|[3]]->fail

poslednji([],_):-fail.
poslednji([X],X).
poslednji([H|T],R):-poslednji(T,R).

%nti(L,N,X).

nti([],_,_):-fail.
nti([H|T],1,H).
nti([H|T],N,X):-N>1,N1 is N-1, nti(T,N1,X).

%duzina(L,D).

duzina([],0).
duzina([H|T],N):-duzina(T,NT),N is NT+1.

%obrtanje([1,2,3,4],X).
%X=[4,3,2,1];

obrtanje([],[]).
obrtanje([H|T],R):-obrtanje(T,TO),append(TO,[H],R).

%palindrom([x,a,m,a,x]).
%true.

palindrom(X):-obrtanje(X,Y),X==Y.

%poravnaj([[1,2],4,b,[c,d,[a,3]],1],X).
% X = [1,2,4,b,c,d,a,3,1]

poravnaj([],[]).
poravnaj([H|T],R):-is_list(H),poravnaj(H,H1),poravnaj(T,T1),append(H1,T1,R).
poravnaj([H|T],R):-not(is_list(H)),poravnaj(T,T1),append([H],T1,R).

%eliminisi([a,a,a,b,c,c,d,b],X).
% X = [a,b,c,d,b]


eliminisi([],[]).
eliminisi([X],[X]).
eliminisi([H|T],[H|T1]):-eliminisi(T,[H1|T1]),H1==H.
eliminisi([H|T],[H,H1|T1]):-eliminisi(T,[H1|T1]),H1\==H.


perm([],[]).
perm([H|T],P):-perm(T,P1),ubaci(H,P1,P).

ubaci(X,[],[X]).
ubaci(X,[H|T],[X,H|T]).
ubaci(X,[H|T],[H|T1]):-ubaci(X,T,T1).

%varijanta sa cut operatorom
%ubaci(X,[],[X]):-!.
%ubaci(X,L,[X|L]).
%ubaci(X,[H|T],[H|T1]):-ubaci(X,T,T1).

komb([],K,_):-K>0,fail,!.
komb(L,0,[]):-!.
komb([H|T],K,[H|X1]):-K>0, K1 is K-1, komb(T,K1,X1).
komb([H|T],K,X):-komb(T,K,X).

% Prvi nacin, elegantniji
%var(L,K,V):-komb(L,K,C),perm(C,V).

var([],K,_):-K>0,fail,!.
var(L,0,[]):-!.
var([H|T],K,Y):-K>0, K1 is K-1, var(T,K1,X1),ubaci(H,X1,Y).
var([H|T],K,X):-var(T,K,X).

sortirana([]).
sortirana([X]).
sortirana([H,H1|T]):- H1 >= H, sortirana([H1|T]).

sortiraj(L, P):- perm(L, P), sortirana(P), !.

isort([],[]).
isort([H|T],X):-isort(T,T1),dodaj(T1,H,X).

dodaj([],X,[X]).
dodaj([H|T],X,[H|X1]):-X>H, dodaj(T,X,X1).
dodaj([H|T],X,[X,H|T]):-X=<H.

msort1([],[]).
msort1([X],[X]).
msort1(L,S):-podeli(L,Leva,Desna),msort1(Leva,SLeva),msort1(Desna,SDesna),
	ucesljaj(SLeva,SDesna,S),!.
	
podeli([],[],[]).
podeli([X],[X],[]).
podeli([H1,H2|T],[H1|T1],[H2|T2]):-podeli(T,T1,T2).

ucesljaj([],L2,L2):-!.
ucesljaj(L1,[],L1):-!.
ucesljaj([H1|T1],[H2|T2],[H1|R]):-H1<H2,ucesljaj(T1,[H2|T2],R).
ucesljaj([H1|T1],[H2|T2],[H2|R]):-H1>=H2,ucesljaj([H1|T1],T2,R).