%1) Esta en la wiki.

%2) I), II), III), IV) Esta en la wiki.

%2) V)

%primo(+X) determina si el numero X es primo o no.

mod(A,B,A) :- A < B.
mod(A,B,C) :- A >= B, D is A - B, mod(D,B,C).

divisible(A,B) :- mod(A,B,C), C=:=0.

divisible2(A,B) :- C is (A//B) * B, C =:= A.
%divisible2(A,B) :- (A//B) * B =:= A.

entre(A,B,A) :- A =< B.
entre(A,B,C) :- A < B, D is A+1, entre(D,B,C).

compuesto(0).
compuesto(1).
compuesto(N) :- N > 1, N1 is N-1, hayAlgunDivisor(2,N1,N).

hayAlgunDivisor(A,B,N) :- entre(A,B,C), divisible(N,C).

primo(A) :- not(compuesto(A)).

%V')

primo2(2).
primo2(N) :- N > 2, N1 is N-1, noHayDivisores(2,N1,N).

noHayDivisores(A,B,_) :- A > B.
noHayDivisores(A,B,N) :- A =< B, mod(N,A,D), D=\=0, C is A+1, noHayDivisores(C,B,N).

noHayDivisores2(A,B,N) :- not(hayAlgunDivisor(A,B,N)).

%4)

%apend(-X,-Y,-Z) concatena las listas X, Y y Z.

append([], X, X).
append( [H | T], Y, [H | Z]) :- append(T, Y, Z).

%I)

%last(+L,-U) devuelve el ultimo elemento U de la lista L.

last([U],U).
last([_|XS],U) :- last(XS,U).

last2(L,U) :- append(_,[U], L).

%I')

%init(+L,-I) devuelve el inicio I de la lista L.

init(L,I) :- last2(L,U), append(I,[U],L).

%head(+L,-H) devuelve el primer elemento H de la lista L.

head([X|_],X).
%head([X|_],H) :- X = H.

head2(L,H) :- append([H],_,L).

%tail(+L,-T) devuelve la cola T de la lista L.

tail([_|XS],XS).
%tail([_|XS],T) :- XS = T.

tail2(L,T) :- head2(L,H), append([H],T,L).

%II)

%reverse(+L,-L1) devuelve el reverso de la lista L.

reverse([], []).
reverse([X|XS],L1) :- reverse(XS,L2), append(L2,[X],L1).

%III)

%max(+L,-M) devuelve el maximo M de la lista L.

maxLista([M],M).
maxLista([X|XS],M) :- maxLista(XS,M1), max(X,M1,M).

max(A,B,A) :- A >= B.
max(A,B,B) :- A < B.

%min(+L,-M) devuelve el minimo M de la lista L.

minLista([M],M).
minLista([X|XS],M) :- minLista(XS,M1), min(X,M1,M).

min(A,B,A) :- A =< B.
min(A,B,B) :- A > B.

%IV)

%palindromo(+L,-L1) devuelve un palindromo construido a partir de la lista L.

palindromo(L,L1) :- reverse(L,L2), append(L, L2, L1).

%V)

%doble(+L,-L1) devuelve los elementos de la lista L repetidos dos veces.

doble([],[]).
doble([X|XS],D) :- doble(XS,D1), append([X,X],D1,D).

doble2([],[]).
doble2([E|L],[E,E|D]) :- doble(L,D).

%VI)

%prefijo(-P,+L) devuelve un prefijo P de la lista L.

prefijo(P,L) :- append(P,_,L).

%VII)

%sufijo(-S,+L) devuelve un sufijo S de la lista L.

sufijo(S,L) :- append(_,S,L).

%VIII)

%sublista(-S,+L) devuelve una sublista S de la lista L.

sublista([],_).
sublista(S,L) :- prefijo(P,L), sufijo(S,P), S \= [].

%IX)

%iesimo(-I,+L,-X) devuelve el I-esimo elemento X de la lista L.

iesimo(I,L,X) :- append(L1, [X | _], L), length(L1,I).

%5) I)

%mezcla(-X,-Y,-Z) intercala los elementos de las listas X e Y.

mezcla([],[],[]).
mezcla([],Y,Y) :- Y \= [].
mezcla(X,[],X) :- X \= [].
mezcla([X|XS],[Y|YS],[X,Y|Z]) :- mezcla(XS,YS,Z).

%II)

%split(-N,+L,-L1,-L2) pone los primeros N elementos de la lista L en L1 y los restantes en L2

