Práctica 5 (pre 2010, Paradigmas)

(Nota: esta todo posteado con %, como para poder probarlo directo en prolog)

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). 

Ejercicio 05

% 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).

Ejercicio 07

%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 09

% 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).