Práctica 5 (pre 2010, Paradigmas)

Ejercicio 01

% A partir de los predicados binarios padre y esposo y de los predicados unarios hombre y mujer, definir % en Prolog los predicados binarios: hijo, abuelo, progenitor, hermano, descendiente, tio.

% i. Considerar el ´arbol geneal´ogico de la siguiente figura. Dibuje el ´arbol de b´usqueda de Prolog % para la consulta abuelo(Who, ron).

%padre(-Padre, -Hijo) %esposo(-Hombre, -Mujer)

padre(john, sue). 
padre(john, bill). 
padre(bob, nancy). 
padre(bob, jeff). 
padre(bill, ron). 
esposo(john, mary). 
esposo(bob, sue). 
esposo(bill, jane). 
hombre(john). 
hombre(bob). 
hombre(jeff). 
hombre(bill). 
hombre(ron). 
mujer(mary). 
mujer(sue). 
mujer(nancy). 
mujer(jane). 

%hijo( -Hijo, -Persona)

hijo(Hijo, Persona) :- hombre(Persona), padre(Persona, Hijo). 
hijo(Hijo, Persona) :- mujer(Persona), esposo(Esposo, Persona), hijo(Hijo, Esposo). 

%abuelo(-Abuelo, -Nieto)

abuelo(Abuelo, Nieto) :- hijo(Nieto, Progenitor), hijo(Progenitor, Abuelo). 

%progenitor(-Progenitor, -Hijo)

progenitor(Progenitor, Hijo) :- hijo(Hijo, Progenitor). 

%hermano(-Hermano, -Persona)

hermano(Hermano, Persona) :- progenitor(Progenitor, Hermano), progenitor(Progenitor, Persona), Hermano \= Persona. 

%descendiente(-Descendiente, -Ascendiente)

descendiente(Descendiente, Ascendiente) :- hijo(Descendiente, Ascendiente). 
descendiente(Descendiente, Ascendiente) :- hijo(Descendiente, Padre), descendiente(Padre, Ascendiente). 

%tio(-Tio, -Sobrino)

tio(Tio, Sobrino) :- hijo(Sobrino, Padre), hermano(Tio, Padre). 

% ii. Defina una nueva relaci´on primo. ¿C´omo se puede definir una consulta para conocer todos los % primos de ron?

%primo(-Primo, -OtroPrimo)

primo(Primo, OtroPrimo) :- abuelo(Abuelo, Primo), abuelo(Abuelo, OtroPrimo), Primo \= OtroPrimo. 

%ii. Respuesta: primo(ron, Primo).

% iii. Considerar el agregado del siguiente hecho y regla: % ancestro(X, X). % ancestro(X, Y) :- ancestro(Z, Y), progenitor(X, Z). % y el ´arbol geneal´ogico del item anterior. % a) Explicar la respuesta a la consulta ancestro(bill, X).

% iii. a. ancestro(bill, X). % iii. a. salida: X = bill; X = ron; Loop Infinito...

% b) Describir las circunstancias en las que puede ocurrir un loop infinito en Prolog.

% c) Sugerir un soluci´on al problema hallado en los puntos anteriores reescribiendo el programa % de ancestro.

% iii. c. ancestro:

ancestro(X, X). 
ancestro(X, Y) :- ancestro(Z, Y), progenitor(X, Z). 

Ejercicio 02

% Usando la definici´on de n´umero natural a partir de cero y sucesor, definir un predicado unario nn, % tal que nn(-X) sii X es un n´umero natural. Definir las siguientes relaciones entre n´umeros naturales:

%data Nat = cero | sucesor Nat

%nn(-X).

nn(cero). 
nn(sucesor(X)) :- nn(X). 

tonn(0, cero). 
tonn(X, sucesor(Y)) :- X > 0, PrevX is X - 1, tonn(PrevX, Y). 

% i. moi(-X, +Y) sii X es menor o igual que Y.

moi(cero, Y) :- nn(Y). 
moi(sucesor(X), sucesor(Y)) :- moi(X, Y). 

% menor(-X, +Y) sii X es menor que Y.

menor(cero, sucesor(Y)) :- nn(Y). 
menor(sucesor(X), sucesor(Y)) :- menor(X, Y). 

% ii. producto(+X, +Y, -Z) sii Z es el producto de X con Y. %suma(-X, -Y, -Z) sii Z es la suma de X con Y.

suma(X, cero, X) :- nn(X). 
suma(X, sucesor(Y), sucesor(Z)) :- suma(X, Y, Z). 

%producto(+X, +Y, -Z)

producto(X, cero, cero) :- nn(X). 
producto(X, sucesor(Y), Z) :- producto(X, Y, XPorY), suma(X, XPorY, Z). 

% iii. fact(+X, -F) sii F es el factorial de X. %iii. fact(+X, -F) sii F es el factorial de X.

fact(cero, sucesor(cero)). 
fact(sucesor(X), F) :- fact(X, PrevF), producto(sucesor(X), PrevF, F). 

%iv. mod(+X, +Y, -Z) sii Z es el resto de la divisi´on entrera entre X e Y. Definicion recursiva.

mod(X, X, cero) :- X \= cero, nn(X). 
mod(X, Y, X) :- Y \= cero, X \= Y, moi(X, Y). 
mod(X, Y, Z) :- Y \= cero, suma(XMenosY, Y, X), mod(XMenosY, Y, Z). 

%iv. modNR(+X, +Y, -Z) sii Z es el resto de la divisi´on entrera entre X e Y. Definicion no recursiva. %Propiedad: Z + K * Y = X

