Menu Close

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

-- ---------------------------------------------------------------------
-- § 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

-- 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:

Sin categoría