I1M2011: Los problemas de las N reinas y de Hamming en Haskell
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos vistos dos aplicaciones de la programación funcional en Haskell: el problema de las reinas (consistente en colocar N reinas en un tablero de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal) y el problema de Hamming (consistente definir una sucesión estrictamente creciente de números tales que el número 1 está en la sucesión y que, si x está en la sucesión, entonces 2*x, 3*x y 5*x también están).
El código del problema de las N reinas es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
-- --------------------------------------------------------------------- -- § Enunciado -- -- --------------------------------------------------------------------- -- Colocar N reinas en un tablero rectangular de dimensiones N por N de -- forma que no se encuentren más de una en la misma línea: horizontal, -- vertical o diagonal. -- --------------------------------------------------------------------- -- § Librerias auxiliares -- -- --------------------------------------------------------------------- import Data.List ((\\)) -- El tablero se representa por una lista de números que indican las -- filas donde se han colocado las reinas. Por ejemplo, [3,5] -- indica que se han colocado las reinas (1,3) y (2,5). type Tablero = [Int] -- (reinas n) es la lista de soluciones del problema de las N -- reinas. Por ejemplo, -- reinas 4 == [[3,1,4,2],[2,4,1,3]]. -- La primera solución [3,1,4,2] se interpreta como -- +---------------+ -- | | R | | | -- +---------------+ -- | | | | R | -- +---------------+ -- | R | | | | -- +---------------+ -- | | | R | | -- +---------------+ reinas :: Int -> [Tablero] reinas n = aux n where aux 0 = [[]] aux m = [r:rs | rs <- aux (m-1), r <- ([1..n] \\ rs), noAtaca r rs 1] -- (noAtaca r rs d) se verifica si la reina r no ataca a niguna de las -- de la lista rs donde la primera de la lista está a una distancia -- horizontal d. noAtaca :: Int -> Tablero -> Int -> Bool noAtaca _ [] _ = True noAtaca r (a:rs) distH = abs(r-a) /= distH && noAtaca r rs (distH+1) |
El código del problema de Hamming es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
-- Los números de Hamming forman una sucesión estrictamente creciente de -- números que cumplen las siguientes condiciones: -- * El número 1 está en la sucesión. -- * Si x está en la sucesión, entonces 2x, 3x y 5x también están. -- * Ningún otro número está en la sucesión. -- hamming es la sucesión de Hamming. Por ejemplo, -- take 12 hamming == [1,2,3,4,5,6,8,9,10,12,15,16] hamming :: [Int] hamming = 1 : mezcla3 [2*i | i <- hamming] [3*i | i <- hamming] [5*i | i <- hamming] -- (mezcla3 xs ys zs) es la lista obtenida mezclando las listas -- ordenadas xs, ys y zs y eliminando los elementos duplicados. Por -- ejemplo, -- ghci> mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10] -- [2,3,4,5,6,8,9,10,12] mezcla3 :: [Int] -> [Int] -> [Int] -> [Int] mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs) -- (mezcla2 xs ys zs) es la lista obtenida mezclando las listas -- ordenadas xs e ys y eliminando los elementos duplicados. Por ejemplo, -- ghci> mezcla2 [2,4,6,8,10,12] [3,6,9,12] -- [2,3,4,6,8,9,10,12] mezcla2 :: [Int] -> [Int] -> [Int] mezcla2 p@(x:xs) q@(y:ys) | x < y = x:mezcla2 xs q | x > y = y:mezcla2 p ys | otherwise = x:mezcla2 xs ys mezcla2 [] ys = ys mezcla2 xs [] = xs |
Las transparencias usadas en la clase son desde la página 37 a la 45 del tema 11: