prolog-exercises.pl

% Ejercicio 1a
% Comprobar si una lista de elementos constituye un conjunto válido
% Un conjunto es una lista de elementos que no contiene elementos repetidos

% pertenece(Lista, Elemento): true si Elemento esta en Lista
pertenece([], _) :- fail.
pertenece([E|_], E) :- !.
pertenece([_|L], E) :- pertenece(L, E).

% esConjunto(Lista): true si Lista es un conjunto
esConjunto([]) :- !.
esConjunto([E|L]) :- not(pertenece(L, E)), esConjunto(L).

% conjunto(C, L): verifica si C es un conjunto con los elementos de L
conjunto(C, []) :- esConjunto(C), !.
conjunto(C, [H|L]) :- pertenece(C, H), conjunto(C, L).

% 1b. Determina si un elemento pertenece a un conjunto
% perteneceAConjunto(Conjunto, Elemento): Elemento se encuentra en Conjunto y Conjunto es un Conjunto
perteneceAConjunto(C, E) :- esConjunto(C), pertenece(C, E).

% 1c. Incorpora un elemento a un conjunto
% insertarEnConjunto(C, E, CE): CE es el resultado de insertarEnConjunto E en C
insertarEnConjunto(C, E, C) :- perteneceAConjunto(C, E), !.
insertarEnConjunto(C, E, C2) :- append(C, [E], C2).

% 1d. Unir dos conjuntos
% unirConjuntos(C, C2, U): U es el resultado de la union entre C y C2
unirConjuntos([], [], []) :- !.
unirConjuntos([], C, C) :- esConjunto(C), !.
unirConjuntos([H|T], C, U) :-
	unirConjuntos(T, C, U2),
	insertarEnConjunto(U2, H, U).

% 1e. Intersectar dos conjuntos
% intersectarConjuntos(C, C2, I): I es la intersección entre C y C2
intersectarConjuntos([], C, []) :- esConjunto(C), !.
intersectarConjuntos([H|T], C, I) :-
	not(perteneceAConjunto(C, H)),
	intersectarConjuntos(T, C, I),
	!.
intersectarConjuntos([H|T], C, I) :-
	intersectarConjuntos(T, C, I2),
	insertarEnConjunto(I2, H, I).

% 1f. Calcular la diferencia entre dos conjuntos
% diferencia(C, C2, D): D es la diferencia entre C2 y C
diferencia(_, [], []) :- !.
diferencia(C, [H|T], D) :-
	perteneceAConjunto(C, H),
	diferencia(C, T, D),
	!.
diferencia(C, [H|T], D) :-
	diferencia(C, T, D2),
	insertarEnConjunto(D2, H, D).

% 1h. Dada una lista de elementos con repeticiones, construir un conjunto que contenga todos los elementos de esa lista.
% convertir(L, C): C es el conjunto formado con los elementos sin repeticiones de la lista L
convertir([], []) :- !.
convertir([H|T], C) :- convertir(T, C2), insertarEnConjunto(C2, H, C).

% 2. Definir predicados recursivos para ordenar:
%   1. Una lista de números

% pivotNros(P, L, I, D):
% 	la magia del quicksort se encuentra aquí, particiona el array
% 	de palabras L en los arrays I y D, I contiene los números que
% 	se encuentran antes del número P y D los números que se
% 	encuentran después.
pivotNros(_, [], [], []) :- !.
pivotNros(P, [H|T], [H|I], D) :- H =< P, !, pivotNros(P, T, I, D).
pivotNros(P, [H|T], I, [H|D]) :- H > P, !, pivotNros(P, T, I, D).

% quicksortNros(L, R): R es el resultado de ordenar el array de números L 
quicksortNros([], []).
quicksortNros([P|L], R) :-
	pivotNros(P, L, I, D),
	quicksortNros(I, I2),
	quicksortNros(D, D2),
	append(I2, [P|D2], R).

%   2. Una lista de palabras (una palabra se representa como una lista de carácteres)

% compararPalabras(P1, P2):
% 	devuelve true si P1 se encuentra antes de P2
% 	en orden lexicográfico 
compararPalabras([], []) :- fail.
compararPalabras([], _) :- !.
compararPalabras(_, []) :- !.
compararPalabras([H|T], [H|T2]) :- compararPalabras(T, T2).
compararPalabras([H|_], [H2|_]) :- char_code(H, X), char_code(H2, X2), X < X2.

% pivotPalabras(P, L, I, D):
% 	particiona el array de palabras L en los arrays I y D,
% 	I contiene las palabras que se encuentran antes de
% 	la palabra P y D las palabras que se encuentran después
% 	(en orden lexicográfico).
pivotPalabras(_, [], [], []) :- !.
pivotPalabras(P, [H|T], [H|I], D) :- compararPalabras(H, P), !, pivotPalabras(P, T, I, D).
pivotPalabras(P, [H|T], I, [H|D]) :- compararPalabras(P, H), !, pivotPalabras(P, T, I, D).

% quicksortPalabras(L, R):
% 	R es el resultado de ordenar en orden lexicográfico las palabras
% 	que se encuentran en el array L.
quicksortPalabras([], []).
quicksortPalabras([P|L], R) :-
	pivotPalabras(P, L, I, D),
	quicksortPalabras(I, I2),
	quicksortPalabras(D, D2),
	append(I2, [P|D2], R).

% 5. Definir eval
% unionExclusiva(C, C2, U): U es el conjunto resultado de la unión exclusiva entre C y C2.
unionExclusiva(C, C2, U) :-
	diferencia(C, C2, D1),
	diferencia(C2, C, D2),
	unirConjuntos(D1, D2, U).

% eval(Expr, Eval): Eval es el resultado de evaluar Expr
eval(E, E) :- esConjunto(E).
eval(A+B, R) :- eval(A, R1), eval(B, R2), unirConjuntos(R1, R2, R).
eval(A/B, R) :- eval(A, R1), eval(B, R2), unionExclusiva(R1, R2, R).
eval(A-B, R) :- eval(A, R1), eval(B, R2), diferencia(R2, R1, R).
eval(A*B, R) :- eval(A, R1), eval(B, R2), intersectarConjuntos(R1, R2, R).

