Hace unos días encontré este desafío en internet:
Se trata de encontrar un código (combinación de tres números), a través de las siguientes pistas:
-
682: Un número es correcto y en su posición correcta.
-
614: Un número es correcto pero mal posicionado.
-
206: Dos números son correctos peros su posición no.
-
738: Nada es correcto.
-
780: Un número es correcto pero mal posicionado.
El ejercicio es ideal para resolverlo mediante varios paradigmas de programación, los cuales hemos estado revisando en los siguientes enlaces:
-
Paradigmas y tipos de lenguajes informáticos. Un enfoque practico
-
Puedes encontrar el código en github (en la carpeta Fuentes/Desafios/EncuentraElCodigo)
En este caso vamos a resolverlo usando Prolog y C, para que veamos sus diferencias:
-
Prolog es un lenguaje lógico/declarativo en que vamos expresando “hechos” o cosas que consideramos como ciertas, al final la combinación de los hechos debe darnos el resultado buscado
-
C es un leguaje imperativo/estructurado, en este tipo de lenguajes, nosotros vamos armando, paso a paso, el camino para encontrar la solución.
Solución en Prolog
Prolog es un buen lenguaje pare resolver este problema, tal como está expresado, porque tenemos una serie de pistas o circunstancia que se deben cumplir, ese conocimiento lo implementaremos en forma de reglas, dentro de nuestro programa.
Puedes ver este código y ejecutarlo en línea en https://swish.swi-prolog.org/p/EncuentraElCodigo.pl.
Cada pista será una regla, el resultado final debe cumplir todas las reglas para ser exitoso.
Cada regla, pudiera cumplirse de más de una forma, pero el resultado final debe cumplir por lo menos una
682: Un número es correcto y en su posición correcta
% 682: Un número es correcto y en su posición correcta.
regla1(X,_,_):- X==6.
regla1(_,X,_):- X==8.
regla1(_,_,X):- X==2.
Por lo menos la regla1 debe cumplirse de una forma, ya sea que el 6, este al principio, el 8 en el medio o el 2 al final.
614: Un número es correcto pero mal posicionado
% 614: Un número es correcto pero mal posicionado.
regla2(_,X,_):- X==6.
regla2(_,_,X):- X==6.
regla2(X,_,_):- X==1.
regla2(_,_,X):- X==1.
regla2(X,_,_):- X==4.
regla2(_,X,_):- X==4.
Se juega con las posiciones de los números, por lo menos uno se debe cumplir.
206: Dos números son correctos peros su posición no
Regla 3 parte uno. Un número es correcto pero mal posicionado.
% Regla 3 parte uno. Un numero es correcto pero mal posicionado
regla3a(_,X,_):- X==2.
regla3a(_,_,X):- X==2.
regla3b(X,_,_):- X==0.
regla3b(_,_,X):- X==0.
regla3c(X,_,_):- X==6.
regla3c(_,X,_):- X==6.
Regla 3 parte dos. Dos números son correctos, con lo que deben cumplirse dos reglas de las anteriores.
regla3(A,B,C):- regla3a(A,B,C), regla3b(A,B,C).
regla3(A,B,C):- regla3a(A,B,C), regla3c(A,B,C).
regla3(A,B,C):- regla3b(A,B,C), regla3c(A,B,C).
738: Nada es correcto
% 738: Nada es correcto.
regla4(X,Y,Z):- not(member(7,[X,Y,Z])),
not(member(3,[X,Y,Z])),
not(member(8,[X,Y,Z])).
Esta es la regla más sencilla, no puede contener ni 7, ni 3, ni 8.
780: Un número es correcto pero mal posicionado
% 780: Un número es correcto pero mal posicionado
regla5(_,X,_):- X==7.
regla5(_,_,X):- X==7.
regla5(X,_,_):- X==8.
regla5(_,_,X):- X==8.
regla5(X,_,_):- X==0.
regla5(_,X,_):- X==0.
Esta regla es igual que la regla 2.
El código final (el resultado): Debe cumplir la todas las reglas
% El codigo debe complir todas las reglas
codigo(X,Y,Z):- regla1(X,Y,Z),
regla2(X,Y,Z),
regla3(X,Y,Z),
regla4(X,Y,Z),
regla5(X,Y,Z).
Comprobación de los resultados
Genero los posibles resultado en un matriz (que van de 000 a 888).
% Genero los posibles resultados,segun las pistas, deben ser
% 0,1,2,3,4,6,7,8 (curiosamente no esta el 5, ni el 9)
% crea una coleccion de matrices que va desde [0,0,0] a [8,8,8]
posiblesResultados(R):- M=[0,1,2,3,4,6,7,8],
findall(N,member(N,M),L),
findall([X,Y,Z],(member(X,L),member(Y,L),member(Z,L)),R).
Busco el código final, entre todos los resultados
% De los posibles resultados, busca los que cumplan el codigo
buscarCodigo(R):- posiblesResultados(M),
findall(L, (member(L,M), codigo(L)),R).
/* Resultados
?- buscarCodigo(R).
R = [[0, 4, 2], [0, 6, 2]]
El resultado 042 cumple todas las reglas.
El resultado 062 tambien las cumple, de forma no excluyente.
*/
Los números que cumplen todos los criterios son el 042 y el 062
El número 062 es válido, si considerarnos como no excluyentes las pistas. Por ejemplo en la primera pista 682: Un número es correcto y en su posición correcta, no consideramos que solo uno es correcto, si no que por lo menos uno. Si los consideramos excluyentes, debiéramos implementar nuevas reglas para tal efecto y solo seria valido el 042,
Solución en C
Haber solucionado el problema en Prolog previamente nos da un indicio de cómo debe solucionarse con otra aproximaciones, en generar se puede estructurar en pequeñas soluciones parciales llamadas reglas y el código final debe cumplir todas las reglas.
Puedes revisar y ejecutar el código en https://repl.it/@JoseLuisLuis65/EncuentraElCodigo
El problema en C lo resolveremos de la siguiente forma:
-
Crearemos pequeñas tablas de conocimiento, que nos definan que escenarios son posibles, cada fila en cada escenario representa un valor posible.
-
Cada regla tendrá definido una tabla de conocimiento, por lo menos debe cumplirse un escenario de la tabla.
-
Al final debe cumplirse todas las reglas, para obtener el resultado.
682: Un número es correcto y en su posición correcta
// 682: Un número es correcto y en su posición correcta.
bool regla1(int x, int y, int z)
{
int validos[3][3] = {
{ 6, X, X },
{ X, 8, X },
{ X, X, 2 }
};
return validar(validos, 3, x, y, z);
}
614: Un número es correcto pero mal posicionado
// 614: Un número es correcto pero mal posicionado.
bool regla2(int x, int y, int z)
{
int validos[6][3] = {
{ X, 6, X },
{ X, X, 6 },
{ 1, X, X },
{ X, X, 1 },
{ 4, X, X },
{ X, 4, X }
};
return validar(validos, 6, x, y, z);
}
206: Dos números son correctos peros su posición no
// 206: Dos números son correctos peros su posición no
bool regla3(int x, int y, int z)
{
int validos1[2][3] = {
{ X, 2, X },
{ X, X, 2 },
};
int validos2[2][3] = {
{ 0, X, X },
{ X, X, 0 },
};
int validos3[2][3] = {
{ 6, X, X },
{ X, 6, X },
};
bool valido =
(validar(validos1, 2, x, y, z)
&& validar(validos2, 2, x, y, z)) ||
(validar(validos1, 2, x, y, z)
&& validar(validos3, 2, x, y, z)) ||
(validar(validos2, 2, x, y, z)
&& validar(validos3, 2, x, y, z));
return valido;
}
738: Nada es correcto
// 706: Nada es correcto.
bool regla4(int x, int y, int z)
{
int invalidos[] = { 7, 3, 8 };
int valores[] = { x, y, z };
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (invalidos[i] == valores[j])
return false;
return true;
}
780: Un número es correcto pero mal posicionado
// 780: Un número es correcto pero mal posicionado
bool regla5(int x, int y, int z)
{
int validos[6][3] = {
{ X, 7, X },
{ X, X, 7 },
{ 8, X, X },
{ X, X, 8 },
{ 0, X, X },
{ X, 0, X }
};
return validar(validos, 6, x, y, z);
}
El código final (el resultado): Debe cumplir la todas las reglas
bool codigo(int x, int y, int z)
{
return regla1(x, y, z) &&
regla2(x, y, z) &&
regla3(x, y, z) &&
regla4(x, y, z) &&
regla5(x, y, z);
}
La siguiente función comprueba que por lo menos una fila sea exitosa, de cada tabla de posibles soluciones.
bool validar(int validos[][3], int filas, int x, int y, int z)
{
//Veo si alguna fila es valida
for (int i = 0; i < filas; i++)
{
bool valido =
(validos[i][0] == X
|| validos[i][0] == x) &&
(validos[i][1] == X
|| validos[i][1] == y) &&
(validos[i][2] == X
|| validos[i][2] == z);
if (valido) return true;
}
// Ninguna es valida
return false;
}
Comprobación de los resultados
int main(void)
{
const int MAX_POSIBLES = 8;
// Genero los posibles resultados,segun las pistas, deben ser
// 0,1,2,3,4,6,7,8 (curiosamente no esta el 5, ni el 9)
int posibles[] = { 0, 1, 2, 3, 4, 6, 7, 8 };
// Recorro todas las posibles soluciones y veo las que tengan exito
for (int i = 0; i < MAX_POSIBLES; i++)
for (int j = 0; j < MAX_POSIBLES; j++)
for (int k = 0; k < MAX_POSIBLES; k++)
if (codigo(i, j, k))
printf("[%d %d %d] ", i, j, k);
return 0;
}
Conclusiones
La solución en Prolog, parece mas sencilla de implementar, dada la naturaleza declarativa del lenguaje, y que el problema en sí consiste en que se deben cumplir una seria de reglas (especialidad de Prolog).
Comparando los tamaños de los archivos en líneas código obtenemos la siguiente grafica.
Es decir para resolver el problema necesitamos 86 líneas en Prolog y 150 en c, comparando porcentajes seria así:
Con lo que podemos concluir que es más conciso resolver este tipo de problemas usando Prolog, que usando C.
Si te ha gustado la entrada, ¡Compártela! ;-)
Nota: Puedes encontrar todo el código fuente de este artículo en https://github.com/jbautistamartin/ParadigmasTiposLenguajes
No hay comentarios:
Publicar un comentario