Segundo Parcial 2do Cuat 2007 (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1: Programación Lógica[editar]

Implementar los siguientes predicados respetando la instanciacion pedida. No utilizar cut (!) ni predicados de alto orden (como setof). La unica excepcion es el not, que esta permitido.

Item A[editar]

Resolver sopas de letras: Se requiere definir el predicado resolver(+Tablero,+ListaPalabras,-Solucion) que indica si Solucion es una solucion a la sopa de letras representada por Tablero y ListaPalabras.

Solucion debe ser una lista de la misma longitud que ListaPalabras tal que su iesimo elemento indica la posicion y direccion en la que se encontro la iesima palabra de ListaPalabras en Tablero.

Representaremos el tablero por una lista de listas de caracteres (los atomos a, b, ..., z) y las palabras por una lista de caracteres. Todas las listas del tablero tendran igual longitud. Los elementos de la lista Solucion deben ser de la forma pos(i,j,d) donde i y j son los ındices de la fila y columna de la primera letra de la palabra, respectivamente, y d es una de las 8 direcciones: arr,ab,der,izq,ar-der,ar-izq,ab-der,ab-izq.

Nota: puede haber varias o ninguna solucion. No se deben devolver soluciones repetidas.

Ejemplo:

?- resolver([[a,c,a,l],[s,o,s,o],[e,a,i,s]],[[l,a,c,a],[s,o,l],[s,o,s],[a,s]],S).
S = [pos(0,3,izq),pos(2,3,arr),pos(1,0,der),pos(0,0,ab)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,0,der),pos(0,2,ab)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,0,der),pos(2,1,arr-izq)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,0,der),pos(2,1,arr-der)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,2,izq),pos(0,0,ab)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,2,izq),pos(0,2,ab)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,2,izq),pos(2,1,arr-izq)];
S = [pos(0,3,izq),pos(2,3,arr),pos(1,2,izq),pos(2,1,arr-der)];
No

Respuesta 1

resolver(Tablero, [], []).
resolver(Tablero, [P|Ps], [S|Ss]) :- ubicacion(Tablero, P, S), resolver(Tablero, Ps, Ss).

ubicacion(T, [], P).
ubicacion(T, [A|As], pos(I,J,D)) :- lth0(I,J,T,A), nextPos(I,J,D,P), ubicacion(T,As,P).

nextPos(I,J,arr, pos(I2,J2,arr)) :- I2 is I-1, J2 is J.
nextPos(I,J,ab, pos(I2,J2,ab)) :- I2 is I+1, J2 is J.
nextPos(I,J,der, pos(I2,J2,der)) :- I2 is I, J2 is J+1.
nextPos(I,J,izq, pos(I2,J2,izq)) :- I2 is I, J2 is J-1.
nextPos(I,J,ar-der, pos(I2,J2,ar-der)) :- I2 is I-1, J2 is J+1.
nextPos(I,J,ar-izq, pos(I2,J2,ar-izq)) :- I2 is I-1, J2 is J-1.
nextPos(I,J,ab-der, pos(I2,J2,ab-der)) :- I2 is I+1, J2 is J+1.
nextPos(I,J,ab-izq, pos(I2,J2,ab-izq)) :- I2 is I+1, J2 is J-1.

lth0(I, J, T, L) :- nth0(I, T, Fila), nth0(J, Fila, L). 

Respuesta 2

dir(X) :- 
    member(X, [arr,ab,der,izq,arr-der,arr-izq,ab-der,ab-izq]).

resolver(_, [], []).
resolver(T, [P|PS], [S|XS]) :-
    esSolucion(T, P, S),
    resolver(T, PS, XS).

esSolucion(T, P, pos(Y,X,D)) :-
    dir(D),
    encaja(T, X, Y, D, P).

encaja(_, _, _, _, []).
encaja(T, X, Y, D, [P|PS]) :-
    enTablero(T, X, Y),
    letra(T, X, Y, P),
    proximoCasillero(X, Y, D, X2, Y2),
    encaja(T, X2, Y2, D, PS).

enTablero(T, X, Y) :-
    length(T, ALTO),
    BALTO is ALTO - 1,
    entre(0, BALTO, Y),
    nth0(Y, T, FILA),
    length(FILA, ANCHO),
    BANCHO is ANCHO - 1,
    entre(0, BANCHO, X).

letra(T, X, Y, P) :-
    nth0(Y, T, FILA),
    nth0(X, FILA, P).

