Prolog: Acertijo jarras de agua
Tags: prolog, jarras, agua, riddle
Published: 2020-03-23 03:09:07

Al empezar a aprender **Prolog**, surgen ejercicios de razonamiento como el acertijo de las jarras de agua, el cual menciona que se tiene 2 jarras, de 5 y 3 litros de capacidad respectivamente, sin ninguna marca de medición, además se tiene una fuente de agua ilimitada que permite llenar las jarras de agua. Se requiere exactamente 4 litros de agua en una de las jarras. En este blog se explica la resolución del acertijo.

Hay que tener en cuenta 3 aspectos fundamentales antes de programar el acertijo en cualquier lenguaje de programación; y estos son los siguientes:

**1.** *Es necesario entender el problema.*
**2.** *Resolver el problema, esto se lo puede hacer mentalmente o como yo, que prefiero plasmar la resolución sobre una hoja de  papel, mediante gráficos que ayuden a entender mejor la resolución del acertijo.*
**3.** *Por último, una vez que haya resuelto el acertijo o problema, es momento de plasmar la solución utilizando un lenguaje de prgramación, Prolog en este caso.*

Para resolver este acertijo se va a utilizar los 3 aspectos recomendados en el punto anterior.

###**1. ¿Cuál es el problema?**
No  se puede medir exactamente los 4 litros de agua dado que se dispone de 2 jarras de 5 y 3 litros sin marcas de medición.

###**2. ¿Cómo resuelvo el problema?**
Para lograr medir los 4 litros necesarios, se requiere realizar un conjunto de pasos, veamos:
Se puede partir llenando cualquiera de las 2 jarras, ***la jarra grande*** (5lt) o ***jarra pequeña*** (3lt), por ejemplo, se llena primero la jarra grande.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/xjc4os2jkau1xyhycmfs.png)

Una vez lleno la jarra de 5 litros,  se vierte el contenido de la jarra grande en la pequeña, dando como resultado, **2** y **3** litros de agua; la jarra pequeña queda llena.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ad31kqqxopf8i0z4z0yb.png)

Como tercer paso, se vacía la jarra pequeña.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/f0uuw70qlua3f6blmoxh.png)

En el cuarto paso, se vierte el contenido de la jarra grande donde hay 2lt de agua a la jarra pequeña, quedando al final 0 litros de agua en la jarra grande y 2 litros en la jarra pequeña.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/483nc0ymffz50tk00cu8.png)

En el quinto paso, se llena nuevamente la jarra grande.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/1zjwq1fpex9zjvlnxhws.png)

En el paso 6, que es el último, se vierte el contenido de la jarra grande a la pequeña donde hay 2lt de agua, dado que solo falta un litro para llenar la jarra pequeña; y la jarra grande contiene 5 litros de agua, al pasar de la jarra grande a la pequeña, resulta **4** litros de agua en la jarra grande.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/0tpx723opp8yam5wst4v.png)

En este paso se ha resuelto el problema en **6** pasos, cabe mencionar que esta no es la única solución, dado que existen varias soluciones, por ejemplo, se puede partir llenando la jarra pequeña (3lt).

###**3. Programar solución**

En este punto esta claro lo que se va a programar, el objetivo de este tutorial no es enseñar cómo funciona **Prolog**, al contrario se entiende que el lector tiene conocimientos, al menos básicos sobre este lenguaje de programación lógico e interpretado.

Se parte de un hecho, donde el estado deseado es que la **jarra grande** (5lt) contenga 4 litros de agua como estado final, para lo cual en **Prolog** se representa de la siguiete manera:
```prolog
estado(4, _ )
```
Donde, el número 4 representa la cantidad de agua en la jarra grande y el símbolo ( **_** ) representa que no interesa el valor en la **jarra pequeña** (3lt), este estado final se lo representará como el siguiente hecho:
```prolog
meta(estado(4, _ )).
```
Para continuar, es necesario definir las variables con las que se va a trabajar, por tanto, a continuación se define las siguientes variables:

***CJG*** = cantidad de agua en la jarra grande
***CJP*** = cantidad de agua en la jarra pequeña
***MJG*** = capacidad máxima de la jarra grande (5lt)
***MJP*** = capacidad máxima de la jarra pequeña (3lt)

A continuación es necesario definir todas las reglas (***8 reglas***) para la resolución del acertijo, donde la verdad de un hecho depende de la verdad de otro hecho o conjunto de hechos. Un estado posible dependerá de un conjunto de reglas, por ejemplo:

**1.** El estado posible puede ser que la jarra grande quede llena, y este hecho se representa de la siguiente manera en Prolog:
```prolog
posible(estado(CJG , CJP), estado(CJG1, CJP), MJG, _)
```
Dado que las reglas se componen de una cabeza y un cuerpo, falta definir el cuerpo de esta regla, que es nada más que otro conjunto de hechos. Para el posible estado mencionado anteriormente se define ciertas condiciones y estas son: **CJG >= 0, CJG < MJG, CJG1 is MJG**, el símbolo ( **,** ) representa un **AND** en prolog y el ( **.** ) el final de un predicado, la palabra reservada **is** representa la igualdad ( **=** ), por tanto, la regla completa queda de la siguiente manera:
```prolog
posible(estado(CJG, CJP), estado(CJG1, CJP), MJG, _) :- CJG >= 0, CJG < MJG, CJG1 is MJG .
```
Esta expresión se lee de la siguiente manera, solo se puede llenar la jarra grande, si la jarra no esta llena. Es decir la jarra grande debe estar vacía o contener una cantidad de agua menor a la capacidad de la jarra (**CJG >= 0, CJG < MJG**), si esto se cumple la cantidad de agua es actualizada con la capacidad de la jarra lo que equivale a llenar la jarra (**CJG1 is MJG**).

En el estado posible, se definen 2 estados, esto quiere decir que hay un estado inicial y un final, se puede apreciar también que en el  segundo estado cambia **CJG** por **CJG1** dado que solo cambiará de estado la jarra grande. Además el posible estado, recibe 2 argumentos más, que son las capacidades de las jarras, dado que solo me interesa el cambio de estado de la jarra grande, se requiere saber la capacidad de dicha jarra, por tanto paso **MJG** y dado que no me interesa el estado de la jarra pequeña utilizo el símbolo ( **_** ).

**2.** Otro estado posible a tomar en cuenta, es cuando se llena la jarra pequeña; y esta regla se define de la siguiente manera:
```prolog
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , MJP):- CJP >= 0, CJP < MJP, CJP1 is MJP.
```
La explicación de este predicado es similiar a lo explicado anteriromente cuando se llenó la jarra grande.

**3 y 4.** Los siguientes estados posibles son, cuando se vacían las jarras. Sólo se puede vaciar una de las jarras si esta contiene agua y para vaciar no se requiere saber la capacidad de las jarras.
```prolog
posible(estado(CJG, CJP), estado(CJG1, CJP), _ , _ ):- CJG > 0, CJG1 is 0.
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , _ ):- CJP > 0, CJP1 is 0.
```
**5 y 6.** Aún quedan 2 posibles estados más, estos son cuando se vierte el agua de la jarra grande en la pequeña y la cantidad de agua de la jarra grande es menor o mayor a la cantidad de agua faltante para llenar la jarra pequeña, esta se define así:
```prolog
posible(estado(CJG, CJP), estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG =< (MJP - CJP), CJG1 is 0, CJP1 is CJP + CJG.
posible(estado(CJG, CJP),  estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG > (MJP - CJP), CJG1 is CJG - (MJP - CJP), CJP1 is MJP.
```
En el predicado anterior se aprecia que cambian los estados de las 2 jarras, ya que al pasar agua de una jarra hacia el otro, los dos estados se ven afectados, por eso la expresión **estado(CJG, CJP), estado(CJG1, CJP1)**, y dado que se se pasa agua desde el recipiente grande a la pequeña es necesario saber la capacidad de la jarra pequeña (**MJP**), como la capacidad de la jarra grande no me interesa en estos 2 casos utilizo el símbolo ( **_** ).

Al pasar agua de la jarra grande a la pequeña hay que tener en cuenta 2 posibles casos, estas son cuando la cantidad de agua a pasar  es menor, igual (**CJG =< (MJP - CJP)**) o mayor (**CJG > (MJP - CJP)**) a la cantidad de agua faltante para llenar la jarra pequeña. 

En el primer caso, la jarra grande queda vacía (**CJG1 is 0**) y la jarra pequeña queda con la cantidad de agua que ya tenía más la cantidad que se vierte desde la jarra grande (**CJP1 is CJP + CJG**).

En el segundo caso, la jarra grande queda con la cantidad de agua que tenía inicialmente menos la cantidad de agua faltante para llenar la jarra pequeña (**CJG - (MJP - CJP)**), lo cual significa que la jarra pequeña queda llena.
Todo esto se cumple si la jarra grande no esta vacía (**CJG > 0**).

**7 y 8.**  Las 2 últimas reglas a definir son cuando se vierte agua de la jarra pequeña en la grande y la cantidad de agua de la jarra pequeña es menor, igual o mayor a la cantidad de agua faltante para llenar la jarra grande (similar a las reglas 5 y 6), esta se define así: 
```prolog
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP =< (MJG - CJG), CJP1 is 0, CJG1 is CJG + CJP .
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP > (MJG - CJG), CJP1 is CJP - (MJG - CJG), CJG1 is MJG.
```
La explicación de la 2 expresiones anteriores son similares a las reglas 5 y 6, con la diferencia, de que es necesario saber la capacidad del recipiente grande (**MJG**) para determinar la cantidad de agua faltante en dicho recipiente.