% 8 Árbol
% esArbol(A): devuelve si A es un árbol
esArbol(#).
esArbol(t(_, B, C)) :- esArbol(B), esArbol(C).

% crearArbolVacio(X): crea un arbol vacío y lo retorna en X
crearArbolVacio(#).

% insertar(E, A, NA): NA es el resultado de ingresar el valor E en el árbol A
insertar(V, #, t(V, #, #)) :- !.
insertar(V, t(V, I, D), t(V, I, D)) :- !.
insertar(V, t(R, I, D), t(R, I, D2)) :-
	V > R,
	!,
	insertar(V, D, D2).
insertar(V, t(R, I, D), t(R, I2, D)) :-
	V < R,
	!,
	insertar(V, I, I2).

anterior(V, t(V, I, #), I) :- !.
anterior(V, t(P, I, D), t(P, I, D2)) :- anterior(V, D, D2).

% eliminar(E, A, NA): NA es el árbol resultante de eliminar el nodo con el valor E del árbol A
eliminar(_, #, #).
eliminar(V, t(V, I, #), I) :- !.
eliminar(V, t(V, #, D), D) :- !.
eliminar(V, t(V, I, D), t(A, I2, D)) :- !, anterior(A, I, I2).
eliminar(V, t(R, I, D), t(R, I2, D)) :- V < R, !, eliminar(V, I, I2).
eliminar(V, t(R, I, D), t(R, I, D2)) :- V > R, !, eliminar(V, D, D2).

% altura(A, X): X es la altura del árbol A
altura(#, 0).
altura(t(_, #, #), 1) :- !.
altura(t(_, I, D), A) :- altura(I, AI), altura(D, AD), A is max(AI, AD) + 1.

% balanceado(A): true si A esta balanceado
balanceado(#).
balanceado(t(_, I, D)) :-
	balanceado(I),
	balanceado(D),
	altura(I, AI),
	altura(D, AD),
	abs(AI - AD) < 2.

:- begin_tests(pertenece).
test(pertenece) :- pertenece([1, 2, 3], 1).
test(pertenece) :- pertenece([1, 2, 3], 2).
test(pertenece) :- pertenece([1, 2, 3], 3).
test(pertenece, [fail]) :- pertenece([], 1).
test(pertenece, [fail]) :- pertenece([1, 2, 3], 4).
:- end_tests(pertenece).

:- begin_tests(esConjunto).
test(esConjunto) :- esConjunto([]).
test(esConjunto) :- esConjunto([1]).
test(esConjunto) :- esConjunto([1, 2, 3]).
test(esConjunto, [fail]) :- esConjunto([1, 2, 1]).
:- end_tests(esConjunto).

:- begin_tests(perteneceAConjunto).
test(perteneceAConjunto) :- perteneceAConjunto([1, 2, 3], 1).
test(perteneceAConjunto) :- perteneceAConjunto([1, 2, 3], 2).
test(perteneceAConjunto) :- perteneceAConjunto([1, 2, 3], 3).
test(perteneceAConjunto, [fail]) :- perteneceAConjunto([], 1).
test(perteneceAConjunto, [fail]) :- perteneceAConjunto([1, 2, 3], 4).
test(perteneceAConjunto, [fail]) :- perteneceAConjunto([1, 1, 2, 3], 1).
test(perteneceAConjunto, [fail]) :- perteneceAConjunto([1, 2, 3, 4, 3], 1).
:- end_tests(perteneceAConjunto).

:- begin_tests(insertarEnConjunto).
test(insertarEnConjunto) :- insertarEnConjunto([], 1, [1]).
test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 1, [1, 2, 3]).
test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 2, [1, 2, 3]).
test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 3, [1, 2, 3]).
test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 4, [1, 2, 3, 4]).
test(insertarEnConjunto) :-
	E = 4,
	insertarEnConjunto([1, 2, 3], E, [1, 2, 3, 4]).
test(insertarEnConjunto) :-
	C = [1, 2, 3],
	insertarEnConjunto(C, 4, [1, 2, 3, 4]).
:- end_tests(insertarEnConjunto).

:- begin_tests(unirConjuntos).
test(unirConjuntos) :- unirConjuntos([], [], []).

test(unirConjuntos) :-
	unirConjuntos([1, 2], [3, 4], L),
	conjunto(L, [1, 2, 3, 4]).

test(unirConjuntos) :-
	unirConjuntos([1, 2], [1, 2], L),
	conjunto(L, [1, 2]).
	
test(unirConjuntos) :-
	unirConjuntos([1, 2], [1, 2, 3], L),
	conjunto(L, [1, 2, 3]).

test(unirConjuntos) :-
	unirConjuntos([1, 2, 3, 4], [2], L),
	conjunto(L, [1, 2, 3, 4]).

test(unirConjuntos) :-
	unirConjuntos([1, 2, 3, 4], [2, 3, 4, 5], L),
	conjunto(L, [1, 2, 3, 4, 5]).

:- end_tests(unirConjuntos).

:- begin_tests(intersectarConjuntos).
test(intersectarConjuntos) :- intersectarConjuntos([], [], []).

test(intersectarConjuntos) :- intersectarConjuntos([1, 2], [3, 4], []).

test(intersectarConjuntos) :- intersectarConjuntos([1, 2], [1, 2], L),
	conjunto(L, [1, 2]).
	
test(intersectarConjuntos) :-
	intersectarConjuntos([1, 2], [1, 2, 3], L),
	conjunto(L, [1, 2]),
	not(conjunto(L, [1, 2, 3])).

test(intersectarConjuntos) :-
	intersectarConjuntos([1, 2, 3, 4], [2], L),
	conjunto(L, [2]),
	not(perteneceAConjunto(L, 1)),
	not(perteneceAConjunto(L, 3)),
	not(perteneceAConjunto(L, 4)).

test(intersectarConjuntos) :-
	intersectarConjuntos([1, 2, 3, 4], [2, 3, 4, 5], L),
	conjunto(L, [2, 3, 4]),
	not(perteneceAConjunto(L, 1)),
	not(perteneceAConjunto(L, 5)).
:- end_tests(intersectarConjuntos).

:- begin_tests(diferencia).
test(diferencia) :- diferencia([], [], []).

test(diferencia) :-
	diferencia([1, 2], [3, 4], L),
	conjunto(L, [3, 4]),
	not(perteneceAConjunto(L, 1)),
	not(perteneceAConjunto(L, 2)).

test(diferencia) :- diferencia([1, 2], [1, 2], []).
	
test(diferencia) :-
	diferencia([1, 2], [1, 2, 3], L),
	perteneceAConjunto(L, 3),
	not(perteneceAConjunto(L, 2)),
	not(perteneceAConjunto(L, 1)).

test(diferencia) :- diferencia([1, 2, 3, 4], [2], []).

test(diferencia) :-
	diferencia([1, 2, 3, 4], [2, 3, 4, 5], L),
	perteneceAConjunto(L, 5),
	not(perteneceAConjunto(L, 1)),
	not(perteneceAConjunto(L, 2)),
	not(perteneceAConjunto(L, 3)),
	not(perteneceAConjunto(L, 4)).
:- end_tests(diferencia).

:- begin_tests(convertir).
test(convertir) :- convertir([], []).
test(convertir) :-
	convertir([1, 2, 3], C),
	conjunto(C, [1, 2, 3]).

test(convertir) :-
	convertir([1, 2, 3, 1, 2], C),
	conjunto(C, [1, 2, 3]).
:- end_tests(convertir).

:- begin_tests(eval).
test(eval) :- eval([1,2,3], [1, 2, 3]).
test(eval) :-
	eval([1,2]+[3,4], A),
	unirConjuntos([1, 2], [3, 4], A).

test(eval) :-
	eval(([1,2]+[3,4])+[5,6], A),
	unirConjuntos([1, 2], [3, 4], R),
	unirConjuntos(R, [5, 6], A).

test(eval) :-
	eval(([a,b,c,d,e]/[d,e,f,g,h])+([h,i,j,k,l]*([j,k,l,m,n,t,u]-[m,n])), A),
	conjunto(A, [a,b,c,f,g,h,j,k,l]).
:- end_tests(eval).

:- begin_tests(arbol).
% tests para crear árboles e insertar elementos
test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, t(30, #, #)).

test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, t(30, t(15, #, #), #)).

test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, t(30, t(15, t(7, #, #), #), t(31, #, #))).

test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(15, A3, A4),
	insertar(31, A4, t(30, t(15, #, #), t(31, #, #))).

% tests para eliminar elementos del árbol
% hoja
test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	eliminar(7, A5, t(30, t(15, #, #), t(31, #, #))).

% cabeza
test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	eliminar(30, A5, t(15, t(7, #, #), t(31, #, #))).

% medio
test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	eliminar(15, A5, t(30, t(7, #, #), t(31, #, #))).

% tests para la altura del árbol
test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	altura(A5, 3).

test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	insertar(32, A5, A6),
	insertar(33, A6, A7),
	insertar(34, A7, A8),
	altura(A8, 5).

% tests para ver si un árbol esta balanceado
test(arbol) :- balanceado(#).

test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	balanceado(A5).

test(arbol) :-
	crearArbolVacio(A),
	insertar(30, A, A2),
	insertar(15, A2, A3),
	insertar(7, A3, A4),
	insertar(31, A4, A5),
	insertar(32, A5, A6),
	insertar(33, A6, A7),
	insertar(34, A7, A8),
	not(balanceado(A8)).
:- end_tests(arbol).

:- begin_tests(qsort).
test(qsort) :- quicksortNros([1, 2, 3], [1, 2, 3]).
test(qsort) :- quicksortNros([], []).
test(qsort) :- quicksortNros([3, 2, 1], [1, 2, 3]).
test(qsort) :- quicksortNros([5, 6, 1, 3, 4, 7], [1, 3, 4, 5, 6, 7]).

test(qsort) :- quicksortPalabras([], []).
test(qsort) :- quicksortPalabras([
	[c,a,s,a,m,i,e,n,t,o],
	[a,r,b,o,l],
	[c,a,s,a]
], [
	[a,r,b,o,l],
	[c,a,s,a],
	[c,a,s,a,m,i,e,n,t,o]
]).
test(qsort) :- quicksortPalabras([
	[a,a],
	[a,a],
	[a,c]
], [
	[a,a],
	[a,a],
	[a,c]
]).
test(qsort) :- quicksortPalabras([
	[a,a],
	[a,b],
	[a,c]
], [
	[a,a],
	[a,b],
	[a,c]
]).
:- end_tests(qsort).

:- run_tests.