modNR(X, X, cero) :- X \= cero, nn(X). 
modNR(X, Y, X) :- Y \= cero, X \= Y, moi(X, Y). 
modNR(X, Y, Z) :- Y \= cero, moi(K, X), menor(Z, Y), producto(K, Y, CasiX), suma(CasiX, Z, X). 

%v. Definir un predicado unario que determine si un n´umero entero dado es primo. Tener en cuenta que el argumento siempre est´a instanciado.

no_es_primo(cero). 
no_es_primo(sucesor(cero)). 
no_es_primo(X) :- nn(X), menor(Menor, X), menor(sucesor(cero), Menor), mod(X, Menor, cero). 
primo(X) :- not(no_es_primo(X)). 

sumaPrimo(float(Entera1, Dec1), float(Entera2, Dec2)) :- 
sumaPrimo(float(Entera1, Dec1), float(Entera2, Dec2)) :- noventaYNueve(N99), moi(Dec1, N99), moi(Dec2, N99), 
producto(Entera1, suc(N99), Ent1), producto(Entera2, suc(N99), Ent2), 
suma(Ent1, Dec1, Num1), suma(Ent2, Dec2, Num2), moi(Num1, Num2), 
suma(Entera2, Dec2, Primo), primo(Primo). 

Ejercicio 04

% Definir los siguientes predicados:

% i. last(-L, -U), donde U es el ´ultimo elemento de la lista L. Definirlo en forma recursiva, y usando % el predicado append definido de la siguiente manera: % append([], X, X). % append( [H | T], Y, [H | Z]) :- append(T, Y, Z).

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

% ii. reverse(+L, -L1), donde L1 contiene los mismos elementos que L, pero en orden inverso. % Ejemplo: reverse([a,b,c], [c,b,a]). % Realizar una definici´on usando append, y otra sin usarlo. Mostrar el ´arbol de prueba para el % ejemplo dado.

% reverse([], []). % reverse([H | T], [ReversedT | [H]]) :- reverse(T, ReversedT). % reverse: como se hace reverse sin append?

reverse2([], []). 
reverse2([H | T], R) :- reverse2(T, ReversedT), append(ReversedT, [H], R). 

% iii. maxlista(+L, -M) y minlista(+L, -M), donde M es el m´aximo/m´inimo de la lista L.

maxlista([H], H). 
maxlista([H | T], H) :- maxlista(T, M), H >= M. 
maxlista([H | T], M) :- maxlista(T, M), H < M. 

minlista([H], H). 
minlista([H | T], H) :- minlista(T, M), H =< M. 
minlista([H | T], M) :- minlista(T, M), H > M. 

% iv. palindromo(+L, -L1), donde L1 es un pal´indromo construido a partir de L. % Ejemplo: palindromo([a,b,c], [a,b,c,c,b,a]).

palindromo(L, P) :- reverse2(L, RevL), append(L, RevL, P). 

% v. doble(-L, -L1), donde cada elemento de L aparece dos veces en L1. % Ejemplo: doble([a,b,c], [a,a,b,b,c,c]).

doble([], []). 
doble([H | T], [H | H | DT]) :- doble(T, DT). 

% vi. prefijo(-P, +L), donde P es prefijo de la lista L.

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

% vii. sufijo(-S, +L), donde S es sufijo de la lista L.

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

% viii. sublista(-S, +L), donde S es sublista de L. % Esta version es para sublistas "continuas" en L.

sublista([], _). 
sublista(S, L) :- append(CasiL, _, L), append(_, S, CasiL), S \= []. 

% Esta version es para sublistas "no continuas" en L.

sublistaB([], []). 
sublistaB([H | SubsT], [H | T]) :- sublistaB(SubsT, T). 
sublistaB(SubsT, [_ | T]) :- sublistaB(SubsT, T). 

% ix. iesimo(-I, +L, -X), donde X es el I-´esimo elemento de la lista L. % Ejemplo: iesimo(2, [10, 20, 30, 40], 20).

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

% Definir los siguientes predicados: % i. mezcla(L1, L2, L3), donde L3 es el resultado de mezclar uno a uno los elementos de las listas % L1 y L2. Si una lista tiene longitud menor, entonces el resto de la lista m´as larga es pasado % sin cambiar. Verificar la reversibilidad, es decir si es posible obtener L3 a partir de L1 y L2, y % viceversa. % Ejemplo: mezcla([a,b,c], [d,e], [a,d,b,e,c]).

mezcla(L1, [], L1). 
mezcla([], L2, L2). 
mezcla([H1 | T1], [H2 | T2], [H1, H2 | T12]) :- mezcla(T1, T2, T12). 

% ii. split(N, L, L1, L2), donde L1 tiene los N primeros elementos de L, y L2 el resto. Si L tiene % menos de N elementos el predicado debe fallar. ¿Cu´an reversible es este predicado? Es decir, % ¿qu´e elementos pueden estar indefinidos al momento de la invocaci´on?

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

% iii. borrar(+ListaConXs, +X, -ListaSinXs), que elimina todas las ocurrencias de X de la lista % ListaConXs.

borrar([], _, []). 
borrar([H | XS], E, [H | YS]) :- E \= H, borrar(XS, E, YS). 
borrar([E | XS], E, YS) :- borrar(XS, E, YS). 

% iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1.

pertenece(E, L1) :- append(Principio, _, L1), append(_, [E], Principio). 
sacarDuplicados([], []). 
sacarDuplicados([H | T], [H | SinDups]) :- borrar(T, H, BorrarH), sacarDuplicados(BorrarH, SinDups). 
sacarDuplicados([H | T], SinDups) :- pertenece(H, T), sacarDuplicados(T, SinDups). 

