Orden superior | Exercitium

Caminos reducidos

José A. Alonso-5-junio-2020-Medio-4 Comentarios

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

   data Direccion = N | S | E | O deriving (Show, Eq)
   type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

   reducido []                              ==  []
   reducido [N]                             ==  [N]
   reducido [N,O]                           ==  [N,O]
   reducido [N,O,E]                         ==  [N]
   reducido [N,O,E,S]                       ==  [] 
   reducido [N,O,S,E]                       ==  [N,O,S,E]
   reducido [S,S,S,N,N,N]                   ==  []
   reducido [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

       [N,S,S,E,O,N,O]  
   --> [S,E,O,N,O]  
   --> [S,N,O]  
   --> [O]

Soluciones

data Direccion = N | S | E | O deriving (Show, Eq)
 
type Camino = [Direccion]
 
-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido1 ds
 
opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E
 
-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
    where aux N (S:xs) = xs
          aux S (N:xs) = xs
          aux E (O:xs) = xs
          aux O (E:xs) = xs
          aux x xs     = x:xs
 
-- 3ª solución 
reducido3 :: Camino -> Camino
reducido3 []       = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido3 ds
 
-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where 
    aux (N:xs, S:ys) = aux (xs,ys)
    aux (S:xs, N:ys) = aux (xs,ys)
    aux (E:xs, O:ys) = aux (xs,ys)
    aux (O:xs, E:ys) = aux (xs,ys)
    aux (  xs, y:ys) = aux (y:xs,ys)
    aux (  xs,   []) = xs
 
-- Comparación de eficiencia
--    ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (3.87 secs, 460160736 bytes)
--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (1.16 secs, 216582880 bytes)
--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.58 secs, 98561872 bytes)
--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.64 secs, 176154640 bytes)
--    
--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (5.43 secs, 962694784 bytes)
--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (9.29 secs, 1722601528 bytes)
-- 
--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (4.52 secs, 547004960 bytes)
--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    
--    ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)
--    []
--    (7.35 secs, 537797096 bytes)
--    ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)
--    []
--    (2.30 secs, 244553404 bytes)
--    ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)
--    []
--    (8.08 secs, 545043608 bytes)
--    ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)
--    []
--    (1.96 secs, 205552240 bytes)

data Direccion = N | S | E | O deriving (Show, Eq) type Camino = [Direccion] -- 1ª solución (por recursión): reducido1 :: Camino -> Camino reducido1 [] = [] reducido1 (d:ds) | null ds' = [d] | d == opuesta (head ds') = tail ds' | otherwise = d:ds' where ds' = reducido1 ds opuesta :: Direccion -> Direccion opuesta N = S opuesta S = N opuesta E = O opuesta O = E -- 2ª solución (por plegado) reducido2 :: Camino -> Camino reducido2 = foldr aux [] where aux N (S:xs) = xs aux S (N:xs) = xs aux E (O:xs) = xs aux O (E:xs) = xs aux x xs = x:xs -- 3ª solución reducido3 :: Camino -> Camino reducido3 [] = [] reducido3 (N:S:ds) = reducido3 ds reducido3 (S:N:ds) = reducido3 ds reducido3 (E:O:ds) = reducido3 ds reducido3 (O:E:ds) = reducido3 ds reducido3 (d:ds) | null ds' = [d] | d == opuesta (head ds') = tail ds' | otherwise = d:ds' where ds' = reducido3 ds -- 4ª solución reducido4 :: Camino -> Camino reducido4 ds = reverse (aux ([],ds)) where aux (N:xs, S:ys) = aux (xs,ys) aux (S:xs, N:ys) = aux (xs,ys) aux (E:xs, O:ys) = aux (xs,ys) aux (O:xs, E:ys) = aux (xs,ys) aux ( xs, y:ys) = aux (y:xs,ys) aux ( xs, []) = xs -- Comparación de eficiencia -- ghci> reducido1 (take (10^6) (cycle [N,E,O,S])) -- [] -- (3.87 secs, 460160736 bytes) -- ghci> reducido2 (take (10^6) (cycle [N,E,O,S])) -- [] -- (1.16 secs, 216582880 bytes) -- ghci> reducido3 (take (10^6) (cycle [N,E,O,S])) -- [] -- (0.58 secs, 98561872 bytes) -- ghci> reducido4 (take (10^6) (cycle [N,E,O,S])) -- [] -- (0.64 secs, 176154640 bytes) -- -- ghci> reducido3 (take (10^7) (cycle [N,E,O,S])) -- [] -- (5.43 secs, 962694784 bytes) -- ghci> reducido4 (take (10^7) (cycle [N,E,O,S])) -- [] -- (9.29 secs, 1722601528 bytes) -- -- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S]) -- 400002 -- (4.52 secs, 547004960 bytes) -- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S]) -- 400002 -- -- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S) -- [] -- (7.35 secs, 537797096 bytes) -- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S) -- [] -- (2.30 secs, 244553404 bytes) -- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S) -- [] -- (8.08 secs, 545043608 bytes) -- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S) -- [] -- (1.96 secs, 205552240 bytes)

Seguir leyendo →

Número como suma de sus dígitos

José A. Alonso-3-junio-2020-Inicial-2 Comentarios

El número 23 se puede escribir de 4 formas como suma de sus dígitos

   2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
   2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
   2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
   2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

   minimoSumandosDigitos        :: Integer -> Integer
   graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

(minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,

     minimoSumandosDigitos 23    ==  8
     minimoSumandosDigitos 232   ==  78
     minimoSumandosDigitos 2323  ==  775
     map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

(graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Soluciones

import Test.QuickCheck
import Graphics.Gnuplot.Simple
import Data.List (nub, genericLength, sort)
import Data.Array (array, (!))
 
minimoSumandosDigitos :: Integer -> Integer
minimoSumandosDigitos n =
  minimoSumandos (digitos n) n
 
-- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo,
--    digitos 2032  ==  [2,3]
digitos :: Integer -> [Integer]
digitos n =
  nub [read [c] | c <- show n, c /= '0']
 
-- (minimoSumandos xs n) es el menor número de elementos de la lista de
-- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por
-- ejemplo, 
--    minimoSumandos [7,2,4] 11  ==  2
minimoSumandos :: [Integer] -> Integer -> Integer
minimoSumandos xs n =
  minimum (map genericLength (sumas xs n))
 
-- (sumas xs n) es la lista de elementos de la lista de enteros
-- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo,  
--    sumas [7,2,4] 11  ==  [[7,2,2],[7,4]]
sumas :: [Integer] -> Integer -> [[Integer]]
sumas [] 0 = [[]]
sumas [] _ = []
sumas (x:xs) n
  | x <= n    = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n
  | otherwise = sumas xs n
 
-- 2ª solución
-- ===========
 
minimoSumandosDigitos2 :: Integer -> Integer
minimoSumandosDigitos2 n = aux n 
  where
    aux 0 = 0
    aux k = 1 + minimo [aux (k - x) | x <- ds,  k >= x]
    ds    = digitos n
    infinito = 10^100
    minimo xs | null xs   = infinito
              | otherwise = minimum xs
 
-- 3ª solución
-- ===========
 
minimoSumandosDigitos3 :: Integer -> Integer
minimoSumandosDigitos3 n = v ! n
  where
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = 1 + minimo [v ! (k - x) | x <- ds, k >= x]
    ds       = digitos n
    infinito = 10^100
    minimo xs | null xs   = infinito
              | otherwise = minimum xs
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_minimoSumandosDigitos :: Positive Integer -> Bool
prop_minimoSumandosDigitos (Positive n) =
  r1 == r2 && r2 == r3
  where
    r1 = minimoSumandosDigitos n
    r2 = minimoSumandosDigitos n
    r3 = minimoSumandosDigitos n
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=9}) prop_minimoSumandosDigitos
--    +++ OK, passed 100 tests.
 
-- Definición de graficaMinimoSumandosDigitos
-- ==========================================
 
graficaMinimoSumandosDigitos :: Integer -> IO ()
graficaMinimoSumandosDigitos n =
  plotList [ Key Nothing
           -- , PNG "Numero_como_suma_de_sus_digitos.png"
           ]
           [minimoSumandosDigitos k | k <- [0..n-1]]

import Test.QuickCheck import Graphics.Gnuplot.Simple import Data.List (nub, genericLength, sort) import Data.Array (array, (!)) minimoSumandosDigitos :: Integer -> Integer minimoSumandosDigitos n = minimoSumandos (digitos n) n -- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo, -- digitos 2032 == [2,3] digitos :: Integer -> [Integer] digitos n = nub [read [c] | c <- show n, c /= '0'] -- (minimoSumandos xs n) es el menor número de elementos de la lista de -- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por -- ejemplo, -- minimoSumandos [7,2,4] 11 == 2 minimoSumandos :: [Integer] -> Integer -> Integer minimoSumandos xs n = minimum (map genericLength (sumas xs n)) -- (sumas xs n) es la lista de elementos de la lista de enteros -- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo, -- sumas [7,2,4] 11 == [[7,2,2],[7,4]] sumas :: [Integer] -> Integer -> [[Integer]] sumas [] 0 = [[]] sumas [] _ = [] sumas (x:xs) n | x <= n = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n | otherwise = sumas xs n -- 2ª solución -- =========== minimoSumandosDigitos2 :: Integer -> Integer minimoSumandosDigitos2 n = aux n where aux 0 = 0 aux k = 1 + minimo [aux (k - x) | x <- ds, k >= x] ds = digitos n infinito = 10^100 minimo xs | null xs = infinito | otherwise = minimum xs -- 3ª solución -- =========== minimoSumandosDigitos3 :: Integer -> Integer minimoSumandosDigitos3 n = v ! n where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = 1 + minimo [v ! (k - x) | x <- ds, k >= x] ds = digitos n infinito = 10^100 minimo xs | null xs = infinito | otherwise = minimum xs -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_minimoSumandosDigitos :: Positive Integer -> Bool prop_minimoSumandosDigitos (Positive n) = r1 == r2 && r2 == r3 where r1 = minimoSumandosDigitos n r2 = minimoSumandosDigitos n r3 = minimoSumandosDigitos n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=9}) prop_minimoSumandosDigitos -- +++ OK, passed 100 tests. -- Definición de graficaMinimoSumandosDigitos -- ========================================== graficaMinimoSumandosDigitos :: Integer -> IO () graficaMinimoSumandosDigitos n = plotList [ Key Nothing -- , PNG "Numero_como_suma_de_sus_digitos.png" ] [minimoSumandosDigitos k | k <- [0..n-1]]

Seguir leyendo →

Cambio con el menor número de monedas

José A. Alonso-2-junio-2020-Avanzado-2 Comentarios

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

   1, 1, 1, 1, 1, 1
   1, 1, 1, 3
   1, 1, 4
   3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

   monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

   monedas [1,3,4]  6                    ==  Just 2
   monedas [2,5,10] 3                    ==  Nothing
   monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

Soluciones

import Data.Array ((!), array)
 
-- 1ª solución
-- ===========
 
monedas :: [Int] -> Int -> Maybe Int
monedas ms x
  | null cs   = Nothing
  | otherwise = Just (minimum (map length cs))
  where cs = cambios ms x
 
-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas
-- de ms. Por ejemplo,
--   λ> cambios [1,5,10] 12
--   [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]
--   λ> cambios [2,5,10] 3
--   []
--   λ> cambios [1,3,4] 6
--   [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]
cambios :: [Int] -> Int -> [[Int]]
cambios _      0 = [[]]
cambios []     _ = []
cambios (k:ks) m
  | m < k     = []
  | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++
                cambios ks m
 
-- 2ª solución
-- ===========
 
monedas2 :: [Int] -> Int -> Maybe Int
monedas2 ms n
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = aux n
    aux 0 = 0
    aux k = siguiente (minimo [aux (k - x) | x <- ms,  k >= x])
 
infinito :: Int
infinito = 10^30
 
minimo :: [Int] -> Int
minimo [] = infinito
minimo xs = minimum xs
 
siguiente :: Int -> Int
siguiente x | x == infinito = infinito
            | otherwise     = 1 + x
 
-- 3ª solución
-- ===========
 
monedas3 :: [Int] -> Int -> Maybe Int
monedas3 ms n  
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = v ! n
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])
 
-- Comparación de eficiencia
-- =========================
 
--    λ> monedas [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.02 secs, 871,144 bytes)
--    λ> monedas2 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (15.44 secs, 1,866,519,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.01 secs, 157,232 bytes)
--    
--    λ> monedas [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (14.20 secs, 1,845,293,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (0.01 secs, 623,376 bytes)

import Data.Array ((!), array) -- 1ª solución -- =========== monedas :: [Int] -> Int -> Maybe Int monedas ms x | null cs = Nothing | otherwise = Just (minimum (map length cs)) where cs = cambios ms x -- (cambios ms x) es la lista de las foemas de obtener x sumando monedas -- de ms. Por ejemplo, -- λ> cambios [1,5,10] 12 -- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]] -- λ> cambios [2,5,10] 3 -- [] -- λ> cambios [1,3,4] 6 -- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]] cambios :: [Int] -> Int -> [[Int]] cambios _ 0 = [[]] cambios [] _ = [] cambios (k:ks) m | m < k = [] | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++ cambios ks m -- 2ª solución -- =========== monedas2 :: [Int] -> Int -> Maybe Int monedas2 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = aux n aux 0 = 0 aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x]) infinito :: Int infinito = 10^30 minimo :: [Int] -> Int minimo [] = infinito minimo xs = minimum xs siguiente :: Int -> Int siguiente x | x == infinito = infinito | otherwise = 1 + x -- 3ª solución -- =========== monedas3 :: [Int] -> Int -> Maybe Int monedas3 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = v ! n v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x]) -- Comparación de eficiencia -- ========================= -- λ> monedas [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.02 secs, 871,144 bytes) -- λ> monedas2 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (15.44 secs, 1,866,519,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.01 secs, 157,232 bytes) -- -- λ> monedas [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (14.20 secs, 1,845,293,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (0.01 secs, 623,376 bytes)

Seguir leyendo →

Operaciones con series de potencias

José A. Alonso-29-mayo-2020-Medio-5 Comentarios

Una serie de potencias es una serie de la forma

   a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

   e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

   type Serie a = [a]

Definir las siguientes funciones

   opuesta      :: Num a => Serie a -> Serie a
   suma         :: Num a => Serie a -> Serie a -> Serie a
   resta        :: Num a => Serie a -> Serie a -> Serie a
   producto     :: Num a => Serie a -> Serie a -> Serie a
   cociente     :: Fractional a => Serie a -> Serie a -> Serie a
   derivada     :: (Num a, Enum a) => Serie a -> Serie a
   integral     :: (Fractional a, Enum a) => Serie a -> Serie a
   expx         :: Serie Rational

tales que

(opuesta xs) es la opuesta de la serie xs. Por ejemplo,

     λ> take 7 (opuesta [-6,-4..])
     [6,4,2,0,-2,-4,-6]

(suma xs ys) es la suma de las series xs e ys. Por ejemplo,

     λ> take 7 (suma [1,3..] [2,4..])
     [3,7,11,15,19,23,27]

(resta xs ys) es la resta de las series xs es ys. Por ejemplo,

     λ> take 7 (resta [3,5..] [2,4..])
     [1,1,1,1,1,1,1]
     λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
     [2,4,6,8,10,12,14]

(producto xs ys) es el producto de las series xs e ys. Por ejemplo,

     λ> take 7 (producto [3,5..] [2,4..])
     [6,22,52,100,170,266,392]

(cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

     λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
     [2.0,4.0,6.0,8.0,10.0,12.0,14.0]

(derivada xs) es la derivada de la serie xs. Por ejemplo,

     λ> take 7 (derivada [2,4..])
     [4,12,24,40,60,84,112]

(integral xs) es la integral de la serie xs. Por ejemplo,

     λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
     [0.0,4.0,6.0,8.0,10.0,12.0,14.0]

expx es la serie de la función exponencial. Por ejemplo,

     λ> take 8 expx
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (derivada expx)
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (integral expx)
     [0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Soluciones

type Serie a = [a] 
 
opuesta :: Num a => Serie a -> Serie a
opuesta = map negate
 
suma :: Num a => Serie a -> Serie a -> Serie a
suma = zipWith (+)
 
resta :: Num a => Serie a -> Serie a -> Serie a
resta xs ys = suma xs (opuesta ys)
 
producto :: Num a => Serie a -> Serie a -> Serie a
producto (x:xs) zs@(y:ys) = 
    x*y : suma (producto xs zs) (map (x*) ys)
 
cociente :: Fractional a => Serie a -> Serie a -> Serie a
cociente (x:xs) (y:ys) = zs 
    where zs = x/y : map (/y) (resta xs (producto zs ys))  
 
derivada :: (Num a, Enum a) => Serie a -> Serie a
derivada (_:xs) = zipWith (*) xs [1..]
 
integral :: (Fractional a, Enum a) => Serie a -> Serie a
integral xs = 0 : zipWith (/) xs [1..]
 
expx :: Serie Rational
expx = map (1/) (map fromIntegral factoriales)
 
-- factoriales es la lista de los factoriales. Por ejemplo, 
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

Seguir leyendo →

Sucesión duplicadora

José A. Alonso-26-mayo-2020-Inicial-5 Comentarios

Para cada entero positivo n, existe una única sucesión que empieza en 1, termina en n y en la que cada uno de sus elementos es el doble de su anterior o el doble más uno. Dicha sucesión se llama la sucesión duplicadora de n. Por ejemplo, la sucesión duplicadora de 13 es [1, 3, 6, 13], ya que

    3 = 2*1 +1
    6 = 2*3
   13 = 2*6 +1

Definir la función

   duplicadora :: Integer -> [Integer]

tal que (duplicadora n) es la sucesión duplicadora de n. Por ejemplo,

   duplicadora 13                   ==  [1,3,6,13]
   duplicadora 17                   ==  [1,2,4,8,17]
   length (duplicadora (10^40000))  ==  132878

Soluciones

-- 1ª definición
duplicadora :: Integer -> [Integer]
duplicadora x =
  reverse (takeWhile (>=1) (iterate (`div` 2) x))
 
-- 2ª definición
duplicadora2 :: Integer -> [Integer]
duplicadora2  =
  reverse . takeWhile (>=1) . iterate (`div` 2)

Seguir leyendo →

Cadenas de primos complementarios

José A. Alonso-25-mayo-2020-Inicial-2 Comentarios

El complemento de un número positivo x se calcula por el siguiente procedimiento:

si x es mayor que 9, se toma cada dígito por su valor posicional y se resta del mayor los otro dígitos. Por ejemplo, el complemento de 1448 es 1000 – 400 – 40 – 8 = 552. Para
si x es menor que 10, su complemento es x.

Definir las funciones

   cadena    :: Integer -> [Integer]
   conCadena :: Int -> [Integer]

tales que

(cadena x) es la cadena de primos a partir de x tal que cada uno es el complemento del anterior. Por ejemplo,

     cadena 8         == []
     cadena 7         == [7]
     cadena 13        == [13,7]
     cadena 643       == [643,557,443]
     cadena 18127     == [18127,1873,127,73,67,53,47]
     cadena 18181213  == [18181213,1818787,181213,18787,1213,787,613,587]

(conCadena n) es la lista de números cuyas cadenas tienen n elementos. Por ejemplo,

     take 6 (conCadena 3)                == [23,31,61,67,103,307]
     [head (conCadena n) | n <- [4..8]]  == [37,43,157,18127,181873]

Soluciones

 
import Data.Numbers.Primes
 
-- (complemento x) es le complemento de x. Por ejemplo,
--    complemento 1448  == 552
--    complemento  639  == 561
--    complemento    7  == 7
complemento :: Integer -> Integer
complemento x = (div x c)*c - (rem x c)
  where c = 10^(length (show x) - 1)          
 
cadena :: Integer -> [Integer]
cadena x    
  | x < 10 && isPrime x = [x]
  | otherwise           = takeWhile isPrime (iterate f x)
  where f x | x < 10 && isPrime x = 0
            | otherwise           = complemento x
 
conCadena :: Int -> [Integer]
conCadena n =
  [y | y <- primes, length (cadena y) == n]

Seguir leyendo →

Las sucesiones de Loomis

José A. Alonso-22-mayo-2020-Medio-4 Comentarios

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

f(0) es x
f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, …
Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, …
Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, …

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

la generada por 2 converge a 2
la generada por 3 converge a 26
la generada por 4 converge a 4
la generada por 5 converge a 26

Definir las siguientes funciones

   sucLoomis           :: Integer -> [Integer]
   convergencia        :: Integer -> Integer
   graficaConvergencia :: [Integer] -> IO ()

tales que

(sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

     λ> take 15 (sucLoomis 1)
     [1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 2)
     [2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 3)
     [3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 4)
     [4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
     λ> take 15 (sucLoomis 5)
     [5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 20)
     [20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
     λ> take 15 (sucLoomis 100)
     [100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
     λ> sucLoomis 1 !! (2*10^5)
     235180736652

(convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

     convergencia  2      ==  2
     convergencia  3      ==  26
     convergencia  4      ==  4
     convergencia 17      ==  38
     convergencia 19      ==  102
     convergencia 43      ==  162
     convergencia 27      ==  202
     convergencia 58      ==  474
     convergencia 63      ==  150056
     convergencia 81      ==  150056
     convergencia 89      ==  150056
     convergencia (10^12) ==  1000101125092

(graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja

y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Soluciones

import Data.List               ((\\))
import Data.Char               (digitToInt)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG))
 
-- 1ª definición de sucLoomis
-- ==========================
 
sucLoomis :: Integer -> [Integer]
sucLoomis x = map (loomis x) [0..]
 
loomis :: Integer -> Integer -> Integer
loomis x 0 = x
loomis x n = y + productoDigitosNoNulos y
  where y = loomis x (n-1)
 
productoDigitosNoNulos :: Integer -> Integer
productoDigitosNoNulos = product . digitosNoNulos
 
digitosNoNulos :: Integer -> [Integer]
digitosNoNulos x =
  [read [c] | c <- show x, c /= '0']
 
-- 2ª definición de sucLoomis
-- ==========================
 
sucLoomis2 :: Integer -> [Integer]
sucLoomis2 = iterate siguienteLoomis 
 
siguienteLoomis :: Integer -> Integer
siguienteLoomis y = y + productoDigitosNoNulos y
 
-- 3ª definición de sucLoomis
-- ==========================
 
sucLoomis3 :: Integer -> [Integer]
sucLoomis3 =
  iterate ((+) <*> product .
           map (toInteger . digitToInt) .
           filter (/= '0') . show)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sucLoomis 1 !! 30000
--    6571272766
--    (2.45 secs, 987,955,944 bytes)
--    λ> sucLoomis2 1 !! 30000
--    6571272766
--    (2.26 secs, 979,543,328 bytes)
--    λ> sucLoomis3 1 !! 30000
--    6571272766
--    (0.31 secs, 88,323,832 bytes)
 
-- 1ª definición de convergencia
-- =============================
 
convergencia1 :: Integer -> Integer
convergencia1 x =
  head (dropWhile noEnSucLoomisDe1 (sucLoomis x))
 
noEnSucLoomisDe1 :: Integer -> Bool
noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1)
 
sucLoomisDe1 :: [Integer]
sucLoomisDe1 = sucLoomis 1
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- 2ª definición de convergencia
-- =============================
 
convergencia2 :: Integer -> Integer
convergencia2 = aux (sucLoomis3 1) . sucLoomis3
 where aux as@(x:xs) bs@(y:ys) | x == y    = x
                               | x < y     = aux xs bs
                               | otherwise = aux as ys
 
-- 3ª definición de convergencia
-- =============================
 
convergencia3 :: Integer -> Integer
convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3
 
-- (interseccion xs ys) es la intersección entre las listas ordenadas xs
-- e ys. Por ejemplo,
--    λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2))
--    [2,4,8,16,22,26,38,62,74,102]
interseccion :: Ord a => [a] -> [a] -> [a]
interseccion = aux
  where aux as@(x:xs) bs@(y:ys) = case compare x y of
                                    LT ->     aux xs bs
                                    EQ -> x : aux xs ys
                                    GT ->     aux as ys
        aux _         _         = []                           
 
-- 4ª definición de convergencia
-- =============================
 
convergencia4 :: Integer -> Integer
convergencia4 x = perteneceA (sucLoomis3 x) 1
  where perteneceA (y:ys) n | y == c    = y
                            | otherwise = perteneceA ys c
          where c = head $ dropWhile (< y) $ sucLoomis3 n
 
-- Comparación de eficiencia
-- =========================
 
--    λ> convergencia1 (10^4)
--    150056
--    (2.94 secs, 1,260,809,808 bytes)
--    λ> convergencia2 (10^4)
--    150056
--    (0.03 secs, 700,240 bytes)
--    λ> convergencia3 (10^4)
--    150056
--    (0.03 secs, 1,165,496 bytes)
--    λ> convergencia4 (10^4)
--    150056
--    (0.02 secs, 1,119,648 bytes)
--    
--    λ> convergencia2 (10^12)
--    1000101125092
--    (1.81 secs, 714,901,080 bytes)
--    λ> convergencia3 (10^12)
--    1000101125092
--    (1.92 secs, 744,932,184 bytes)
--    λ> convergencia4 (10^12)
--    1000101125092
--    (1.82 secs, 941,053,328 bytes)
 
-- Definición de graficaConvergencia
-- ==================================
 
graficaConvergencia :: [Integer] -> IO ()
graficaConvergencia xs =
  plotList [ Key Nothing
           , Title "Convergencia de sucesiones de Loomis"
           , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs))
           , PNG "Las_sucesiones_de_Loomis_2.png"
           ]
           [(x,convergencia2 x) | x <- xs]

import Data.List ((\\)) import Data.Char (digitToInt) import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG)) -- 1ª definición de sucLoomis -- ========================== sucLoomis :: Integer -> [Integer] sucLoomis x = map (loomis x) [0..] loomis :: Integer -> Integer -> Integer loomis x 0 = x loomis x n = y + productoDigitosNoNulos y where y = loomis x (n-1) productoDigitosNoNulos :: Integer -> Integer productoDigitosNoNulos = product . digitosNoNulos digitosNoNulos :: Integer -> [Integer] digitosNoNulos x = [read [c] | c <- show x, c /= '0'] -- 2ª definición de sucLoomis -- ========================== sucLoomis2 :: Integer -> [Integer] sucLoomis2 = iterate siguienteLoomis siguienteLoomis :: Integer -> Integer siguienteLoomis y = y + productoDigitosNoNulos y -- 3ª definición de sucLoomis -- ========================== sucLoomis3 :: Integer -> [Integer] sucLoomis3 = iterate ((+) <*> product . map (toInteger . digitToInt) . filter (/= '0') . show) -- Comparación de eficiencia -- ========================= -- λ> sucLoomis 1 !! 30000 -- 6571272766 -- (2.45 secs, 987,955,944 bytes) -- λ> sucLoomis2 1 !! 30000 -- 6571272766 -- (2.26 secs, 979,543,328 bytes) -- λ> sucLoomis3 1 !! 30000 -- 6571272766 -- (0.31 secs, 88,323,832 bytes) -- 1ª definición de convergencia -- ============================= convergencia1 :: Integer -> Integer convergencia1 x = head (dropWhile noEnSucLoomisDe1 (sucLoomis x)) noEnSucLoomisDe1 :: Integer -> Bool noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1) sucLoomisDe1 :: [Integer] sucLoomisDe1 = sucLoomis 1 pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (<x) ys) -- 2ª definición de convergencia -- ============================= convergencia2 :: Integer -> Integer convergencia2 = aux (sucLoomis3 1) . sucLoomis3 where aux as@(x:xs) bs@(y:ys) | x == y = x | x < y = aux xs bs | otherwise = aux as ys -- 3ª definición de convergencia -- ============================= convergencia3 :: Integer -> Integer convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3 -- (interseccion xs ys) es la intersección entre las listas ordenadas xs -- e ys. Por ejemplo, -- λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2)) -- [2,4,8,16,22,26,38,62,74,102] interseccion :: Ord a => [a] -> [a] -> [a] interseccion = aux where aux as@(x:xs) bs@(y:ys) = case compare x y of LT -> aux xs bs EQ -> x : aux xs ys GT -> aux as ys aux _ _ = [] -- 4ª definición de convergencia -- ============================= convergencia4 :: Integer -> Integer convergencia4 x = perteneceA (sucLoomis3 x) 1 where perteneceA (y:ys) n | y == c = y | otherwise = perteneceA ys c where c = head $ dropWhile (< y) $ sucLoomis3 n -- Comparación de eficiencia -- ========================= -- λ> convergencia1 (10^4) -- 150056 -- (2.94 secs, 1,260,809,808 bytes) -- λ> convergencia2 (10^4) -- 150056 -- (0.03 secs, 700,240 bytes) -- λ> convergencia3 (10^4) -- 150056 -- (0.03 secs, 1,165,496 bytes) -- λ> convergencia4 (10^4) -- 150056 -- (0.02 secs, 1,119,648 bytes) -- -- λ> convergencia2 (10^12) -- 1000101125092 -- (1.81 secs, 714,901,080 bytes) -- λ> convergencia3 (10^12) -- 1000101125092 -- (1.92 secs, 744,932,184 bytes) -- λ> convergencia4 (10^12) -- 1000101125092 -- (1.82 secs, 941,053,328 bytes) -- Definición de graficaConvergencia -- ================================== graficaConvergencia :: [Integer] -> IO () graficaConvergencia xs = plotList [ Key Nothing , Title "Convergencia de sucesiones de Loomis" , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs)) , PNG "Las_sucesiones_de_Loomis_2.png" ] [(x,convergencia2 x) | x <- xs]

Seguir leyendo →

Espacio de estados del problema de las N reinas

José A. Alonso-21-mayo-2020-Avanzado-1 Comentario

El problema de las N reinas consiste en colocar N reinas en 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. Por ejemplo, una solución para el problema de las 4 reinas es

   |---|---|---|---|
   |   | R |   |   |
   |---|---|---|---|
   |   |   |   | R |
   |---|---|---|---|
   | R |   |   |   |
   |---|---|---|---|
   |   |   | R |   |
   |---|---|---|---|

Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.

Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].

Usando la librería de árboles Data.Tree, definir las funciones

   arbolReinas :: Int -> Tree [Int]
   nEstados    :: Int -> Int
   soluciones  :: Int -> [[Int]]
   nSoluciones :: Int -> Int

tales que

(arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbolReinas 4)))
     []
     |
     +- [1]
     |  |
     |  +- [3,1]
     |  |
     |  `- [4,1]
     |     |
     |     `- [2,4,1]
     |
     +- [2]
     |  |
     |  `- [4,2]
     |     |
     |     `- [1,4,2]
     |        |
     |        `- [3,1,4,2]
     |
     +- [3]
     |  |
     |  `- [1,3]
     |     |
     |     `- [4,1,3]
     |        |
     |        `- [2,4,1,3]
     |
     `- [4]
        |
        +- [1,4]
        |  |
        |  `- [3,1,4]
        |
        `- [2,4]
 
     λ> putStrLn (drawTree (fmap show (arbolReinas 5)))
     []
     |
     +- [1]
     |  |
     |  +- [3,1]
     |  |  |
     |  |  `- [5,3,1]
     |  |     |
     |  |     `- [2,5,3,1]
     |  |        |
     |  |        `- [4,2,5,3,1]
     |  |
     |  +- [4,1]
     |  |  |
     |  |  `- [2,4,1]
     |  |     |
     |  |     `- [5,2,4,1]
     |  |        |
     |  |        `- [3,5,2,4,1]
     |  |
     |  `- [5,1]
     |     |
     |     `- [2,5,1]
     |
     +- [2]
     |  |
     |  +- [4,2]
     |  |  |
     |  |  `- [1,4,2]
     |  |     |
     |  |     `- [3,1,4,2]
     |  |        |
     |  |        `- [5,3,1,4,2]
     |  |
     |  `- [5,2]
     |     |
     |     +- [1,5,2]
     |     |  |
     |     |  `- [4,1,5,2]
     |     |
     |     `- [3,5,2]
     |        |
     |        `- [1,3,5,2]
     |           |
     |           `- [4,1,3,5,2]
     |
     +- [3]
     |  |
     |  +- [1,3]
     |  |  |
     |  |  `- [4,1,3]
     |  |     |
     |  |     `- [2,4,1,3]
     |  |        |
     |  |        `- [5,2,4,1,3]
     |  |
     |  `- [5,3]
     |     |
     |     `- [2,5,3]
     |        |
     |        `- [4,2,5,3]
     |           |
     |           `- [1,4,2,5,3]
     |
     +- [4]
     |  |
     |  +- [1,4]
     |  |  |
     |  |  +- [3,1,4]
     |  |  |  |
     |  |  |  `- [5,3,1,4]
     |  |  |     |
     |  |  |     `- [2,5,3,1,4]
     |  |  |
     |  |  `- [5,1,4]
     |  |     |
     |  |     `- [2,5,1,4]
     |  |
     |  `- [2,4]
     |     |
     |     `- [5,2,4]
     |        |
     |        `- [3,5,2,4]
     |           |
     |           `- [1,3,5,2,4]
     |
     `- [5]
        |
        +- [1,5]
        |  |
        |  `- [4,1,5]
        |
        +- [2,5]
        |  |
        |  `- [4,2,5]
        |     |
        |     `- [1,4,2,5]
        |        |
        |        `- [3,1,4,2,5]
        |
        `- [3,5]
           |
           `- [1,3,5]
              |
              `- [4,1,3,5]
                 |
                 `- [2,4,1,3,5]

λ> putStrLn (drawTree (fmap show (arbolReinas 4))) [] | +- [1] | | | +- [3,1] | | | `- [4,1] | | | `- [2,4,1] | +- [2] | | | `- [4,2] | | | `- [1,4,2] | | | `- [3,1,4,2] | +- [3] | | | `- [1,3] | | | `- [4,1,3] | | | `- [2,4,1,3] | `- [4] | +- [1,4] | | | `- [3,1,4] | `- [2,4] λ> putStrLn (drawTree (fmap show (arbolReinas 5))) [] | +- [1] | | | +- [3,1] | | | | | `- [5,3,1] | | | | | `- [2,5,3,1] | | | | | `- [4,2,5,3,1] | | | +- [4,1] | | | | | `- [2,4,1] | | | | | `- [5,2,4,1] | | | | | `- [3,5,2,4,1] | | | `- [5,1] | | | `- [2,5,1] | +- [2] | | | +- [4,2] | | | | | `- [1,4,2] | | | | | `- [3,1,4,2] | | | | | `- [5,3,1,4,2] | | | `- [5,2] | | | +- [1,5,2] | | | | | `- [4,1,5,2] | | | `- [3,5,2] | | | `- [1,3,5,2] | | | `- [4,1,3,5,2] | +- [3] | | | +- [1,3] | | | | | `- [4,1,3] | | | | | `- [2,4,1,3] | | | | | `- [5,2,4,1,3] | | | `- [5,3] | | | `- [2,5,3] | | | `- [4,2,5,3] | | | `- [1,4,2,5,3] | +- [4] | | | +- [1,4] | | | | | +- [3,1,4] | | | | | | | `- [5,3,1,4] | | | | | | | `- [2,5,3,1,4] | | | | | `- [5,1,4] | | | | | `- [2,5,1,4] | | | `- [2,4] | | | `- [5,2,4] | | | `- [3,5,2,4] | | | `- [1,3,5,2,4] | `- [5] | +- [1,5] | | | `- [4,1,5] | +- [2,5] | | | `- [4,2,5] | | | `- [1,4,2,5] | | | `- [3,1,4,2,5] | `- [3,5] | `- [1,3,5] | `- [4,1,3,5] | `- [2,4,1,3,5]

(nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,

     nEstados 4            ==  17
     nEstados 5            ==  54
     map nEstados [0..10]  ==  [1,2,3,6,17,54,153,552,2057,8394,35539]

(soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,

     λ> soluciones 4
     [[3,1,4,2],[2,4,1,3]]
     λ> soluciones 5
     [[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
      [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]

(nSoluciones n) es el número de soluciones del problema de las n reinas. Por ejemplo,

     nSoluciones 4            ==  2
     nSoluciones 5            ==  10
     map nSoluciones [0..10]  ==  [1,1,0,0,2,10,4,40,92,352,724]

Soluciones

import Data.List ((\\))
import Data.Tree
 
-- Definición de arbolReinas
-- =========================
 
arbolReinas :: Int -> Tree [Int]
arbolReinas n = expansion n []
  where
    expansion m xs = Node xs [expansion (m-1) ys | ys <- sucesores n xs]
 
-- (sucesores n xs) es la lista de los sucesores del estado xs en el
-- problema de las n reinas. Por ejemplo,
--    sucesores 4 []       ==  [[1],[2],[3],[4]]
--    sucesores 4 [1]      ==  [[3,1],[4,1]]
--    sucesores 4 [4,1]    ==  [[2,4,1]]
--    sucesores 4 [2,4,1]  ==  []
sucesores :: Int -> [Int] -> [[Int]]
sucesores n xs = [y:xs | y <- [1..n] \\ xs
                       , noAtaca y xs 1]
 
-- (noAtaca y xs d) se verifica si la reina en la fila y no ataca a las
-- colocadas en las filas xs donde d es el número de columnas desde la
-- de la posición de x a la primera de xs.
noAtaca :: Int -> [Int] -> Int -> Bool
noAtaca _ [] _ = True
noAtaca y (x:xs) distH = abs(y-x) /= distH &&
                         noAtaca y xs (distH + 1)               
 
-- Definición de nEstados
-- ======================
 
nEstados :: Int -> Int
nEstados = length . arbolReinas
 
-- Definición de solucionesReinas
-- ==============================
 
--    λ> soluciones 4
--    [[3,1,4,2],[2,4,1,3]]
--    λ> soluciones 5
--    [[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
--     [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]
soluciones :: Int -> [[Int]]
soluciones n =
  filter (\xs -> length xs == n) (estados n)
 
-- (estados n) es la lista de estados del problema de las n reinas. Por
-- ejemplo, 
--   λ> estados 4
--   [[],
--    [1],[2],[3],[4],
--    [3,1],[4,1],[4,2],[1,3],[1,4],[2,4],
--    [2,4,1],[1,4,2],[4,1,3],[3,1,4],
--    [3,1,4,2],[2,4,1,3]]
estados :: Int -> [[Int]]
estados = concat . levels . arbolReinas
 
-- Definición de nSoluciones
-- =========================
 
nSoluciones :: Int -> Int
nSoluciones = length . soluciones

Seguir leyendo →

Codificación de Fibonacci

José A. Alonso-20-mayo-2020-Avanzado-4 Comentarios

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)…d(k-1)d(k) de ceros y unos tal que

   n = d(0)*F(2) + d(1)*F(3) +...+ d(k-1)*F(k+1) 
   d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci.

   0,1,1,2,3,5,8,13,21,34,...

Por ejemplo. La codificación de Fibonacci de 4 es “1011” ya que los dos últimos elementos son iguales a 1 y

   1*F(2) + 0*F(3) + 1*F(4) = 1*1 + 0*2 + 1*3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

    1  = 1     = F(2)           ≡       11
    2  = 2     = F(3)           ≡      011
    3  = 3     = F(4)           ≡     0011
    4  = 1+3   = F(2)+F(4)      ≡     1011
    5  = 5     = F(5)           ≡    00011
    6  = 1+5   = F(2)+F(5)      ≡    10011
    7  = 2+5   = F(3)+F(5)      ≡    01011
    8  = 8     = F(6)           ≡   000011
    9  = 1+8   = F(2)+F(6)      ≡   100011
   10  = 2+8   = F(3)+F(6)      ≡   010011
   11  = 3+8   = F(4)+F(6)      ≡   001011
   12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
   13  = 13    = F(7)           ≡  0000011
   14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

   codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

   λ> codigoFib 65
   "0100100011"
   λ> [codigoFib n | n <- [1..7]]
   ["11","011","0011","1011","00011","10011","01011"]

Soluciones

import Data.List
import Data.Array
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
codigoFib1 :: Integer -> String
codigoFib1 = (concatMap show) . codificaFibLista
 
-- (codificaFibLista n) es la lista correspondiente a la codificación de
-- Fibonacci del número n. Por ejemplo,
--    λ> codificaFibLista 65
--    [0,1,0,0,1,0,0,0,1,1]
--    λ> [codificaFibLista n | n <- [1..7]]
--    [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]]
codificaFibLista :: Integer -> [Integer]
codificaFibLista n = map f [2..head xs] ++ [1]
  where xs = map fst (descomposicion n)
        f i | elem i xs = 1
            | otherwise = 0
 
-- (descomposicion n) es la lista de pares (i,f) tales que f es el
-- i-ésimo número de Fibonacci y las segundas componentes es una
-- sucesión decreciente de números de Fibonacci cuya suma es n. Por
-- ejemplo, 
--    descomposicion 65  ==  [(10,55),(6,8),(3,2)]
--    descomposicion 66  ==  [(10,55),(6,8),(4,3)]
descomposicion :: Integer -> [(Integer, Integer)]
descomposicion 0 = []
descomposicion 1 = [(2,1)]
descomposicion n = (i,x) : descomposicion (n-x)
  where (i,x) = fibAnterior n
 
-- (fibAnterior n) es el mayor número de Fibonacci menor o igual que
-- n. Por ejemplo,
--    fibAnterior 33  ==  (8,21)
--    fibAnterior 34  ==  (9,34)
fibAnterior :: Integer -> (Integer, Integer)
fibAnterior n = last (takeWhile p fibsConIndice)
  where p (i,x) = x <= n
 
-- fibsConIndice es la sucesión de los números de Fibonacci junto con
-- sus índices. Por ejemplo,
--    λ> take 10 fibsConIndice
--    [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21),(9,34)]
fibsConIndice :: [(Integer, Integer)]
fibsConIndice = zip [0..] fibs
 
-- fibs es la sucesión de Fibonacci. Por ejemplo, 
--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
--- 2ª solución
-- ============
 
codigoFib2 :: Integer -> String
codigoFib2 = (concatMap show) . elems . codificaFibVec
 
-- (codificaFibVec n) es el vector correspondiente a la codificación de
-- Fibonacci del número n. Por ejemplo,
--    λ> codificaFibVec 65
--    array (0,9) [(0,0),(1,1),(2,0),(3,0),(4,1),(5,0),(6,0),(7,0),(8,1),(9,1)]
--    λ> [elems (codificaFibVec n) | n <- [1..7]]
--    [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]]
codificaFibVec :: Integer -> Array Integer Integer
codificaFibVec n = accumArray (+) 0 (0,a+1) ((a+1,1):is) 
  where is = [(i-2,1) | (i,x) <- descomposicion n]
        a  = fst (head is)
 
-- Comparación de eficiencia
-- =========================
--    λ> head [n | n <- [1..], length (codigoFib1 n) > 25]
--    121393
--    (14.37 secs, 3135674112 bytes)
--    λ> :r
--    Ok, modules loaded: Main.
--    λ> head [n | n <- [1..], length (codigoFib2 n) > 25]
--    121393
--    (12.04 secs, 2762190920 bytes)
 
-- Propiedades
-- ===========
 
-- Usaremos la 2ª definición
codigoFib :: Integer -> String
codigoFib = codigoFib2
 
-- Prop.: La función descomposicion es correcta:
propDescomposicionCorrecta :: Integer -> Property
propDescomposicionCorrecta n =
  n >= 0 ==> n == sum (map snd (descomposicion n))
 
-- La comprobación es
--    λ> quickCheck propDescomposicionCorrecta
--    +++ OK, passed 100 tests.
 
-- Prop.: Todo número natural se puede descomponer en suma de números de
-- la sucesión de Fibonacci.
propDescomposicion :: Integer -> Property
propDescomposicion n =
  n >= 0 ==> not (null (descomposicion n))
 
-- La comprobación es
--    λ> quickCheck propDescomposicion
--    +++ OK, passed 100 tests.
 
-- Prop.: Las codificaciones de Fibonacci tienen como mínimo 2 elementos.
prop1 :: Integer -> Property
prop1 n = n > 0 ==> length (codigoFib n) >= 2
 
-- La comprobación es
--    λ> quickCheck prop1
--    +++ OK, passed 100 tests.
 
-- Prop.: Los dos últimos elementos de las codificaciones de Fibonacci
-- son iguales a 1.
prop2 :: Integer -> Property
prop2 n = n > 0 ==> take 2 (reverse (codigoFib n)) == "11"
 
-- La comprobación es
--    λ> quickCheck prop2
--    +++ OK, passed 100 tests.
 
-- Prop.: En las codificaciones de Fibonacci, la cadena "11" sólo
-- aparece una vez y la única vez que aparece es al final.
prop3 :: Integer -> Property
prop3 n = 
  n > 0 ==> not (isInfixOf "11" (drop 2 (reverse (codigoFib n))))
 
-- La comprobación es
--    λ> quickCheck prop3
--    +++ OK, passed 100 tests.

import Data.List import Data.Array import Test.QuickCheck -- 1ª solución -- =========== codigoFib1 :: Integer -> String codigoFib1 = (concatMap show) . codificaFibLista -- (codificaFibLista n) es la lista correspondiente a la codificación de -- Fibonacci del número n. Por ejemplo, -- λ> codificaFibLista 65 -- [0,1,0,0,1,0,0,0,1,1] -- λ> [codificaFibLista n | n <- [1..7]] -- [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]] codificaFibLista :: Integer -> [Integer] codificaFibLista n = map f [2..head xs] ++ [1] where xs = map fst (descomposicion n) f i | elem i xs = 1 | otherwise = 0 -- (descomposicion n) es la lista de pares (i,f) tales que f es el -- i-ésimo número de Fibonacci y las segundas componentes es una -- sucesión decreciente de números de Fibonacci cuya suma es n. Por -- ejemplo, -- descomposicion 65 == [(10,55),(6,8),(3,2)] -- descomposicion 66 == [(10,55),(6,8),(4,3)] descomposicion :: Integer -> [(Integer, Integer)] descomposicion 0 = [] descomposicion 1 = [(2,1)] descomposicion n = (i,x) : descomposicion (n-x) where (i,x) = fibAnterior n -- (fibAnterior n) es el mayor número de Fibonacci menor o igual que -- n. Por ejemplo, -- fibAnterior 33 == (8,21) -- fibAnterior 34 == (9,34) fibAnterior :: Integer -> (Integer, Integer) fibAnterior n = last (takeWhile p fibsConIndice) where p (i,x) = x <= n -- fibsConIndice es la sucesión de los números de Fibonacci junto con -- sus índices. Por ejemplo, -- λ> take 10 fibsConIndice -- [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21),(9,34)] fibsConIndice :: [(Integer, Integer)] fibsConIndice = zip [0..] fibs -- fibs es la sucesión de Fibonacci. Por ejemplo, -- take 10 fibs == [0,1,1,2,3,5,8,13,21,34] fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) --- 2ª solución -- ============ codigoFib2 :: Integer -> String codigoFib2 = (concatMap show) . elems . codificaFibVec -- (codificaFibVec n) es el vector correspondiente a la codificación de -- Fibonacci del número n. Por ejemplo, -- λ> codificaFibVec 65 -- array (0,9) [(0,0),(1,1),(2,0),(3,0),(4,1),(5,0),(6,0),(7,0),(8,1),(9,1)] -- λ> [elems (codificaFibVec n) | n <- [1..7]] -- [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]] codificaFibVec :: Integer -> Array Integer Integer codificaFibVec n = accumArray (+) 0 (0,a+1) ((a+1,1):is) where is = [(i-2,1) | (i,x) <- descomposicion n] a = fst (head is) -- Comparación de eficiencia -- ========================= -- λ> head [n | n <- [1..], length (codigoFib1 n) > 25] -- 121393 -- (14.37 secs, 3135674112 bytes) -- λ> :r -- Ok, modules loaded: Main. -- λ> head [n | n <- [1..], length (codigoFib2 n) > 25] -- 121393 -- (12.04 secs, 2762190920 bytes) -- Propiedades -- =========== -- Usaremos la 2ª definición codigoFib :: Integer -> String codigoFib = codigoFib2 -- Prop.: La función descomposicion es correcta: propDescomposicionCorrecta :: Integer -> Property propDescomposicionCorrecta n = n >= 0 ==> n == sum (map snd (descomposicion n)) -- La comprobación es -- λ> quickCheck propDescomposicionCorrecta -- +++ OK, passed 100 tests. -- Prop.: Todo número natural se puede descomponer en suma de números de -- la sucesión de Fibonacci. propDescomposicion :: Integer -> Property propDescomposicion n = n >= 0 ==> not (null (descomposicion n)) -- La comprobación es -- λ> quickCheck propDescomposicion -- +++ OK, passed 100 tests. -- Prop.: Las codificaciones de Fibonacci tienen como mínimo 2 elementos. prop1 :: Integer -> Property prop1 n = n > 0 ==> length (codigoFib n) >= 2 -- La comprobación es -- λ> quickCheck prop1 -- +++ OK, passed 100 tests. -- Prop.: Los dos últimos elementos de las codificaciones de Fibonacci -- son iguales a 1. prop2 :: Integer -> Property prop2 n = n > 0 ==> take 2 (reverse (codigoFib n)) == "11" -- La comprobación es -- λ> quickCheck prop2 -- +++ OK, passed 100 tests. -- Prop.: En las codificaciones de Fibonacci, la cadena "11" sólo -- aparece una vez y la única vez que aparece es al final. prop3 :: Integer -> Property prop3 n = n > 0 ==> not (isInfixOf "11" (drop 2 (reverse (codigoFib n)))) -- La comprobación es -- λ> quickCheck prop3 -- +++ OK, passed 100 tests.

Seguir leyendo →

Números de Perrin

José A. Alonso-19-mayo-2020-Inicial-4 Comentarios

Los números de Perrin se definen por la elación de recurrencia

   P(n) = P(n - 2) + P(n - 3) si n > 2,

con los valores iniciales

   P(0) = 3, P(1) = 0 y P(2) = 2.

Definir la sucesión

   sucPerrin :: [Integer]

cuyos elementos son los números de Perrin. Por ejemplo,

   λ> take 15 sucPerrin
   [3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
   λ> length (show (sucPerrin !! (2*10^5)))
   24425

Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.

Soluciones

import Data.List (genericIndex, unfoldr)
import Data.Numbers.Primes (isPrime)
import Test.QuickCheck
 
-- 1ª solución
sucPerrin1 :: [Integer]
sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)
 
-- 2ª solución
sucPerrin2 :: [Integer]
sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]
  where op (a,b,c) = (b,c,a+b)
 
-- 3ª solución
sucPerrin3 :: [Integer]
sucPerrin3 =
  unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))
 
-- 4ª solución
sucPerrin4 :: [Integer]
sucPerrin4 = [vectorPerrin n ! n | n <- [0..]]
 
vectorPerrin :: Integer -> Array Integer Integer
vectorPerrin n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 3
  f 1 = 0
  f 2 = 2
  f i = v ! (i-2) + v ! (i-3)
 
-- Comparación de eficiencia
--    λ> length (show (sucPerrin1 !! (3*10^5)))
--    36638
--    (1.62 secs, 2,366,238,984 bytes)
--    λ> length (show (sucPerrin2 !! (3*10^5)))
--    36638
--    (1.40 secs, 2,428,701,384 bytes)
--    λ> length (show (sucPerrin3 !! (3*10^5)))
--    36638
--    (1.14 secs, 2,409,504,864 bytes)
--    λ> length (show (sucPerrin4 !! (3*10^5)))
--    36638
--    (1.78 secs, 2,585,400,776 bytes)
 
 
-- Usaremos la 3ª
sucPerrin :: [Integer]
sucPerrin = sucPerrin3
 
-- La propiedad es  
conjeturaPerrin :: Integer -> Property
conjeturaPerrin n =
  n > 1 ==>
  (perrin n `mod` n == 0) == isPrime n
 
-- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por
-- ejemplo,
--    perrin 4  ==  2
--    perrin 5  ==  5
--    perrin 6  ==  5
perrin :: Integer -> Integer
perrin n = sucPerrin `genericIndex` n
 
-- La comprobación es
--    λ> quickCheck conjeturaPerrin
--    +++ OK, passed 100 tests.
 
-- Nota: Aunque QuickCheck no haya encontrado contraejemplos, la
-- propiedad no es cierta. Sólo lo es una de las implicaciones: si n es
-- primo, entonces el  n-ésimo término de la sucesión de Perrin es
-- divisible por n. La otra es falsa y los primeros contraejemplos son
--    271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291

