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