na_casu(milos).
na_casu(milan).
na_casu(jasna).

voli(milos, cokolada).
voli(branka, sladoled).
voli(milan, pivo).
voli(milos, X):-voli(branka, X).

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

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

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

%rad sa listama
%[1,2,3,4,5] - ovo je lista u prologu 
%[1,2,[2,3],5,6] - ovo je takodje lista
%[H|T] - H je element liste, T je rep (takodje lista)
%[]

%poslednji element liste
poslednji([X], X).
poslednji([H|T],X):-poslednji(T, X).

%pronaci n-ti element liste npr. nti([3,4,5], 2, 4).
nti([H|T], 1, H).
nti([H|T], N, X):-N1 is N-1, nti(T, N1, X).

%odrediti duzinu liste npr. duzina([5,6,3,1],4).
duzina([],0).
duzina([H|T],N):-duzina(T,N1), N is N1+1.

%spajanje dve liste npr. spoj([4,53,3],[5,6],[4,53,3,5,6]).
spajanje([],L,L).
spajanje([H1|T1],L2,[H1|T3]):- spajanje(T1,L2,T3).

%obrtanje liste npr. obrni([4,5,6,3],[3,6,5,4]).
%Prvi nacin
obrni([],[]).
obrni([H|T], R):-obrni(T,M), spajanje(M,[H],R).

%drugi nacin
obrni(X,Y):-obrni(X,[],Y).
obrni([],A,A).
obrni([H|T],A,Y):-obrni(T,[H|A],Y).

%palindrom
palindrom(L):-obrni(L,L).


poravnaj([],[]).
poravnaj([H|T],R):-is_list(H),poravnaj(T,R1),spajanje(H,R1,R),!.
poravnaj([H|T],[H|T1]):-poravnaj(T,T1).

duplikati([],[]).
duplikati([X|R],L) :- nti(R,1,X), duplikati(R,L).
duplikati([X|R],[X|R1]) :- not(nti(R,1,X)), duplikati(R,R1).


duplikati2([],[]).
duplikati2([H],[H]).
duplikati2([H1,H2|T],R):-H1==H2, duplikati2([H2|T],R).
duplikati2([H1,H2|T],[H1|R]):-H1\==H2, duplikati2([H2|T],R).

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

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

sortirana([X]).
sortirana([H,H1|R]):- H=<H1, sortirana([H1|R]). 

naivsort(L, P):-perm(L,P),sortirana(P).

ubacisort(X,[],[X]).
ubacisort(X,[Y|R],[X,Y|R]) :- X<Y,!.
ubacisort(X,[Y|R],[Y|R1]) :- ubacisort(X,R,R1).

insertion([],[]).
insertion([X|R],L) :- insertion(R,R1), ubacisort(X,R1,L).