osoba(marko).
osoba(ana).

ima_vozacku(ana).

auto(fiat).
auto(honda).

vozi(X,Y):-osoba(X),ima_vozacku(X),auto(Y).
vozi(marko,fiat).

%bojenje grafa
bojenje(Srb,Mak,Cg,Alb,Bug,Rum,Madj):-sused(Srb,Mak),
sused(Srb,Cg),
sused(Srb,Bug),
sused(Srb,Rum),
sused(Srb,Madj),
sused(Mak,Alb),
sused(Bug,Rum),
sused(Rum,Madj),
sused(Bug,Mak),
sused(Cg,Alb).

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

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

% lista se predstavlja kao skup el. u okviru uglastih zagrada
% rek. definicija
% 1. prazna lista [] je lista
% 2. [H|T], H je glava liste, a T je rep liste koji je isto lista

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

% moguca je i ova reprezentacija liste:
% [H1,H2,...,HN|T]
% [H1,H2,...,HN]

%:-ntielement([1,2,3,4,5],3,X).
%X=3;

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

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

obrni([],[]).
obrni([H|T],R):-obrni(T,T1),append(T1,[H],R).

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

palindrom(L):-reverse(L,RL),L==RL.

ravnaj([],[]).
ravnaj([H|T],R):-is_list(H),ravnaj(H,HR),ravnaj(T,TR),append(HR,TR,R).
ravnaj([H|T],R):-not(is_list(H)),ravnaj(T,TR),append([H],TR,R).

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

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

komb(L,0,[]).
komb([H|T],K,[H|R1]):-K>0,K1 is K-1,komb(T,K1,R1).
komb([H|T],K,R):-K>0,komb(T,K,R).

nsort(L,S):-perm(L,S),sortirana(S).

sortirana([]).
sortirana([H]).
sortirana([H1,H2|T]):-H1=<H2,sortirana([H2|T]).

isort([],[]).
isort([H|T],R):-isort(T,TS),ubacisortirano(H,TS,R).

ubacisortirano(X,[],[X]).
ubacisortirano(X,[H|T],[X,H|T]):-X<H.
ubacisortirano(X,[H|T],[H|R]):-X>=H,ubacisortirano(X,T,R).

usort([],[]):-!.
usort([X],[X]):-!.
usort(L,LS):-razbi2(L,L1,L2),usort(L1,L1S),usort(L2,L2S), 
	ucesljaj(L1S,L2S,LS).

razbi2([],[],[]).
razbi2([H],[H],[]).
razbi2([H1,H2|T],[H1|T1],[H2|T2]):-razbi2(T,T1,T2).

ucesljaj([],[],[]).
ucesljaj([],L,L).
ucesljaj(L,[],L).
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).

%drugi deo casa

prost(1).
prost(X):-X2 is X//2,prostp(X,X2).

prostp(X,1):-!.
prostp(X,B):-Mod is X mod B, Mod=:=0,fail.
prostp(X,B):-Mod is X mod B, Mod=\=0, B1 is B-1, prostp(X,B1).

uzajamnoprosti(X,Y):-nzd(X,Y,D),D=:=1.

nzd(X,X,X).
nzd(X,Y,D):-X>Y,X1 is X-Y, nzd(X1,Y,D).
nzd(X,Y,D):-X<Y,Y1 is Y-X,nzd(X,Y1,D).

faktori(1,[]):-!.
faktori(X,[D|F1]):-delilac(X,D),X1 is X//D, faktori(X1,F1).

delilac(1,1):-!.
delilac(X,D):-delilacp(X,2,D).

delilacp(X,X,X):-!.
delilacp(X,B,B):-Rem is X mod B, Rem=:=0.
delilacp(X,B,D):-Rem is X mod B, Rem=\=0, B1 is B+1, 
	delilacp(X,B1,D).
	
svi_prosti(0,[]):-!.
svi_prosti(N,[N|T]):-prost(N),N1 is N-1,svi_prosti(N1,T).
svi_prosti(N,T):-not(prost(N)),N1 is N-1,svi_prosti(N1,T).

vrednostpol([],_,0).
vrednostpol([[K,S]|T],X,V):-pow(X,S,U),vrednostpol(T,X,TV),
	V is TV+K*U.

% primeri korektnih zapisa drveta u nasoj notaciji:
% nil 
% d(5,nil,nil)
% d(6,d(3,nil,nil),nil)

%primeri nekorektnih zapisa ...:
% null
% d(nil,nil,nil)
% d(5,5,nil), ovo nije drvo jer ne prati rek. definiciju drveta a to je:
% 5 ceo broj - ovo je korektno
% L = 5 - L mora da bude drvo, sto nije tacno!
% D = nil - ovo je u redu

je_drvo(nil).
je_drvo(d(X,L,D)):-integer(X),je_drvo(L),je_drvo(D).

lista_u_drvo([],nil).
lista_u_drvo([H|T],R):-lista_u_drvo(T,R1),ubacig(H,R1,R).

ubacig(X,nil,d(X,nil,nil)).
ubacig(X,d(Y,L,D),d(Y,L,D1)):-X>Y,ubacig(X,D,D1).
ubacig(X,d(Y,L,D),d(Y,L1,D)):-ubacig(X,L,L1).

ispisid(nil,_).
ispisid(d(X,L,D),K):-K1 is K+1,ispisid(D,K1),blanko(K),
		write(X),nl,ispisid(L,K1).

blanko(0):-!.
blanko(K):-write('   '),K1 is K-1, blanko(K1).

kcvorovi(nil,_,[]).
kcvorovi(d(X,_,_),1,[X]):-!.
kcvorovi(d(X,L,D),K,R):-K1 is K-1,kcvorovi(L,K1,L1),
	kcvorovi(D,K1,D1),append(L1,D1,R).

%primer poziva	
%lista_u_drvo([5,6,2,3,8,6],X),ispisid(X,0), kcvorovi(X,3,K).

%ocekivani rezultat za
%lista_u_drvo([5,6,2,3,8,6],X),ispisid(X,0), bfs(X,L).
% L = [6,3,8,2,6,5]

%bfs(D,L):-bfsp(D,L,1).
%bfsp(D,R,K):-dubina(D,Dub),K=<Dub,
%	kcvorovi(D,K,KL),K1 is K+1,bfsp(D,L1,K1), append(KL,K1,R).
%bfsp(D,[],K):-dubina(D,Dub),K>Dub.

dubina(nil,0).
dubina(d(X,L,D),Kd):-dubina(L,Dl),dubina(D,Dd),maks(Dl,Dd,M),Kd is M+1.

maks(X,Y,X):-X>Y.
maks(X,Y,Y).