Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
% 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment