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
|
1 2 |
import System.Timeout (timeout) import Control.Exception (evaluate) |
A continuación, definimos la función de Fibonacci
|
1 2 3 4 |
fib :: Int -> Int fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2) |
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.
|
1 2 |
acotada :: Int -> (a -> b) -> a -> IO (Maybe b) acotada t f x = timeout t (return $! f x) |
Con acotada podemos realizar evaluaciones con tiempo limitado. Por ejemplo,
|
1 2 3 4 5 6 |
ghci> acotada 100 fib 5 Just 8 ghci> acotada 100 fib 20 Nothing ghci> acotada (10^5) fib 20 Just 10946 |
También se puede acotar con evaluate. Por ejemplo,
|
1 2 3 4 5 6 |
ghci> timeout 100 $ evaluate (fib 5) Just 8 ghci> timeout 100 $ evaluate (fib 20) Nothing ghci> timeout (10^5) $ evaluate (fib 20) Just 10946 |
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.
He publicado una actualización del libro Exámenes de programación funcional con Haskell (2009-2014) en el que recopilo los exámenes de la asignatura de Informática (de primero del Grado en Matemáticas) desde el curso 2009-10 hasta el actual. El libro contiene 81 exámenes y 539 ejercicios.
Este libro es el complemento de los anteriores:
En las Olimpiadas de Matemáticas del 2001 se propuso el siguiente problema
Buscar todas las sucesiones finitas (x(0), x(1),…,x(n)) tales que para todo j, 0 ≤ j ≤ n, x(j) es igual al número de veces que aparece j en la sucesión.
Las sucesiones que cumplen la anterior condición se llaman auto descriptivas. Un ejemplo de sucesión auto descriptiva es [5,2,1,0,0,1,0,0,0] ya que
En la siguiente 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, se resuelve el problema con Haskell.
Read More “Sucesiones auto descriptivas en Haskell”