###Lista de estados
La solución al acertijo es una lista de estados (los que fueron analizados anteriormente) y es conveniente determinar que no existan estados repetidos, por tanto hay que verificar si un elemento pertenece a una [lista](http://www.exa.unicen.edu.ar/catedras/prog_exp/apuntes/clase3.pdf), en **Prolog** se define de la siguiente manera:
```prolog
miembro(X, [X | _ ]).
miembro(X, [ _ | L ]) :- miembro(X, L).
```
###Solución
A continuación, se define la solución a este acertijo:

**E** = cabeza de la lista    **L** = cola de la lista
```prolog
solucion([E | L], [E | L], MJG, MJP) :- meta(E).
```
El predicado anterior, la solución base (*definida con el mismo nombre sin acento*) recibe 4 parámetros, los 2 primeros valores son listas y deben ser iguales (***[E | L], [E | L]***), mismas que se dividen en cabeza y cola (***[E | L]***), los 2 últimos valores son la capacidad de las jarras. En resúmen, hay solución, si es la meta que estoy buscando; la meta recibe la cabeza de la lista el cual es un estado y anteriormente ya se definió el hecho de la meta deseada para que sea solución **meta(estado(4, _ ))**, en el caso que la solución base no se cumpla  se define lo siguiente:
```prolog
solucion([E | L], LS, MJG, MJP) :- posible(E, EP, MJG, MJP), not(miembro(EP, L)), solucion([EP, E | L], LS, MJG, MJP).
```
El predicado anterior define otra regla que obtiene la lista de estados posibles hasta llegar a la solución base, la solución recibe 4 valores, los 2 primero valores son listas, la primera lista es la lista de estados posibles (*dividido en cabeza y cola*) y la misma será almacenada en la segunda lista que es la lista solución (***[E | L], LS***).

En el cuerpo de la regla se verifica que a partir del último estado posible (*cabeza de la lista*) exista un nuevo estado posible **posible(E, EP, MJG, MJP)**, además el nuevo estado posible no debe estar repetido en la lista de estados posibles **not(miembro(EP, L))**, en cuanto se cumpla estas 2 condiciones se llama una vez más al predicado **solucion**, pero en esta ocación se agrega el nuevo estado a la lista de estados (***[EP, E | L]***), esto se repetirá hasta que se encuentre la **meta**.

Para ejecutar el programa en ***SWI-Prolog***,  se lo hace de la siguiente manera:
```prolog
solucion([estado(0, 0)], L, 5, 3).
```
Al predicado solución se le envía la lista de estados, va empezar solo con un elemento (**[estado(0, 0)]**) en la lista de estados posibles, la variable donde se almacenarán dichos estados (***L***) y la capacidad de la jarra grande (5) y pequeña (3) respectivamente.

La salida es la siguiente (*se mostrarán varias listas de diferentes soluciones*):
```prolog
L = [estado(4, 0), estado(1, 3), estado(1, 0), estado(0, 1), estado(5, 1), estado(3, 3), estado(3, 0), estado(0, 3), estado(..., ...)|...] ;
L = [estado(4, 3), estado(4, 0), estado(1, 3), estado(1, 0), estado(0, 1), estado(5, 1), estado(3, 3), estado(3, 0), estado(..., ...)|...] ;
L = [estado(4, 3), estado(5, 2), estado(0, 2), estado(2, 0), estado(2, 3), estado(5, 0), estado(0, 0)] ;
...
```
A continuación se muestra todo el código:
```prolog
meta(estado(4, _ )) .
posible(estado(CJG, CJP), estado(CJG1, CJP), MJG, _) :- CJG >= 0, CJG < MJG, CJG1 is MJG .
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , MJP):- CJP >= 0, CJP < MJP, CJP1 is MJP. 
posible(estado(CJG, CJP), estado(CJG1, CJP), _ , _ ):- CJG > 0, CJG1 is 0.
posible(estado(CJG, CJP), estado(CJG, CJP1), _ , _ ):- CJP > 0, CJP1 is 0. 
posible(estado(CJG, CJP), estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG =< (MJP - CJP), CJG1 is 0, CJP1 is CJP + CJG.
posible(estado(CJG, CJP),  estado(CJG1, CJP1), _ , MJP):- CJG > 0, CJP < MJP, CJG > (MJP - CJP), CJG1 is CJG - (MJP - CJP), CJP1 is MJP. 
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP =< (MJG - CJG), CJP1 is 0, CJG1 is CJG + CJP .
posible(estado(CJG, CJP), estado(CJG1, CJP1), MJG, _ ):- CJP > 0, CJG < MJG, CJP > (MJG - CJG), CJP1 is CJP - (MJG - CJG), CJG1 is MJG. 

/*  Verifica si un elemento pertenece a una lista */
miembro(X, [X | _ ]).
miembro(X, [ _ | L ]) :- miembro(X, L). 

/*  Implementando solución */ 
solucion([E | L], [E | L], MJG, MJP) :- meta(E). 
solucion([E | L], LS, MJG, MJP) :- posible(E, EP, MJG, MJP), not(miembro(EP, L)), solucion([EP, E | L], LS, MJG, MJP). 
```
También pueden encontrar el mismo código en [GitHub](https://github.com/foqc/WaterJugRiddle).

Con esto concluimos, espero haber ayudado a entender mejor, la resolución del problema en Prolog, si tienen alguna pregunta no duden en escribirme.

*¡Gracias por su lectura!*