proximoCasillero(X, Y, arr, X, Y2) :- Y2 is Y - 1.
proximoCasillero(X, Y, ab,  X, Y2) :- Y2 is Y + 1.
proximoCasillero(X, Y, der, X2, Y) :- X2 is X + 1.
proximoCasillero(X, Y, izq, X2, Y) :- X2 is X - 1.
proximoCasillero(X, Y, arr-izq, X2, Y2) :- X2 is X - 1, Y2 is Y - 1.
proximoCasillero(X, Y, arr-der, X2, Y2) :- X2 is X + 1, Y2 is Y - 1.
proximoCasillero(X, Y, ab-izq, X2, Y2) :- X2 is X - 1, Y2 is Y + 1.
proximoCasillero(X, Y, ab-der, X2, Y2) :- X2 is X + 1, Y2 is Y + 1.

Item B[editar]

Generar sopas de letras: Se pide definir el predicado generar(-Tablero,+ListaDePalabras) que dice si la sopa representada es resoluble. En caso de venir no instanciado, se deben generar todos los tableros validos en algun momento y no se deben devolver soluciones repetidas.

Respuesta 1

generar(T,L) :- generarTablero(T), not(not(resolver(T,L,S))).

generarTablero(T) :- dimension(X,Y), tablero(T,X,Y).

filaTablero([], 0).
filaTablero([A|As], X) :- X > 0, X1 is X - 1, isChar(A), filaTablero(As,X1).

tablero([], X, 0).
tablero([F|Fs], X, Y) :- Y > 0, Y1 is Y - 1, filaTablero(F,X), tablero(Fs,X,Y1).

dimension(X,Y) :- between(1,inf,X1), between(1,X1,Y1), isPerm(X1,Y1,X,Y).

isPerm(X,Y,X,Y).
isPerm(X,Y,Y,X) :- X =\= Y.

isChar(a).
isChar(b).
isChar(c).
isChar(z).

Respuesta 2

desde(A, A).
desde(A, X) :- AA is A + 1, desde(AA, X).

generarTablero(T, P) :-
    desde(1, N), 
    entre(1, N, ALTO),
    entre(1, N, ANCHO),
    tableroDe(ALTO, ANCHO, T),
    not(not(resolver(T, P, _))).

tableroDe(ALTO, ANCHO, T) :-
    length(T, ALTO),
    filasDe(ANCHO, T).

filasDe(_, []).
filasDe(ANCHO, [F|FS]) :-
    length(F, ANCHO),
    soloLetras(F),
    filasDe(ANCHO, FS).

soloLetras([]).
soloLetras([L|LS]) :-
    member(L, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]),
    soloLetras(LS).

Item C[editar]

Generar sopas de letras II: Se pide definir el predicado generar2(+Tablero,-ListaDePalabras) que dice si la sopa representada es resoluble. En caso de venir no instanciada, se deben generar todas las listas de palabras posibles. No se deben devolver soluciones repetidas. La lista de palabras no debe contener palabras repetidas.

Ejemplo:

?- generar2([[a,c,a,l],[s,o,s,o],[e,a,i,s]],L).
L = [[a]];
L = [[a],[c]];
L = [[a,c]];
...
No

Respuesta

generar2(Tablero, L) :- between(1,inf,X), generarLista(L,X), noDup(L), not(not(resolver(Tablero,L,S))).

generarLista([], 0).
generarLista([P|Ps], X) :- between(1,X,Y), generarPalabra(P,Y), R is X-Y, generarLista(Ps,R).

generarPalabra([], 0).
generarPalabra([A|As], X) :- X > 0, X1 is X-1, isChar(A), generarPalabra(As,X1).

noDup([]).
noDup([X|Xs]) :- not(member(X,Xs)), noDup(Xs).


Ejercicio 2: Resolucion Lógica[editar]

Sea N(x) el predicado unario “x es un numero natural” y M(x, y) el predicado binario “x es menor o igual que y”.

Dados los siguientes enunciados:

  1. Hay un mınimo natural (i.e., hay un numero natural menor o igual al resto de los numeros naturales).
  2. Todo numero natural tiene otro numero natural menor o igual.

Demostrar asumiendo (1) que se cumple (2), utilizando resolucion general.

Respuesta

Proposicion: Hay un minimo natural








Goal negado: No es cierto que Todo numero natural tiene otro numero natural menor o igual.










Resolucion

Clausulas:

De
Con
Agrego

De
Agrego

De
Agrego clausula vacia

Por lo tanto, el target es insatisfacible
Por lo tanto, la negacion del target es verdadera
Por lo tanto, todo numero natural tiene otro numero natural menor o igual

Ejercicio 3: Herencia[editar]

Para este ejercicio definiremos las clases A, B, C, tal que A es clase padre de B y esta de C. Cada una de ellas tendra dos mensajes do1 y do2, implementados como sigue:

A do1: Transcript show ’A’. A1 a1.
A do2: Transcript show ’a’. A2 a2.
B do1: Transcript show ’B’. B1 b1.
B do2: Transcript show ’b’. B2 b2.
C do1: Transcript show ’C’. C1 c1.
C do2: Transcript show ’c’. C2 c2.