%Ejecicio 7 %Definir el predicado aplanar(+Xs, -Ys), que es verdadero sii Ys contiene los elementos contenidos %en alg´un nivel de Xs, en el mismo orden de aparici´on. Los elementos de Xs son enteros, ´atomos o %nuevamente listas, de modo que Xs puede tener una profundidad arbitraria. Por el contrario, Ys es %una lista de un solo nivel de profundidad. %Ejemplos: %?- aplanar([a, [3, b, []], [2]], [a, 3, b, 2]). %?- aplanar([[1, [2, 3], [a]], [[[]]]], [1, 2, 3, a]).

aplanar([], []). 
aplanar([H | T], App) :- is_list(H), aplanar(H, AppH), aplanar(T, AppT), append(AppH, AppT, App). 
aplanar([H | T], App) :- not(is_list(H)), aplanar(T, AppT), append([H], AppT, App). 

Ejercicio 08

%Definir los siguientes predicados: %i. ordenada(+L), que ser´a cierta si los elementos de L est´an ordenados en forma ascendente.

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

%ii. quicksort(+L, -L1), donde L1 es el resultado de ordenar L por el m´etodo de quicksort, que %consiste en dividir a L en 2 sublistas con los menores y mayores al primer elemento, ordenar cada %una de ellas y luego proceder a concatenarlas.

quicksort_partir([], _, [], []). 
quicksort_partir([H | T], E, [H | Menores], Mayores) :- (H =< E), quicksort_partir(T, E, Menores, Mayores). 
quicksort_partir([H | T], E, Menores, [H | Mayores]) :- H > E, quicksort_partir(T, E, Menores, Mayores). 

quicksort([], []). 
quicksort([H | T], S) :- quicksort_partir(T, H, Menores, Mayores), quicksort(Menores, MenOrd), 
quicksort(Mayores, MayOrd), append(MenOrd, [H | MayOrd], S). 

%iii. inssort(+L, -L1), donde L1 es el resultado de ordenar L por el m´etodo de inserci´on, que %consiste en insertar cada elemento en el lugar adecuado del resto de la lista ya ordenada.

insertar_ordenado([], E, [E]). 
insertar_ordenado([H | T], E, [E, H | T]) :- E =< H. 
insertar_ordenado([H | T], E, [H | S]) :- E > H, insertar_ordenado(T, E, S). 

inssort([], []). 
inssort([H | T], S) :- inssort(T, SortT), insertar_ordenado(SortT, H, S). 

% Ejercicio 9 % Definir un predicado rotar(+L, +N, -R), tal que R sea la lista L rotada N posiciones (la rotaci´on se % debe hacer hacia la derecha si N>0 y hacia la izquierda si N<0). % Ejemplos: % rotar([1, a, 2, b, 3], 3, X) debe dar como respuesta X = [2, b, 3, 1, a] % rotar([1, a, 2, b, 3], -3, X) debe dar como respuesta X = [b, 3, 1, a, 2]

modulus(N, Modulus, Result) :- Result is ((N mod Modulus) + Modulus) mod Modulus. 

rotar(L, N, R) :- length(L, Length), modulus(N, Length, Rotate), append(Init, Tail, L), 
length(Tail, Rotate), append(Tail, Init, R). 

Ejercicio 10

% Definir un predicado que reciba una lista de n´umeros naturales y devuelva otra lista de n´umeros % naturales, en la que cada n´umero n de la primera lista aparezca repetido n veces en forma consecutiva, % respetando su orden de aparici´on. Considerar que la lista original siempre est´a instanciada. % Ejemplo: para la lista [2, 3, 1, 0, 2] la salida es [2, 2, 3, 3, 3, 1, 2, 2].

repetir_n(_, 0, []). 
repetir_n(E, Times, [E | T]) :- Times > 0, TimesMenos1 is Times - 1, repetir_n(E, TimesMenos1, T). 

repetir_numeros([], []). 
repetir_numeros([H | T], Reps) :- repetir_n(H, H, Hs), repetir_numeros(T, Ts), append(Hs, Ts, Reps). 

Ejercicio 11

% Escribir en Prolog un predicado que devuelva la mediana de una lista (la mediana es el elemento que % se halla en la posici´on del medio de dicha lista, tras ser ordenada). Utilizar los predicados definidos % anteriormente. Considerar que la lista siempre est´a instanciada.

mediana(L, M) :- quicksort(L, S), length(L, Length), Mitad is Length // 2, 
append(Primeros, [M | _], S), length(Primeros, Mitad). 

Ejercicio 12

% Escribir en Prolog los siguientes predicados:

% interseccion(+X, +Y, -Z), tal que Z es la intersecci´on sin repeticiones de las listas X e Y, % % respetando en Z el orden en que aparecen los elementos en X.

interseccion_con_duplicados([], _, []). 
interseccion_con_duplicados([H | T], Y, [H | IntTY]) :- pertenece(H, Y), interseccion_con_duplicados(T, Y, IntTY). 
interseccion_con_duplicados([H | T], Y, IntTY) :- not(pertenece(H, Y)), interseccion_con_duplicados(T, Y, IntTY). 

interseccion(X, Y, Z) :- interseccion_con_duplicados(X, Y, W), sacarDuplicados(W, Z). 

% data Arbol = nil | bin(Arbol, Raiz, Arbol)

Ejercicio 13

% Un ´arbol binario se representar´a en Prolog con: % nil, si es vac´io. % bin(sai, v, sad), donde v es el valor del nodo, sai es el sub´arbol izquierdo y sad es el sub´arbol % derecho. % i. Definir predicados en Prolog para las operaciones comunes de ´arboles: vacio, raiz, altura y % cantidadNodos. Asumir siempre que el ´arbol est´a instanciado.