split(N,L,L1,L2) :- append(L1,L2,L), length(L1,N).

%III)

%borrar(+L,+E,-L1) borra los elementos E en la lista L.

borrar([],_,[]).
borrar([E|XS], E, L) :- borrar(XS,E,L1), append([],L1,L).
borrar([X|XS], E, L) :- borrar(XS,E,L1), X \= E, append([X],L1,L).

borrar2([],_,[]).
borrar2([X|XS], E, L) :- borrar2(XS,E,L1), elemento(X,E,L2), append(L2,L1,L).

elemento(E,E,[]).
elemento(X,E,[X]) :- X \= E.

borrar3([],_,[]).
borrar3([E|XS],E,YS) :- borrar3(XS,E,YS).
borrar3([X|XS],E,[X|YS]) :- X \= E, borrar3(XS,E,YS).

%IV)

sacarDuplicados([],[]).
sacarDuplicados([X|XS],L) :- borrar(XS,X,L1), sacarDuplicados(L1,L2), append([X],L2,L).

%7)

%aplanar(+L,-L1) aplana la lista L.

aplanar([],[]).
aplanar([X|XS],L1) :- X = [_|_], aplanar(X,L2), aplanar(XS,L3), append(L2,L3,L1).
aplanar([X|XS],L1) :- X = [], aplanar(XS,L3), append([],L3,L1).
aplanar([X|XS],L1) :- X \= [_|_], aplanar(XS,L2), append([X],L2,L1).

aplanar2([],[]).
aplanar2([X|XS],L1) :- is_list(X), aplanar2(X,L2), aplanar2(XS,L3), append(L2,L3,L1).
aplanar2([X|XS],L1) :- not(is_list(X)), aplanar2(XS,L2), append([X],L2,L1).

%8) I)

%ordenada(+L) determina si la lista L esta ordenada ascendentemente o no.

ordenada([]).
ordenada([_]).
ordenada([X,Y|XS]) :- X =< Y, ordenada(XS). 

%II)

%quicksort(+L, -L1) ordena la lista L usando quicksort.

quicksort([],[]).
quicksort([X|XS],L) :- menores(X,XS,L1), mayores(X,XS,L2),
                       quicksort(L1,L3), quicksort(L2,L4), append(L3,[X|L4],L).
                       
menores(_,[],[]).
menores(X,[Y|YS],L1) :- menores(X,YS,L2), X < Y,append([],L2,L1).
menores(X,[Y|YS],L1) :- menores(X,YS,L2), X >= Y , append([Y],L2,L1).

mayores(_,[],[]).
mayores(X,[Y|YS],L1) :- mayores(X,YS,L2), X < Y,append([Y],L2,L1).
mayores(X,[Y|YS],L1) :- mayores(X,YS,L2), X >= Y, append([],L2,L1).

%III)

%inssort(+L, -L1) ordena la lista L usando insertion sort.

inssort([],[]).
inssort([X|XS],L1) :- inssort(XS,L2), insertar(X,L2,L1).

insertar(X,[],[X]).
insertar(X,[Y|YS],[X,Y|YS]) :- X =< Y.
insertar(X,[Y|YS],[Y|XS]) :- X > Y, insertar(X,YS,XS).

%9)

%rotar(+L, +N, -R) rota la lista N posiciones en el sentido del signo de N.

rotar([],N,[]) :- N \= 0.
rotar(L,0,L).
rotar(L,N,L1) :- N < 0, N1 is -N, rotacionIzquierda(L,N1,L1).
rotar(L,N,L1) :- N > 0, rotacionDerecha(L,N,L1).

rotacionIzquierda(L,0,L).
rotacionIzquierda([X|XS],N,L1) :- N > 0, N1 is N-1, append(XS,[X],L2), rotacionIzquierda(L2,N1,L1).

rotacionDerecha(L,0,L).
rotacionDerecha(L,N,L1) :- N > 0, N1 is N-1, last(L,U), init(L,I), append([U],I,L2), rotacionDerecha(L2,N1,L1).

%10)

%repeticiones(+L,-L1) devuelve una lista L1 repitiendo n veces cada n en la lista L.

repeticiones([],[]).
repeticiones([X|XS],L1) :- repeticiones(XS,L2), repetir(X,X,L3), append(L3,L2,L1).

repetir(0,_,[]).
repetir(M,N,L) :- M > 0, M1 is M-1, repetir(M1,N,L1), append([N],L1,L).

%11)

%mediana(+L,-M) devuelve la mediana M de la lista L.

mediana(L,M) :- quicksort(L,L1), length(L,N), I is N//2, iesimo(I,L1,M).

%12)

%pertenece(-X,-L) determina si X pertenece o no a la lista L.

pertenece(X,[X|_]).
pertenece(X,[Y|YS]) :- X \= Y, pertenece(X,YS).

%interseccion(+X,+Y,-Z) devuelve la interseccion Z entre las listas X e Y sin repetidos y en el orden de X.

interseccionConDuplicados([],_,[]).
interseccionConDuplicados([X|XS],Y,Z) :- not(pertenece(X,Y)), interseccionConDuplicados(XS,Y,Z).
interseccionConDuplicados([X|XS],Y,[X|Z]) :- pertenece(X,Y), interseccionConDuplicados(XS,Y,Z).
%interseccionConDuplicados([X|XS],Y,Z) :- pertenece(X,Y), interseccionConDuplicados(XS,Y,L1), append([X],L1,Z).

interseccion(X,Y,Z) :- interseccionConDuplicados(X,Y,L), sacarDuplicados(L,Z).

%13) I)

%vacio(+A), raiz(+A,-R), altura(+A,-N), cantidadNodos(+A,-N) son predicados para arboles binarios que corresponden a las operaciones comunes.

vacio(nil).

raiz(bin(_,R,_),R).

altura(nil,0).
altura(bin(I,_,D),N) :- altura(I,H1), altura(D,H2), max(H1,H2,N).
%altura(bin(I,_,D),N) :- altura(I,H1), altura(D,H2), max(H1,H2,M), N is M+1.

cantidadNodos(nil,0).
cantidadNodos(bin(I,_,D),N) :- cantidadNodos(I,C1), cantidadNodos(D,C2), N is C1+C2+1.

%I')

%hoja(+N) determina si el nodo N es una hoja o no.

hoja(bin(nil,_,nil)).

%izq(+A,-I) devuelve la parte izquierda del arbol A y der(+A,-D) la derecha.
 
izq(bin(I,_,_),I).
der(bin(_,_,D),D).

%II)

hpp(A,L) :- hppConRepetidos(A,0,L1), sacarDuplicados(L1,L).

hppConRepetidos(A,_,[])  :- vacio(A).
hppConRepetidos(A,N,[R]) :- hoja(A), P is N mod 2, P =:= 0, raiz(A,R).
hppConRepetidos(A,N,[])  :- hoja(A), P is N mod 2, P =\= 0.
hppConRepetidos(A,N,L)   :- not(vacio(A)), not(hoja(A)), der(A,D), izq(A,I), N1 is N+1,
                            hppConRepetidos(I,N1,L1), hppConRepetidos(D,N1,L2), append(L1,L2,L).
                          
%14)I)

%aBB(+A) determina si A es un arbol binario de busqueda o no.

aBB(nil).
aBB(bin(I,R,D)) :- aBB(I), aBB(D), todosMenoresQue(I,R), todosMayoresQue(D,R).

todosMenoresQue(nil,_).
todosMenoresQue(bin(I,R,D),N) :- N >= R, todosMenoresQue(I,N), todosMenoresQue(D,N).

todosMayoresQue(nil,_).
todosMayoresQue(bin(I,R,D),N) :- N < R, todosMayoresQue(I,N), todosMayoresQue(D,N).

%II) 

%insertarABB(+A,+X,-A1) devuelve el arbol binario de busqueda que resulta de insertar X en el arbol binario de busqueda A.

insertarABB(nil,X,bin(nil,X,nil)).
insertarABB(bin(I,R,D),X,bin(A2,R,D)) :- X =< R, insertarABB(I,X,A2).
insertarABB(bin(I,R,D),X,bin(I,R,A2)) :- X > R, insertarABB(D,X,A2).

%III)

%ramas(+A,-L) devuelve todas las ramas del arbol A.

ramas(A,[])    :- vacio(A).
ramas(A,[[R]]) :- hoja(A), raiz(A,R).
ramas(A,L)     :- not(hoja(A)), izq(A,I), der(A,D), raiz(A,R), ramas(I,L1), ramas(D,L2),
                  agregarATodasLasListas(L1,R,L3), agregarATodasLasListas(L2,R,L4), append(L3,L4,L).
                        
agregarATodasLasListas([],_,[]).
agregarATodasLasListas([Y|YS],X,L1) :- agregarATodasLasListas(YS,X,L2), append([X],Y,L3), append([L3],L2,L1).

%IV)

%ramasInv(+L,-A) devuelve el arbol A con las ramas de L.

ramasInv([],nil).
ramasInv([[R]],bin(nil,R,nil)).
ramasInv(L,bin(I,R,D)) :- head(L,X), head(X,R), sacarPrimerElemento(L,L1), partir(L1,L2,L3), ramasInv(L2,I), ramasInv(L3,D).

partir(L,I,D) :- split(_,L,I,D), empiezanTodasIgual(I), empiezanTodasIgual(D), aIzquierda(I,D).

aIzquierda([],[]).
aIzquierda(L1,[]) :- L1 \= [].
aIzquierda([X|_],[Y|_]) :- head(X,X1), head(Y,Y1), X1 \= Y1.

sacarPrimerElemento([],[]).
sacarPrimerElemento([Y|YS],L1) :- sacarPrimerElemento(YS,L2), tail(Y,L3), append([L3],L2,L1).

empiezanTodasIgual([]).
empiezanTodasIgual([X|XS]) :- head(X,Y), empiezanTodasIgualAux(XS,Y).

empiezanTodasIgualAux([],_).
empiezanTodasIgualAux([X|XS],Y) :-  head(X,Y), empiezanTodasIgualAux(XS,Y).

%15)

%mayores(+A,+M) determina si A es un arbol de naturales.

maximo(hoja(V),M)   :- entre(0,M,V).
maximo(nodo(V,L),M) :- todosMaximos(L,M), sumaHijos(L,N), N1 is N+1, entre(N1,M,V).

sumaHijos([],0).
sumaHijos([hoja(V)|XS],N) :- sumaHijos(XS,N1), N is N1+V.
sumaHijos([nodo(V,L)|XS],N) :- sumaHijos(L,N1), sumaHijos(XS,N2), N is N1+N2+V.

todosMaximos([],_).
todosMaximos([X|XS],M) :- maximo(X,M), todosMaximos(XS,M).

%16)

%combinador(+N,+A,+B,-L) devuelve una lista de longitud N con elementos entre A y B.

combinador(0,_,_,[]).
combinador(N,A,B,L) :- N > 0, N1 is N-1, combinador(N1,A,B,L1), entre(A,B,C), append([C],L1,L).

%17)

%desde(+A,-B) devuelve numeros a partir de A

desde(D,D).
desde(D,X) :- DD is D+1, desde(DD,X).

%semiLatino(+N,-L) devuelve un cuadrado semi latino de dimension N x N.

semiLatino(N,L) :- N > 2, desde(0,A), cuadradoQueSuma(L,N,N,A).

cuadradoQueSuma([],0,_,_).
cuadradoQueSuma(L,N,M,A) :- N > 0, N1 is N - 1, cuadradoQueSuma(L1,N1,M,A), filaQueSuma(F,M,A), append([F],L1,L).

filaQueSuma(F,N,A) :- combinador(N,0,A,F), sumaFila(F,A).

sumaFila([],0).
sumaFila([X|XS],N) :- sumaFila(XS,N1), N is N1+X.

%18)

%personas(+C,-L) devuelve la lista de personas L del censo C.

personas(censo(L),L).

%edad(+C,+P,-E) devuelve la edad E de la persona P en el censo C.

edad(censo([persona(N,E)| _]),N,E).
edad(censo([persona(N1,_)|XS]),N2,E) :- N1 \= N2, edad(censo(XS),N2,E).

%personasEnPromedio(+C,+E,-L) devuelve un conjunto de personas del censo C cuyo promedio de edad es menor a E.

personasEnPromedio(C,E,L) :- personas(C,L1), soloPersonas(L1,L2), subConjuntos(L2,L), L \= [], promedioEdad(C,L,P), P < E.

soloPersonas([],[]).
soloPersonas([persona(N,_)|XS],L) :- soloPersonas(XS,L1), append([N],L1,L).

promedioEdad(C,L,P) :- sumaEdades(C,L,S), length(L,N), P is S//N.

sumaEdades(_,[],0).
sumaEdades(C,[X|XS],N) :- sumaEdades(C,XS,N1), edad(C,X,E), N is N1+E.

subConjuntos([],[]).
subConjuntos([_|XS],L1) :- subConjuntos(XS,L1).
subConjuntos([X|XS],L1) :- subConjuntos(XS,L2), append([X],L2,L1).

%19) Esta en la wiki.