Reemplazar en cada caso las letras mayusculas por super o self y las letras minusculas por do1 o do2 (o argumentar por que no es posible) de manera que al ejecutar (C new) do1. se imprima en el transcript la secuencia:
a) (4 puntos) CbAcBaCbAcBa...
b) (4 puntos) CBACacCBACac...
c) (4 puntos) CBaCbcCBaCbc...

Item A[editar]

Secuencia C b A c B a ...

A do1: Transcript show ´A´. self  do2.
A do2: Transcript show ´a´. self  do1. 
B do1: Transcript show ´B´. super do2.
B do2: Transcript show ´b´. super do1.
C do1: Transcript show ´C´. super do2.
C do2: Transcript show ´c´. super do1.

Item B[editar]

Secuencia C B A C a c ...

No se puede ya que la unica que muestra C es "C do1" y en el primer caso debe llamar a "super do1" y en el segundo caso se debería hacer algo así como "super super do2" y no se puede.

Item C[editar]

Secuencia C B a C b c ...

No se puede ya que la unica que muestra C es "C do1" y en el primer caso debe llamar a "super do1" y en el segundo caso a "super do2".

Ejercicio 4: Colecciones[editar]

Item A[editar]

Extender la clase Collection para que soporte un mensaje aplanar sin parametros que dada una coleccion de colecciones devuelva la concatenacion de estas. El tipo de la coleccion devuelta debe ser el mismo que el de la receptora.

Respuesta

aplanar
	"Aplana una coleccion"

	| ret |
	ret := self class new.
	self do: 
		[:sec | sec do: [:each | ret add: each] ].
	^ret.

Test Case

bagOfArrays := Bag new.
bagOfArrays addAll: #( #(1 2) #(3 4 5) #() #(6)).
bagOfArrays aplanar. Bag (1 2 3 4 5 6)
bagOfArrays aplanar collect: [:each | each.].

Item B[editar]

Extender la clase Collection para que reciba un nuevo mensaje evaluarSegunIndice:aBlock. Sean p1, ..., pn los resultados de evaluar aBlock usando los enteros 1, ..., n como parametro, respectivamente. Cada elemento de la coleccion receptora sera un bloque y se debe devolver una coleccion del mismo tipo donde cada uno de sus elementos proviene de evaluar el i-esimo bloque de la receptora utilizando pi como parametro.

Respuesta

evaluarSegunIndice: aBlock

	| index |
	index := 0.

	^(self collect: 
	[:each |
		index := index + 1.
		(each value: (aBlock value: index)).
	]).

Test Case

bagOfBlocks := Bag new.
bagOfBlocks add: [:n | (10 + n).].
bagOfBlocks add: [:n | (20 + n).].
bagOfBlocks add: [:n | (30 + n).].
bagOfBlocks evaluarSegunIndice: [:n | 2*n.]. Bag (16 22 34)

Item C[editar]

Utilizando los items anteriores, extender la clase Collection para que reciba un nuevo mensaje multipElems que devuelva una coleccion del mismo tipo. Si los elementos de la coleccion receptora son , entonces la coleccion devuelta debe ser , es decir, el i-esimo elemento aparece repetido i veces.

Respuesta

El enunciado es un poco vago y no se sabe bien a qué apunta. Acá se propone la siguiente resolución:

multipElems
|repeat|
repeat := [:n :e |
		|res|
		res := self class new.
		1 to: n do: [:nx | res add: e].
		res.
 	   ].

^((self collect: [:e | [:n | repeat value:n value:e]]) evaluarSegunIndice: [:i|i]) aplanar.


Ejercicio 5: Subtipado[editar]

Hallar tipos S y T tal que la cantidad de tipos X que cumplen

estrictamente (o sea, X no es igual a ninguno de sus limites) sea exactamente 43. Considerar los tipos basicos y no Top ni Bottom. Permutaciones de un registro cuentan como el mismo tipo.

Respuesta

Si queremos que haya 43 tipos estrictos podemos pensar que es lo mismo que tener 45 tipos no estrictos (ya que luego se le resta cada una de las cotas). 45 puede dividirse en factores primos como , vamos a ver como podemos repartir la combinatoria para que nos de esa cantidad.

Usando "entre(A, B)" como la cantidad de tipos no estrictos entre A y B, y

planteamos

Vamos a tratar de lograr 9 entre esos tipos

Si

Si

por lo tanto si entonces .

Ahora debemos lograr 5 tipos con la otra parte que nos queda, queremos

Con , "x" puede tomar los valores: Bool, Nat, Int, Float o no estar presente. Eso nos da un total de 5 tipos posibles.

Finalmente, con tenemos un total de 45 tipos no estrictos lo que nos da un total de 43 tipos estrictos.