max(X, Y, X) :- X >= Y. 
max(X, Y, Y) :- X < Y. 
min(X, Y, X) :- X < Y. 
min(X, Y, Y) :- X >= Y. 

%vacio(+Arbol).

vacio(nil). 

%raiz(+Arbol, -Raiz).

raiz(bin(_, Raiz, _), Raiz). 

%altura(+Arbol, -Altura).

altura(nil, 0). 
altura(bin(Izq, _, Der), N) :- altura(Izq, AlturaI), altura(Der, AlturaD), 
max(AlturaI, AlturaD, N). 

%cantidadNodos(+Arbol, -Cantidad).

cantidadNodos(nil, 0). 
cantidadNodos(bin(Izq, _, Der), N) :- cantidadNodos(Izq, CantI), cantidadNodos(Der, CantD), 
N is CantI + CantD + 1. 

% ii. Se define la profundidad de un nodo como la distancia desde la ra´iz hasta el mismo (la ra´iz % tiene profundidad 0). Definir un predicado hpp que permita, dado un ´arbol binario instanciado, % obtener la lista de todos los valores de las hojas que tengan profundidad par. Puede ocurrir que % dos o m´as hojas distintas tengan el mismo valor, pero en la respuesta de hpp los valores no deben % repetirse. % Ejemplo: % hpp( bin(bin(nil, 2, nil), 2, bin(bin(nil, 4, nil), 1, nil) ), L). % L = [4]; % No.

%hpp(+Arbol, -L)

hpp_con_duplicados(nil, 0, []). 
hpp_con_duplicados(nil, 1, []). 
hpp_con_duplicados(bin(Izq, Root, Der), 0, [Root | Res]) :- hpp_con_duplicados(Izq, 1, ResI), hpp_con_duplicados(Der, 1, ResD), 
append(ResI, ResD, Res). 
hpp_con_duplicados(bin(Izq, _, Der), 1, Res) :- hpp_con_duplicados(Izq, 0, ResI), hpp_con_duplicados(Der, 0, ResD), 
append(ResI, ResD, Res). 

% iv. sacarDuplicados(+L1, -L2), que saca todos los elementos duplicados de la lista L1.

pertenece(E, L1) :- append(Principio, _, L1), append(_, [E], Principio). 
sacarDuplicados([], []). 
sacarDuplicados([H | T], [H | SinDups]) :- borrar(T, H, BorrarH), sacarDuplicados(BorrarH, SinDups). 
sacarDuplicados([H | T], SinDups) :- pertenece(H, T), sacarDuplicados(T, SinDups). 

hpp(Arbol, Res) :- hpp_con_duplicados(Arbol, 0, Dups), append([_], L, Dups), sacarDuplicados(L, Res). 

Ejercicio 14

% Definir los siguientes predicados, utilizando la misma representaci´on de ´arbol binario definida en el % ejercicio 13: % i. aBB(+T) que ser´a verdadero si T es un ´arbol binario de b´usqueda.

maximo_vs(nil, N, N). 
maximo_vs(bin(Izq, Root, Der), N, Max) :- maximo_vs(Izq, Root, MaxI), maximo_vs(Der, N, MaxD), 
max(MaxI, MaxD, Max). 
minimo_vs(nil, N, N). 
minimo_vs(bin(Izq, Root, Der), N, Min) :- minimo_vs(Izq, Root, MinI), minimo_vs(Der, N, MinD), 
min(MinI, MinD, Min). 

aBB(nil). 
aBB(bin(Izq, Root, Der)) :- aBB(Izq), aBB(Der), maximo_vs(Izq, Root, Root), 
minimo_vs(Der, Root + 1, Root + 1). 

% ii. aBBInsertar(+X, +T1, -T2) donde T2 resulta de insertar X en orden en el ´arbol T1.

aBBInsertar(X, nil, bin(nil, X, nil)). 
aBBInsertar(X, bin(Izq, Root, Der), bin(NuevoIzq, Root, Der)) :- X =< Root, aBBInsertar(X, Izq, NuevoIzq). 
aBBInsertar(X, bin(Izq, Root, Der), bin(Izq, Root, NuevoDer)) :- X > Root, aBBInsertar(X, Der, NuevoDer). 

Ejercicio 15

% Un ´arbol n-ario de naturales se representar´a en Prolog con: % hoja(V), donde V es un natural seg´un la representaci´øn de Prolog. % nodo(V, Hijos), donde V es un natural seg´un la representaci´øn de Prolog, e Hijos es una lista % no vac´ia de ´arboles n-arios de naturales. % Definir el predicado mayores(+Arbol, +Max) que dado un ´arbol n-ario de naturales (que podr´ia % contener variables en los nodos) devuelve verdadero si: % Los naturales que contiene el ´arbol son menores o iguales a Max (en caso de ser variables, deber´an % instanciarse con valores en dicho rango). % El valor de cada nodo del ´arbol es mayor que la suma de los valores de sus hijos. % ejemplo: mayores(nodo(X, [hoja(0), nodo(1,[hoja(0), hoja(0)]),nodo(4,[hoja(1), hoja(0), nodo(1, [hoja(0)])])]),9)

%in_range(+Min, +Max, -Num).

in_range(Min, Max, Min) :- Min =< Max. 
in_range(Min, Max, N) :- Min =< Max, NextMin is Min + 1, in_range(NextMin, Max, N). 

valor(hoja(V), V). 
valor(nodo(V, _), V). 