import Data.List (genericIndex, unfoldr) import Data.Numbers.Primes (isPrime) import Test.QuickCheck -- 1ª solución sucPerrin1 :: [Integer] sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1) -- 2ª solución sucPerrin2 :: [Integer] sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)] where op (a,b,c) = (b,c,a+b) -- 3ª solución sucPerrin3 :: [Integer] sucPerrin3 = unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2)) -- 4ª solución sucPerrin4 :: [Integer] sucPerrin4 = [vectorPerrin n ! n | n <- [0..]] vectorPerrin :: Integer -> Array Integer Integer vectorPerrin n = v where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 3 f 1 = 0 f 2 = 2 f i = v ! (i-2) + v ! (i-3) -- Comparación de eficiencia -- λ> length (show (sucPerrin1 !! (3*10^5))) -- 36638 -- (1.62 secs, 2,366,238,984 bytes) -- λ> length (show (sucPerrin2 !! (3*10^5))) -- 36638 -- (1.40 secs, 2,428,701,384 bytes) -- λ> length (show (sucPerrin3 !! (3*10^5))) -- 36638 -- (1.14 secs, 2,409,504,864 bytes) -- λ> length (show (sucPerrin4 !! (3*10^5))) -- 36638 -- (1.78 secs, 2,585,400,776 bytes) -- Usaremos la 3ª sucPerrin :: [Integer] sucPerrin = sucPerrin3 -- La propiedad es conjeturaPerrin :: Integer -> Property conjeturaPerrin n = n > 1 ==> (perrin n `mod` n == 0) == isPrime n -- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por -- ejemplo, -- perrin 4 == 2 -- perrin 5 == 5 -- perrin 6 == 5 perrin :: Integer -> Integer perrin n = sucPerrin `genericIndex` n -- La comprobación es -- λ> quickCheck conjeturaPerrin -- +++ OK, passed 100 tests. -- Nota: Aunque QuickCheck no haya encontrado contraejemplos, la -- propiedad no es cierta. Sólo lo es una de las implicaciones: si n es -- primo, entonces el n-ésimo término de la sucesión de Perrin es -- divisible por n. La otra es falsa y los primeros contraejemplos son -- 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291

Seguir leyendo →

Etiqueta: Orden superior

Caminos reducidos

Soluciones

Número como suma de sus dígitos

Soluciones

Cambio con el menor número de monedas

Soluciones

Operaciones con series de potencias

Soluciones

Sucesión duplicadora

Soluciones

Cadenas de primos complementarios

Soluciones

Las sucesiones de Loomis

Soluciones

Espacio de estados del problema de las N reinas

Soluciones

Codificación de Fibonacci

Soluciones

Números de Perrin

Soluciones

Etiquetas

Entradas recientes

Comentarios recientes

Buscar

Correo electrónico

Meta