PeH

Recientemente, Justin Le ha publicado el artículo Wolf, goat, cabbage: The list MonadPlus & logic problems en el que explica cómo se pueden usar las mónadas para resolver el problema del granjero, el lobo, la oveja y la col. El enunciado de dicho problema es el siguiente

Un granjero fue al mercado y compró un lobo, una oveja y una col. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras. Además, si el lobo se queda solo con la cabra se la come y si la cabra se queda sola con la col se la come.

El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta. ¿Cómo lo hizo?

A partir del artículo, he elaborado la siguiente relación de ejercicios (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell). En ella se incluyen soluciones sin usar mónadas y con mónadas (concretamente, los ejercicios 12, 15 y 17).

La relación de ejercicios y sus soluciones es la siguiente
Read More “El problema del granjero, la oveja y la col en Haskell”

El tres en raya es un juego entre dos jugadores que marcan los espacios de un tablero de 3×3 alternadamente. Un jugador gana si consigue tener una línea de tres de sus símbolos: la línea puede ser horizontal, vertical o diagonal.

El objetivo de esta relación de ejercicos es realizar un programa para que la máquina juegue contra el humano el tres en raya usando la estrategia minimax.
Read More “El juego de “tres en raya” en Haskell”

A veces es interesante evaluar expresiones en Haskell durante un tiempo limitado. Se puede conseguir usando la función timeout de la librería System.Timeout y la evaluate de la Control.Exception.

Vamos a mostrar su uso el siguiente ejemplo. En primer lugar, importamos las funciones

A continuación, definimos la función de Fibonacci

y la función acotada tal que (acotada t f x) calcula (f x) durante t microsegundos (1/10^6 segundos) y devuelve (Just (f x)) si encuentra su valor o Nothing en caso contrario.

Con acotada podemos realizar evaluaciones con tiempo limitado. Por ejemplo,

También se puede acotar con evaluate. Por ejemplo,

Esta entrada se basa en la consulta Haskell time limit on evaluation de StackOverflow.

El problema de Josefo hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y cuarenta soldados camaradas fueron capturados por los romanos. Antes que rendirse, decidieron acabar ellos mismos con sus vidas. Para hacerlo, se dispusieron en un círculo y acordaron que irían contando de tres en tres, de forma que cada tercer soldado sería ejecutado por la persona de su izquierda. El último hombre que quedara con vida tendría que suicidarse. Según cuenta la leyenda, Josefo calculó rápidamente cuál sería la posición del último hombre en morir para colocarse allí, y una vez hubieron muerto sus compatriotas, se entregó a los romanos.

El enunciado del problema de Josefo de orden (n,m) es el siguiente: Se tienen n personas entorno a un círculo, ordenadas y numeradas desde la primera a la n-ésima. Empezando por la persona número 1, se saltan m-1 personas y se mata a la m-ésima. A continuación se saltan otras m-1 personas y se ejecuta a la siguiente. El proceso continúa hasta que sólo quede una. El objetivo es, dados n y m, encontrar el lugar inicial en el círculo para sobrevivir.

A continuación muestro una relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) en la que se presentan distintas soluciones y se compara su eficiencia.

Read More “El problema de Josefo en Haskell”