mayores(hoja(V), Max) :- in_range(0, Max, V). 
mayores(nodo(V, [X]), Max) :- valor(X, Val), in_range(0, Max, Val), Val1 is Val + 1, in_range(Val1, Max, V). 
mayores(nodo(V, [X, Y | T]), Max) :- valor(X, Val), in_range(0, Max, Val), Val1 is Val + 1, in_range(Val1, Max, V), 
VMenosX is V - Val, mayores(nodo(VMenosX, [Y | T]), Max). 

%mayores no anda bien, no hace la suma de todos los subhijos, sino de los inmediatos... como se hace bien? facilmente?

Ejercicio 16

% Definir el predicado combinador(+L,+D,+H,-XS), que debe dar verdadero cuando XS es una lista de % naturales de longitud L, y cada uno de sus elementos XSi cumple que D ? XSi ? H. No se deben devolver % soluciones repetidas. % Por ejemplo: combinador(2,3,5,X). % X = [3,3] ; % X = [3,4] ; % X = [3,5] ; % X = [4,3] ; % X = [4,4] ; % X = [4,5] ; % X = [5,3] ; % X = [5,4] ; % X = [5,5] ;

%in_range(+Min, +Max, -Min).

in_range(Min, Max, Min) :- Min =< Max. 
in_range(Min, Max, N) :- Min =< Max, NextMin is Min + 1, in_range(NextMin, Max, N). 

%combinador(+L, +D, +H, -XS).

combinador(0, _, _, []). 
combinador(L, Min, Max, [H | T]) :- L > 0, in_range(Min, Max, H), L1 is L - 1, combinador(L1, Min, Max, T). 

Ejercicio 17

% Un cuadrado semi-latino es una matriz cuadrada de naturales (incluido el cero) donde todas las filas % de la matriz suman lo mismo. Por ejemplo: % 1 3 0 % 2 2 0 todas las filas suman 4 % 1 1 2 % Representamos la matriz como una lista de filas, donde cada fila es una lista de naturales. El ejemplo % anterior se representar´ia de la siguiente manera: [[1,3,0],[2,2,0],[1,1,2]]. % Se pide definir el predicado cuadradoSemiLatino(N,XS). El par´ametro N debe estar instanciado, y % XS no puede estar instanciado. El predicado debe ir devolviendo matrices (utilizando la representaci % ´on antes mencionada), que sean cuadrados semi-latinos de dimensi´on N*N. Dichas matrices deben % devolverse de manera ordenada: primero aqu´ellas cuyas filas suman 0, luego 1, luego 2, etc.. % Ejemplo: cuadradoSemiLatino(2,X). devuelve: % X = [[0, 0], [0, 0]] ; % X = [[0, 1], [0, 1]] ; % X = [[0, 1], [1, 0]] ; % X = [[1, 0], [0, 1]] ; % X = [[1, 0], [1, 0]] ; % X = [[0, 2], [0, 2]] ; % etc. % Para la implementaci´on de cuadradoSemiLatino se cuenta con el siguiente predicado: % desde(D, D). % desde(D, X) :- DD is D+1, desde(DD, X).

%desde(+Desde, -Numero).

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

%lista_semi_latina(+Longuitud, +Suma, -Lista).

lista_semi_latina(0, 0, []). 
lista_semi_latina(Long, Suma, [H | T]) :- Long > 0, Suma >= 0, Long1 is Long - 1, in_range(0, Suma, H), 
NuevaSuma is Suma - H, lista_semi_latina(Long1, NuevaSuma, T). 

%rectanguloSemiLatino(+Columnas, +Filas, +Suma, -XS).

rectanguloSemiLatino(_, 0, Suma, []) :- Suma >= 0. 
rectanguloSemiLatino(Columnas, Filas, Suma, [H | T]) :- Filas > 0, Filas1 is Filas - 1, lista_semi_latina(Columnas, Suma, H), 
rectanguloSemiLatino(Columnas, Filas1, Suma, T). 

%cuadradoSemiLatino(+N, -XS).

cuadradoSemiLatino(N, X) :- desde(0, Suma), rectanguloSemiLatino(N, N, Suma, X). 

Ejercicio 18

% Sea la estructura Agenda, y los siguientes predicados disponibles: % personas(+Agenda, -Personas), que tiene ´exito cuando Personas contiene toda la lista % personas de la Agenda. % edad(+Agenda, +Persona, -Edad), que tiene ´exito cuando la Persona tiene edad Edad % la Agenda. % Definir el predicado personasEnPromedio(+Agenda, +Edad, -Conjunto) que tenga ´exito cuando % Conjunto sea una lista de Personas de la Agenda, cuyo promedio de edad sea menor a Edad.

%personas(+Agenda, -Personas).

personas(agenda(Personas), Personas). 

%edad(+Agenda, +Persona, -Edad).

edad(agenda([persona(Nombre, Edad) | _]), Nombre, Edad). 
edad(agenda([persona(OtroNombre, Edad) | Resto]), Nombre, Edad) :- OtroNombre \= Nombre, 
edad(agenda(Resto), Nombre, Edad). 
subconjuntos_personas(agenda([]), []). 
subconjuntos_personas(agenda([H | T]), [H | Sub]) :- subconjuntos_personas(agenda(T), Sub). 
subconjuntos_personas(agenda([_ | T]), Sub) :- subconjuntos_personas(agenda(T), Sub). 

%promedio_edades(Personas, Edad).

suma_edades([persona(_, Edad)], Edad). 
suma_edades([persona(_, Edad) | T], Suma) :- suma_edades(T, SumaT), Suma is SumaT + Edad. 

%personasEnPromedio(+Agenda, +Edad, -Conjunto).

personasEnPromedio(Agenda, Edad, Conjunto) :- subconjuntos_personas(Agenda, Conjunto), suma_edades(Conjunto, Suma), 
length(Conjunto, Cantidad), Promedio is (Suma // Cantidad), Edad > Promedio. 

%caso: personasEnPromedio(agenda([persona(0, 0), persona(0, 1), persona(0, 2), persona(0, 3), persona(0, 4), persona(0, 5)]), 0, X).

Ejercicio 19

% (opcional) % Torres de Hanoi. Se tienen tres estacas A, B y C, y N discos de distintos tama˜nos, perforados en el % centro. Los discos pueden apilarse en las estacas formando torres, y est´an ubicados inicialmente en % la estaca A en orden decreciente de tama˜no. El problema consiste en mover los discos de A a C de % tal manera que terminen ordenados como lo estaban originalmente. La tarea debe efectuarse bajo las % siguientes restricciones: % En cada paso s´olo un disco puede moverse de una estaca a otra. % Nunca puede ubicarse un disco sobre otro m´as peque˜no. % Usando Prolog, modelar y resolver el problema de las torres de Hanoi para tres estacas y N discos. % data Estacas = a | b | c % data Movimiento = Mover Estacas Estacas

%es_estaca(+E).

es_estaca(a). 
es_estaca(b). 
es_estaca(c). 

%estacas_diferentes(-E1, -E2, -E3).

estacas_diferentes(a, b, c). 
estacas_diferentes(a, c, b). 
estacas_diferentes(b, a, c). 
estacas_diferentes(b, c, a). 
estacas_diferentes(c, a, b). 
estacas_diferentes(c, b, a). 

%hanoi_mover(+N, +Desde, +Hasta, -Movimientos).

hanoi_mover(0, Desde, Hasta, []) :- es_estaca(Desde), es_estaca(Hasta). 
hanoi_mover(N, Desde, Hasta, Movimientos) :- N > 0, N1 is N - 1, estacas_diferentes(Desde, Hasta, Otra), 
hanoi_mover(N1, Desde, Otra, MovsDesdeOtra), 
hanoi_mover(N1, Otra, Hasta, MovsOtraHasta), 
append(MovsDesdeOtra, [mov(Desde, Hasta) | MovsOtraHasta], Movimientos). 

%hanoi(+N, -Movimientos).

hanoi(N, Movimientos) :- hanoi_mover(N, a, c, Movimientos). 

Funciones Varias

%repeat(-Elemento, -Lista). % Requiere: true. % Asegura: Lista es una lista que contiene solamente a Elem (cero o mas veces).

repeat(_, []). 
repeat(Elem, [Elem | Tail]) :- repeat(Elem, Tail). 

%multi_length(-Lista_de_Listas, -Lista_de_Longuitudes). % Requiere: Lista_de_Listas es una lista de listas, y Lista_de_Longuitudes es una lista de naturales. % Asegura: Lista_de_Longuitudes es una lista que contiene las longuitudes de los elementos de Lista_de_Listas.

multi_length([], []). 
multi_length([X | XS], [L | LS]) :- length(X, L), multi_length(XS, LS). 

%multi_append(-Lista_de_Listas, -Listas_Unidas). % Requiere: Lista_de_Listas no contiene ninguna lista vacia, pero ella si puede ser la lista vacia. % Asegura: Listas_Unidas son todas las listas de la listas unidas, % en el orden en que aparecian en la lista de listas.

multi_append([], []). 
multi_append([[X] | YS], [X | ZS]) :- multi_append(YS, ZS). 
multi_append([[X1, X2 | XS] | YS], [X1 | ZS]) :- multi_append([[X2 | XS] | YS], ZS). 

%particion_doble(-Parte1, -Parte2, -Lista). % Requiere: true. % Asegura: Parte1 y Parte2 son una particion de Lista en dos listas, % preservando en ellas el orden relativo original de los elementos.

particion_doble([], [], []). 
particion_doble([X | XS], [], [X | XS]). 
particion_doble([], [Y | YS], [Y | YS]). 
particion_doble([X | XS], [Y | YS], [X | ZS]) :- particion_doble(XS, [Y | YS], ZS). 
particion_doble([X | XS], [Y | YS], [Y | ZS]) :- particion_doble([X | XS], YS, ZS). 

%particion_doble_sin_vacio(-Parte1, -Parte2, -Lista). % Requiere: true. % Asegura: Parte1 y Parte2 son una particion de Lista en dos listas (ninguna vacia), % preservando en ellas el orden relativo original de los elementos.

particion_doble_sin_vacio([X], [Y | YS], [X, Y | YS]). 
particion_doble_sin_vacio([X1, X2 | XS], [Y | YS], [X1 | ZS]) :- particion_doble_sin_vacio([X2 | XS], [Y | YS], ZS). 
particion_doble_sin_vacio([X1, X2 | XS], [Y | YS], [X1 | ZS]) :- particion_doble_sin_vacio([Y | YS], [X2 | XS], ZS). 

%particion(-ListaDeSublistas, +Lista). % Requiere: Lista es una Lista, ListaDeSublistas una lista de listas. % Asegura: ListaDeSublistas es una lista de sublistas disjuntas que forman Lista.

particion([], []). 
particion( XS, [X | XS]). 
particion([[X | XS], Y | YS], ZS) :- particion_doble_sin_vacio([X | XS], PS, ZS). 

%particion_de_longuitud_n(+Lista, +Longuitud, -ListaDeSublistas) % Requiere: Lista es una Lista de longuitud multiplo de Longuitud, ListaDeSublistas una lista de listas. % Asegura: ListaDeSublistas es una lista de sublistas disjuntas que forman Lista cada una de longuitud Longuitud.

particion_de_longuitud_n(Lista, Longuitud, ListaDeSublistas) :- particion(ListaDeSublistas, Lista), 
length(Lista, Length_Lista), Cantidad is Length_Lista // Longuitud, 
repeat(Longuitud, Lista_Longs), length(Lista_Longs, Cantidad), 
multi_length(ListaDeSublistas, Lista_Longs). 

%lista_de_grupos(+Lista_de_Paises_en_Grupos, +Ids, -Grupos).

lista_de_grupos([], [], []). 
lista_de_grupos([P | PS], [I | IS], [grupo(I, P) | GS]) :- lista_de_grupos(PS, IS, GS). 

% Requiere: length(Lista_de_Paises_en_Grupos) == length(Ids). % Asegura: Grupos es la formacion de grupos asignando un id a cada grupo de paises de la lista.

%mesclar_particiones_de_listas(-Particiones, +Listas_de_Listas).

grupos(Ps, Ids, Grupos) :- lista_de_grupos(Lista_de_Paises_en_Grupos, Ids, Grupos). 

%grupos(+Ps, +Ids, -Grupos)

grupos(Ps, Ids, Grupos) :- lista_de_grupos(Lista_de_Paises_en_Grupos, Ids, Grupos). 

paises([[argentina, brasil], [mejico,canada], 
[sudafrica, egipto]]). 
listas([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]). 
listas2([1, 2, 3]). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funciones de Numeros - Start % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%es_natural(-Numero).

es_natural(0). 
es_natural(N) :- es_natural(N1), N is N1 + 1. 

%es_positivo(-Numero).

es_positivo(1). 
es_positivo(N) :- es_natural(N1), N is N1 + 1. 

%es_negativo(-Numero).

es_negativo(-1). 
es_negativo(N) :- es_negativo(N1), N is N1 - 1. 

%diferencia_con_siguiente_entero(-Signo, +Numero).

diferencia_con_siguiente_entero(1, 0). 
diferencia_con_siguiente_entero(1, N) :- N > 0. 
diferencia_con_siguiente_entero(0, N) :- N < 0. 

%es_entero(-Signo, +Numero).

es_entero(0). 
es_entero(N) :- es_entero(M), NM is -M, diferencia_con_siguiente_entero(S, NM), 
N is NM + S. 

%signo_aux(-Signo, +Numero).

signo_aux(0, 0). 
signo_aux(1, N) :- N > 0. 
signo_aux(-1, N) :- N < 0. 

%signo(-Signo, -Numero).

signo(0, 0). 
signo(S, N) :- es_entero(N), N \= 0, signo_aux(S, N). 

%en_rango(-Numero, +Desde, +Hasta).

en_rango(D, D, H) :- D =< H. 
en_rango(N, D, H) :- D =< H, ND is D + 1, en_rango(N, ND, H). 

%desde(-Numero, +Desde).

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funciones de Numeros - End % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funciones de Arboles - Start % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%es_arbol_de_altura(-Arbol, +Altura).

es_arbol_de_altura(nil, 0). 
es_arbol_de_altura(bin(I, _, D), H) :- H > 0, H1 is H - 1, 
en_rango(HI, 0, H1), 
en_rango(HD, 0, H1), H1 is max(HD, HI), 
es_arbol_de_altura(I, HI), es_arbol_de_altura(D, HD). 

%altura(-Arbol, -Altura).

altura(A, H) :- es_natural(H), es_arbol_de_altura(A, H). 

%preorder_de_arboles(-Nodos, -Arbol).

preorder_de_arboles([], []). 
preorder_de_arboles(L, [nil | AS]) :- preorder_de_arboles(L, AS). 
preorder_de_arboles([X | XS], [bin(I, X, D) | AS]) :- preorder_de_arboles(XS, [I, D | AS]). 

%preorder(-Nodos, -Arbol).

preorder(L, A) :- preorder_de_arboles(L, [A]). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funciones de Arboles - End % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funciones de Listas - Comienzo % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% map_tomar_uno_de_lista(-Reordenado, -Resto, +ListaDeListas) % Requiere: true. % Asegura: Reordenado es una lista formada agarrando un elemento de cada sublista % de ListaDeListas y Resto es lo que queda despues de sacar eso. % Uso:

map_tomar_uno_de_lista([], [], []). 
map_tomar_uno_de_lista([H | T], [R | RS], [L | LS]) :- particion_doble_unicas_vacia([H], R, L), 
map_tomar_uno_de_lista(T, RS, LS). 

% particion(-ListaDeSublistas, +Lista). % Requiere: true. % Asegura: ListaDeSublistas es una lista de sublistas disjuntas que forman Lista. % particion( XS, [X | XS]). % particion([[X | XS], Y | YS], ZS) :- particion_doble_unicas([X | XS], WS, ZS), particion(Y | YS, WS).

% particion_doble_unicas(-Parte1, -Parte2, -Lista). % Requiere: true. % Asegura: Parte1 y Parte2 son una particion de Lista en dos listas (ninguna vacia), % preservando en ellas el orden relativo original de los elementos.

particion_doble_unicas([X], [Y | YS], [X, Y | YS]). 
particion_doble_unicas([X1, X2 | XS], [Y | YS], [X1 | ZS]) :- particion_doble_unicas([X2 | XS], [Y | YS], ZS). 
particion_doble_unicas([X1, X2 | XS], [Y | YS], [X1 | ZS]) :- particion_doble_unicas([Y | YS], [X2 | XS], ZS). 

% particiones_de_longuitud_n(-ListaDeSublistas, +Longuitud, +Lista) % Requiere: true. % Asegura: ListaDeSublistas es una lista de sublistas disjuntas que forman Lista cada una de longuitud Longuitud.

particiones_de_longuitud_n([XS], L, XS) :- length(XS, L). 
particiones_de_longuitud_n([X | XS], L, ZS) :- not(length(ZS, L)), particion_doble_unicas(X, YS, ZS), length(X, L), 
particiones_de_longuitud_n(XS, L, YS). 

% map_particiones_de_longuitud_n(-Sublistas, +CantidadDeGrupos, +Listas) % Requiere: true. % Asegura: similar a Haskell: map particiones_de_longuitud_n.

map_particiones_de_longuitud_n([], N, []) :- N > 0. 
map_particiones_de_longuitud_n([X | XS], N, [Y | YS]) :- map_particiones_de_longuitud_n(XS, N, YS), 
particiones_de_longuitud_n(X, N, Y). 

% iesimos_elementos(-Iesimos, +Indice, -ListaDeListas) % Requiere: true. % Asegura: Iesimos son los iesimos elementos de cada lista de ListaDeListas.

iesimos_elementos([], N, []) :- N >= 0. 
iesimos_elementos([E | XS], I, [Y | YS]) :- nth0(I, Y, E), iesimos_elementos(XS, I, YS). 

% generar_listas_tomando_de_listas_entre_iesimos(-Reordenado, +Desde, +Hasta, +ListaDeListas)

generar_listas_tomando_de_listas_entre_iesimos([], D, H, L) :- D > H, is_list(L). 
generar_listas_tomando_de_listas_entre_iesimos([X | XS], D, H, YS) :- D =< H, D1 is D + 1, iesimos_elementos(X, D, YS), 
generar_listas_tomando_de_listas_entre_iesimos(XS, D1, H, YS). 

% last(+N, -Tail, -Lista). % Requiere: true. % Asegura: Tail son los ultimos n elementos de Lista.

last(N, Tail, Lista) :- length(Tail, N), append(_, Tail, Lista). 

% sin_iesimo(-ListaSinIesimo, -Indice, -Lista) % Requiere: true % Asegura: ListaSinIesimo es la lista sin el elemento en la posicion Indice de Lista.

sin_iesimo(NL, I, L) :- append(Init, [_ | Tail], L), length(Init, I), append(Init, Tail, NL). 

% sin_primera_aparicion(-ListaSinElemento, -Elemento, -Lista) % Requiere: true. % Asegura: ListaSinElemento es igual a Lista sin la primera aparicion del elemento.

sin_primera_aparicion(ZS, E, L) :- append(ZS1, [E | ZS2], L), append(ZS1, ZS2, ZS), not(member(E, ZS1)). 

% concat(-Lista_de_Listas, -Listas_Unidas). % Requiere: true. % Asegura: Listas_Unidas son todas las listas de la listas unidas, % en el orden en que aparecian en la lista de listas.

concat([], []). 
concat([[X] | YS], [X | ZS]) :- concat(YS, ZS). 
concat([[X1, X2 | XS] | YS], [X1 | ZS]) :- concat([[X2 | XS] | YS], ZS). 

% map_concat(-ListaDeListasDeListas, +ListasMappeadas) % Requiere: true. % Asegura: similar a Haskell: map concat

map_concat([], []). 
map_concat([X | XS], [Y | YS]) :- concat(X, Y), map_concat(XS, YS). 

% take(+N, -Tail, -Lista). % Requiere: true. % Asegura: Tail son los elementos que quedan luego de sacar los n primeros % elementos a Lista.

drop(N, Tail, Lista) :- length(Init, N), append(Init, Tail, Lista). 

% pertenece(-Elemento, -Lista) % Requiere: true % Asegura: Elemento pertenece a Lista.

pertenece(E, L) :- append(_, [E | _], L). 

% sin_un_elemento(-ListaSinElemento, -Elemento, -Lista) % Requiere: true. % Asegura: ListaSinElemento es igual a Lista sin una vez ese elemento.

sin_un_elemento(ZS, E, L) :- append(ZS1, [E | ZS2], L), append(ZS1, ZS2, ZS). 

% sin_elemento(-ListaSinElementos, +Elemento, +Lista) % Requiere: true. % Asegura: ListaSinElementos es igual a Lista sin todas las apariciones del elemento.

sin_elemento([], _, []). 
sin_elemento(L, H, [H | T]) :- sin_elemento(L, H, T). 
sin_elemento([H | L], E, [H | T]) :- E \= H, sin_elemento(L, E, T). 

% iesimo(-Elemento, -Indice, -Lista) % Requiere: true % Asegura: Elemento es el elemento en la posicion Indice de Lista.

iesimo(E, I, L) :- append(Init, [E | _], L), length(Init, I). 

% interseccion(-Interseccion, +ListaL, +ListaR) % Requiere: true. % Asegura: Interseccion es la interseccion sin duplicados de ListaL y ListaR % manteniendo el orden de los elementos en ListaL.

interseccion([], [], []). 
interseccion([E | ZS], [E | LL], LRE) :- member(E, LRE), delete(LRE, E, LR), 
interseccion(ZS, LL, LR). 
interseccion(ZS, [E | LL], LR) :- not(member(E, LR)), interseccion(ZS, LL, LR). 

% sin_repetidos(-ListaSinRepetidos, +Lista). % Requiere: true. % Asegura: ListaSinRepetidos es igual a Lista solo que no tiene repetidos.

sin_repetidos([], []). 
sin_repetidos([E | XS], [E | YS]) :- not(member(E, YS)), sin_repetidos(XS, YS). 
sin_repetidos(XS, [E | YS]) :- member(E, YS), sin_repetidos(XS, YS). 
sin_repetidos([E | XS], [E | YS]) :- member(E, YS), sin_repetidos(XSE, YS), 
select(E, XSE, XS). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Funciones de Listas - Fin % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%