mayo 2016 – Exercitium

Sucesión infinita de todas las palabras

PorJosé A. Alonso 31-mayo-2016

El conjunto de todas las palabras se puede ordenar como en los diccionarios:

     a,   b, ...,   z,   A,   B, ...,   Z,
    aa,  ab, ...,  az,  aA,  aB, ...,  aZ,
    ba,  bb, ...,  bz,  bA,  bB, ...,  bZ,
   ...
    za,  zb, ...,  zz,  zA,  zB, ...,  zZ,
   aaa, aab, ..., aaz, aaA, aaB, ..., aaZ,
   baa, bab, ..., baz, baA, baB, ..., baZ,
   ...

a, b, ..., z, A, B, ..., Z,

aa, ab, ..., az, aA, aB, ..., aZ,

ba, bb, ..., bz, bA, bB, ..., bZ,

...

za, zb, ..., zz, zA, zB, ..., zZ,

aaa, aab, ..., aaz, aaA, aaB, ..., aaZ,

baa, bab, ..., baz, baA, baB, ..., baZ,

...

Definir las funciones

   palabras :: [String]
   posicion :: String -> Integer

1 2	palabras :: [String] posicion :: String -> Integer

tales que

palabras es la lista ordenada de todas las palabras. Por ejemplo,

     λ> take 10 (drop 100 palabras)
     ["aW","aX","aY","aZ","ba","bb","bc","bd","be","bf"]
     λ> take 10 (drop 2750 palabras)
     ["ZU","ZV","ZW","ZX","ZY","ZZ","aaa","aab","aac","aad"]
     λ> palabras !! (10^6)
     "gePO"

λ> take 10 (drop 100 palabras)

["aW","aX","aY","aZ","ba","bb","bc","bd","be","bf"]

λ> take 10 (drop 2750 palabras)

["ZU","ZV","ZW","ZX","ZY","ZZ","aaa","aab","aac","aad"]

λ> palabras !! (10^6)

"gePO"

(posicion n) es la palabra que ocupa la posición n en la lista ordenada de todas las palabras. Por ejemplo,

   posicion "c"                    ==  2
   posicion "ab"                   ==  53
   posicion "ba"                   ==  104
   posicion "eva"                  ==  14664
   posicion "adan"                 ==  151489
   posicion "HoyEsMartes"          ==  4957940944437977046
   posicion "EnUnLugarDeLaMancha"  ==  241779893912461058861484239910864

posicion "c" == 2

posicion "ab" == 53

posicion "ba" == 104

posicion "eva" == 14664

posicion "adan" == 151489

posicion "HoyEsMartes" == 4957940944437977046

posicion "EnUnLugarDeLaMancha" == 241779893912461058861484239910864

Comprobar con QuickCheck que para todo entero positivo n se verifica que

   posicion (palabras `genericIndex` n) == n

1	posicion (palabras `genericIndex` n) == n

Soluciones

[schedule expon=’2016-06-07′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 07 de junio.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-06-07′ at=»06:00″]

import Data.List (genericIndex, genericLength)
import Test.QuickCheck

-- 1ª definición de palabras
-- =========================
    
palabras1 :: [String]
palabras1 = concatMap palabrasDeLongitud [1..]

-- (palabrasDeLongitud n) es la lista ordenada de palabras longitud
-- n. Por ejemplo,
--    take 3 (palabrasDeLongitud 2)  ==  ["aa","ab","ac"]
--    take 3 (palabrasDeLongitud 3)  ==  ["aaa","aab","aac"]
palabrasDeLongitud :: Integer -> [String]
palabrasDeLongitud 1 = [[x]  | x <- letras]
palabrasDeLongitud n = [x:ys | x <- letras,
                               ys <- palabrasDeLongitud (n-1)]

-- letras es la lista ordenada de las letras.                       
letras :: [Char]
letras = ['a'..'z'] ++ ['A'..'Z']

-- 2ª definición de palabras
-- =========================

palabras2 :: [String]
palabras2 = concat (iterate f elementales)
    where f = concatMap (\x -> map (x++) elementales)

-- elementales es la lista de las palabras de una letra.              
elementales :: [String]            
elementales = map (:[]) letras

-- 3ª definición de palabras
-- =========================

palabras3 :: [String]
palabras3 = tail $ map reverse aux
    where aux = "" : [c:cs | cs <- aux, c <- letras]

-- Comparación
-- ===========

--    λ> palabras1 !! (10^6)
--    "gePO"
--    (0.87 secs, 480,927,648 bytes)
--    λ> palabras2 !! (10^6)
--    "gePO"
--    (0.11 secs, 146,879,840 bytes)
--    λ> palabras3 !! (10^6)
--    "gePO"
--    (0.25 secs, 203,584,608 bytes)

-- 1ª definición de posicion
-- =========================

posicion1 :: String -> Integer
posicion1 cs = genericLength (takeWhile (/=cs) palabras1)

-- 1ª definición de posicion
-- =========================

posicion2 :: String -> Integer
posicion2 ""     = -1
posicion2 (c:cs) = (1 + posicionLetra c) * 52^(length cs) + posicion2 cs

posicionLetra :: Char -> Integer
posicionLetra c = genericLength (takeWhile (/=c) letras)

-- La propiedad es
prop_palabras :: (Positive Integer) -> Bool
prop_palabras (Positive n) =
    posicion2 (palabras3 `genericIndex` n) == n

-- La comprobación es              
--    λ> quickCheck prop_palabras
--    +++ OK, passed 100 tests.

import Data.List (genericIndex, genericLength)

import Test.QuickCheck

-- 1ª definición de palabras

-- =========================

palabras1 :: [String]

palabras1 = concatMap palabrasDeLongitud [1..]

-- (palabrasDeLongitud n) es la lista ordenada de palabras longitud

-- n. Por ejemplo,

-- take 3 (palabrasDeLongitud 2) == ["aa","ab","ac"]

-- take 3 (palabrasDeLongitud 3) == ["aaa","aab","aac"]

palabrasDeLongitud :: Integer -> [String]

palabrasDeLongitud 1 = [[x] | x <- letras]

palabrasDeLongitud n = [x:ys | x <- letras,

ys <- palabrasDeLongitud (n-1)]

-- letras es la lista ordenada de las letras.

letras :: [Char]

letras = ['a'..'z'] ++ ['A'..'Z']

-- 2ª definición de palabras

-- =========================

palabras2 :: [String]

palabras2 = concat (iterate f elementales)

where f = concatMap (\x -> map (x++) elementales)

-- elementales es la lista de las palabras de una letra.

elementales :: [String]

elementales = map (:[]) letras

-- 3ª definición de palabras

-- =========================

palabras3 :: [String]

palabras3 = tail $ map reverse aux

where aux = "" : [c:cs | cs <- aux, c <- letras]

-- Comparación

-- ===========

-- λ> palabras1 !! (10^6)

-- "gePO"

-- (0.87 secs, 480,927,648 bytes)

-- λ> palabras2 !! (10^6)

-- "gePO"

-- (0.11 secs, 146,879,840 bytes)

-- λ> palabras3 !! (10^6)

-- "gePO"

-- (0.25 secs, 203,584,608 bytes)

-- 1ª definición de posicion

-- =========================

posicion1 :: String -> Integer

posicion1 cs = genericLength (takeWhile (/=cs) palabras1)

-- 1ª definición de posicion

-- =========================

posicion2 :: String -> Integer

posicion2 "" = -1

posicion2 (c:cs) = (1 + posicionLetra c) * 52^(length cs) + posicion2 cs

posicionLetra :: Char -> Integer

posicionLetra c = genericLength (takeWhile (/=c) letras)

-- La propiedad es

prop_palabras :: (Positive Integer) -> Bool

prop_palabras (Positive n) =

posicion2 (palabras3 `genericIndex` n) == n

-- La comprobación es

-- λ> quickCheck prop_palabras

-- +++ OK, passed 100 tests.

[/schedule]

Cadenas de primos complementarios

PorJosé A. Alonso 30-mayo-201625-abril-2021

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]

1 2	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]

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]

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

Soluciones

[schedule expon=’2016-06-06′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 06 de junio.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-06-06′ at=»06:00″]

import Data.Numbers.Primes

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

complemento :: Integer -> Integer
complemento x = (div x c)*c - (rem x c)
    where c = 10^(length (show x) - 1)          

conCadena :: Int -> [Integer]
conCadena n =
    [y | y <- primes, length (cadena y) == n]

import Data.Numbers.Primes

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

complemento :: Integer -> Integer

complemento x = (div x c)*c - (rem x c)

where c = 10^(length (show x) - 1)

conCadena :: Int -> [Integer]

conCadena n =

[y | y <- primes, length (cadena y) == n]

[/schedule]

Construcción del árbol a partir de los recorridos preorden e inorden

PorJosé A. Alonso 27-mayo-201627-mayo-2016

Los árboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
                deriving (Show, Eq)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

Por ejemplo, el árbol

/ \

3 7

/ \

2 4

se representa por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	N 9 (N 3 (H 2) (H 4)) (H 7)

Definir las siguientes funciones

   preorden :: Arbol a -> [a]
   inorden  :: Arbol a -> [a]
   arboles  :: Eq a => [a] -> [a] -> [Arbol a]

preorden :: Arbol a -> [a]

inorden :: Arbol a -> [a]

arboles :: Eq a => [a] -> [a] -> [Arbol a]

tales que

(preorden x) es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo,

     preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]

1	preorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [9,3,2,4,7]

(inorden x) es la lista correspondiente al recorrido inorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación visita la raíz del árbol y, finalmente, recorre el subárbol derecho. Por ejemplo,

     inorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,3,4,9,7]

1	inorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [2,3,4,9,7]

(arboles xs ys) es la lista de los árboles con recorrido preorden xs y recorrido inorden de ys. Por ejemplo,

      λ> arboles [9,3,2,4,7] [2,3,4,9,7]
      [N 9 (N 3 (H 2) (H 4)) (H 7)]
      λ> arboles [9,3,2,4,7] [2,4,3,9,7]
      []
      λ> arboles [1,1,1,2,3] [1,1,2,1,3]
      [N 1 (H 1) (N 1 (H 2) (H 3)),
       N 1 (N 1 (H 1) (H 2)) (H 3)]
      λ> let x = N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))
      λ> arboles (preorden x) (inorden x)
      [N 1 (H 1) (N 1 (H 3) (N 1 (H 1) (N 1 (H 2) (H 3)))),
       N 1 (H 1) (N 1 (H 3) (N 1 (N 1 (H 1) (H 2)) (H 3))),
       N 1 (N 1 (H 1) (H 3)) (N 1 (H 1) (N 1 (H 2) (H 3))),
       N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))]

λ> arboles [9,3,2,4,7] [2,3,4,9,7]

[N 9 (N 3 (H 2) (H 4)) (H 7)]

λ> arboles [9,3,2,4,7] [2,4,3,9,7]

[]

λ> arboles [1,1,1,2,3] [1,1,2,1,3]

[N 1 (H 1) (N 1 (H 2) (H 3)),

N 1 (N 1 (H 1) (H 2)) (H 3)]

λ> let x = N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))

λ> arboles (preorden x) (inorden x)

[N 1 (H 1) (N 1 (H 3) (N 1 (H 1) (N 1 (H 2) (H 3)))),

N 1 (H 1) (N 1 (H 3) (N 1 (N 1 (H 1) (H 2)) (H 3))),

N 1 (N 1 (H 1) (H 3)) (N 1 (H 1) (N 1 (H 2) (H 3))),

N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))]

Comprobar con QuickCheck, que para todo árbol x se verifican las siguientes propiedades

    prop_arboles1 :: Arbol Int -> Bool
    prop_arboles1 x =
        x `elem` arboles (preorden x) (inorden x)
    
    prop_arboles2 :: Arbol Int -> Bool
    prop_arboles2 x =
        and [preorden a == xs && inorden a == ys | a <- as] 
        where xs = preorden x
              ys = inorden x
              as = arboles xs ys

prop_arboles1 :: Arbol Int -> Bool

prop_arboles1 x =

x `elem` arboles (preorden x) (inorden x)

prop_arboles2 :: Arbol Int -> Bool

prop_arboles2 x =

and [preorden a == xs && inorden a == ys | a <- as]

where xs = preorden x

ys = inorden x

as = arboles xs ys

Nota: Para la comprobación, se usa el siguiente generador

   import Control.Monad 
   
   instance Arbitrary a => Arbitrary (Arbol a) where
     arbitrary = sized arbol
       where
         arbol 0       = liftM H arbitrary 
         arbol n | n>0 = oneof [liftM H arbitrary,
                                liftM3 N arbitrary subarbol subarbol]
                         where subarbol = arbol (div n 2)

import Control.Monad

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbol

where

arbol 0 = liftM H arbitrary

arbol n | n>0 = oneof [liftM H arbitrary,

liftM3 N arbitrary subarbol subarbol]

where subarbol = arbol (div n 2)

Soluciones

[schedule expon=’2016-06-02′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 02 de junio.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-06-02′ at=»06:00″]

import Data.List (elemIndex, elemIndices)
import Data.Maybe (isJust, fromJust)
import Test.QuickCheck
import Control.Monad 

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving (Show, Eq)

preorden :: Arbol a -> [a]
preorden (H x)     = [x]
preorden (N x i d) = x : (preorden i ++ preorden d)

inorden :: Arbol a -> [a]
inorden (H x)     = [x]
inorden (N x i d) = inorden i ++ (x : inorden d)

arboles :: Eq a => [a] -> [a] -> [Arbol a]
arboles [] _      = []
arboles [x] ys | ys == [x] = [H x]
               | otherwise = []
arboles (x:xs) ys =
    [N x i d | k <- elemIndices x ys 
             , let (ys1,_:ys2) = splitAt k ys
             , let (xs1,xs2)   = splitAt k xs
             , i <- arboles xs1 ys1
             , d <- arboles xs2 ys2]

prop_arboles1 :: Arbol Int -> Bool
prop_arboles1 x =
    x `elem` arboles (preorden x) (inorden x)

prop_arboles2 :: Arbol Int -> Bool
prop_arboles2 x =
    and [preorden a == xs && inorden a == ys | a <- as] 
    where xs = preorden x
          ys = inorden x
          as = arboles xs ys

instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbol
    where
      arbol 0       = liftM H arbitrary 
      arbol n | n>0 = oneof [liftM H arbitrary,
                             liftM3 N arbitrary subarbol subarbol]
                      where subarbol = arbol (div n 2)

import Data.List (elemIndex, elemIndices)

import Data.Maybe (isJust, fromJust)

import Test.QuickCheck

import Control.Monad

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

preorden :: Arbol a -> [a]

preorden (H x) = [x]

preorden (N x i d) = x : (preorden i ++ preorden d)

inorden :: Arbol a -> [a]

inorden (H x) = [x]

inorden (N x i d) = inorden i ++ (x : inorden d)

arboles :: Eq a => [a] -> [a] -> [Arbol a]

arboles [] _ = []

arboles [x] ys | ys == [x] = [H x]

| otherwise = []

arboles (x:xs) ys =

[N x i d | k <- elemIndices x ys

, let (ys1,_:ys2) = splitAt k ys

, let (xs1,xs2) = splitAt k xs

, i <- arboles xs1 ys1

, d <- arboles xs2 ys2]

prop_arboles1 :: Arbol Int -> Bool

prop_arboles1 x =

x `elem` arboles (preorden x) (inorden x)

prop_arboles2 :: Arbol Int -> Bool

prop_arboles2 x =

and [preorden a == xs && inorden a == ys | a <- as]

where xs = preorden x

ys = inorden x

as = arboles xs ys

instance Arbitrary a => Arbitrary (Arbol a) where

arbitrary = sized arbol

where

arbol 0 = liftM H arbitrary

arbol n | n>0 = oneof [liftM H arbitrary,

liftM3 N arbitrary subarbol subarbol]

where subarbol = arbol (div n 2)

[/schedule]

Caminos en una retícula

PorJosé A. Alonso 26-mayo-20162-junio-2016

El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.

Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.

Para representar los caminos se definen los siguientes tipos de datos:

    data Direccion = D | A deriving (Show, Eq)
    type Camino = [Direccion]

1 2	data Direccion = D \| A deriving (Show, Eq) type Camino = [Direccion]

Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].

Definir las funciones

   caminos  :: Int -> Int -> [Camino]
   nCaminos :: Int -> Int -> Integer

1 2	caminos :: Int -> Int -> [Camino] nCaminos :: Int -> Int -> Integer

tales que

(caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     λ> caminos 2 2
     [[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]
     λ> caminos 1 3
     [[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]
     λ> caminos 2 3
     [[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],
      [D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

λ> caminos 2 2

[[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]

λ> caminos 1 3

[[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]

λ> caminos 2 3

[[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],

[D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

(nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     nCaminos 2 2  ==  6
     nCaminos 1 3  ==  4
     nCaminos 2 3  ==  10
     length (show (nCaminos 20000 30000))  ==  14612
     length (show (nCaminos 30000 20000))  ==  14612

nCaminos 2 2 == 6

nCaminos 1 3 == 4

nCaminos 2 3 == 10

length (show (nCaminos 20000 30000)) == 14612

length (show (nCaminos 30000 20000)) == 14612

Soluciones

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos
-- =====================

caminos :: Int -> Int -> [Camino]
caminos 0 n = [replicate n A]
caminos m 0 = [replicate m D]
caminos m n = [A:xs | xs <- caminos m (n-1)] ++
              [D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos
-- =========================

nCaminos1 :: Int -> Int -> Integer
nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos
-- =========================

nCaminos2 :: Int -> Int -> Integer
nCaminos2 0 n = 1
nCaminos2 m 0 = 1
nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos
-- =========================

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición
-- de m veces la D y n veces la A. Por tanto, su número es
--    (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer
nCaminos3 m n = 
    fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer
fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos
-- =======================

nCaminos4 :: Int -> Int -> Integer
nCaminos4 m n = 
    product [a+1..a+b] `div` product [2..b]
    where m' = fromIntegral m
          n' = fromIntegral n
          a  = max m' n'
          b  = min m' n'

-- Comparación de eficiencia
-- =========================

--    λ> nCaminos1 10 10
--    184756
--    (3.50 secs, 656,909,648 bytes)
--    λ> nCaminos2 10 10
--    184756
--    (0.50 secs, 47,330,272 bytes)
--    λ> nCaminos3 10 10
--    184756
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 10
--    184756
--    (0.01 secs, 0 bytes)
-- 
--    λ> nCaminos2 10 15
--    3268760
--    (8.83 secs, 1,142,623,080 bytes)
--    λ> nCaminos3 10 15
--    3268760
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 15
--    3268760
--    (0.00 secs, 0 bytes)
--
--    λ> let n = 2*10^4 
--    (0.01 secs, 0 bytes)
--    λ> length (show (nCaminos3 n n))
--    12039
--    (8.41 secs, 2,369,767,480 bytes)
--    λ> length (show (nCaminos4 n n))
--    12039
--    (2.98 secs, 833,386,648 bytes)

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos

-- =====================

caminos :: Int -> Int -> [Camino]

caminos 0 n = [replicate n A]

caminos m 0 = [replicate m D]

caminos m n = [A:xs | xs <- caminos m (n-1)] ++

[D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos

-- =========================

nCaminos1 :: Int -> Int -> Integer

nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos

-- =========================

nCaminos2 :: Int -> Int -> Integer

nCaminos2 0 n = 1

nCaminos2 m 0 = 1

nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos

-- =========================

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición

-- de m veces la D y n veces la A. Por tanto, su número es

-- (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer

nCaminos3 m n =

fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer

fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos

-- =======================

nCaminos4 :: Int -> Int -> Integer

nCaminos4 m n =

product [a+1..a+b] `div` product [2..b]

where m' = fromIntegral m

n' = fromIntegral n

a = max m' n'

b = min m' n'

-- Comparación de eficiencia

-- =========================

-- λ> nCaminos1 10 10

-- 184756

-- (3.50 secs, 656,909,648 bytes)

-- λ> nCaminos2 10 10

-- 184756

-- (0.50 secs, 47,330,272 bytes)

-- λ> nCaminos3 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos2 10 15

-- 3268760

-- (8.83 secs, 1,142,623,080 bytes)

-- λ> nCaminos3 10 15

-- 3268760

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 15

-- 3268760

-- (0.00 secs, 0 bytes)

-- λ> let n = 2*10^4

-- (0.01 secs, 0 bytes)

-- λ> length (show (nCaminos3 n n))

-- 12039

-- (8.41 secs, 2,369,767,480 bytes)

-- λ> length (show (nCaminos4 n n))

-- 12039

-- (2.98 secs, 833,386,648 bytes)

Centro de gravedad de una lista

PorJosé A. Alonso 25-mayo-201626-marzo-2022

Se dice que una lista de números xs es equilibrada si existe una posición k tal que la suma de los elementos de xs en las posiciones menores que k es igual a la de los elementos de xs en las posiciones mayores que k. La posición k se llama el centro de gravedad de xs. Por ejemplo, la lista [1,3,4,5,-2,1] es equilibrada, y su centro de gravedad es 2, ya que la suma de [1,3] es igual a la de [5,-2,1]. En cambio, la lista [1,6,4,5,-2,1] no tiene centro de gravedad.

Definir la función

   centro :: (Num a, Eq a) => [a] -> Maybe Int

1	centro :: (Num a, Eq a) => [a] -> Maybe Int

tal que (centro xs) es justo el centro e gravedad de xs, si la lista xs es equilibrada y Nothing en caso contrario. Por ejemplo,

   centro [1,3,4,5,-2,1]           ==  Just 2
   centro [1,6,4,5,-2,1]           ==  Nothing
   centro [1,2,3,4,3,2,1]          ==  Just 3
   centro [1,100,50,-51,1,1]       ==  Just 1
   centro [1,2,3,4,5,6]            ==  Nothing
   centro [20,10,30,10,10,15,35]   ==  Just 3
   centro [20,10,-80,10,10,15,35]  ==  Just 0
   centro [10,-80,10,10,15,35,20]  ==  Just 6
   centro [0,0,0,0,0]              ==  Just 0
   centro [-1,-2,-3,-4,-3,-2,-1]   ==  Just 3

centro [1,3,4,5,-2,1] == Just 2

centro [1,6,4,5,-2,1] == Nothing

centro [1,2,3,4,3,2,1] == Just 3

centro [1,100,50,-51,1,1] == Just 1

centro [1,2,3,4,5,6] == Nothing

centro [20,10,30,10,10,15,35] == Just 3

centro [20,10,-80,10,10,15,35] == Just 0

centro [10,-80,10,10,15,35,20] == Just 6

centro [0,0,0,0,0] == Just 0

centro [-1,-2,-3,-4,-3,-2,-1] == Just 3

Soluciones

import Data.List (inits, tails)
import Data.Maybe (listToMaybe)

-- 1ª solución
-- ===========

centro1 :: (Num a, Eq a) => [a] -> Maybe Int
centro1 xs 
    | null ns   = Nothing
    | otherwise = Just (head ns)
    where ns = [n | n <- [0..length xs - 1],
                    let (ys,_:zs) = splitAt n xs,
                    sum ys == sum zs]

-- 2ª solución
-- ===========

centro2 :: (Num a, Eq a) => [a] -> Maybe Int
centro2 xs = aux 0 0 (sum xs) xs where
    aux _ _ _ [] = Nothing
    aux k i d (z:zs) | i == d - z = Just k
                     | otherwise  = aux (k + 1) (i + z) (d - z) zs

-- 3ª solución
-- ===========

centro3 :: (Num a, Eq a) => [a] -> Maybe Int
centro3 xs =
  listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)
                  , sum ys == sum zs]

-- Comparación de eficiencia
-- =========================

--    λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))
--    Just 3000
--    (2.70 secs, 2,088,881,728 bytes)
--    λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))
--    Just 3000
--    (0.03 secs, 0 bytes)
--    λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))
--    Just 3000
--    (2.34 secs, 1,727,569,688 bytes)

import Data.List (inits, tails)

import Data.Maybe (listToMaybe)

-- 1ª solución

-- ===========

centro1 :: (Num a, Eq a) => [a] -> Maybe Int

centro1 xs

| null ns = Nothing

| otherwise = Just (head ns)

where ns = [n | n <- [0..length xs - 1],

let (ys,_:zs) = splitAt n xs,

sum ys == sum zs]

-- 2ª solución

-- ===========

centro2 :: (Num a, Eq a) => [a] -> Maybe Int

centro2 xs = aux 0 0 (sum xs) xs where

aux _ _ _ [] = Nothing

aux k i d (z:zs) | i == d - z = Just k

| otherwise = aux (k + 1) (i + z) (d - z) zs

-- 3ª solución

-- ===========

centro3 :: (Num a, Eq a) => [a] -> Maybe Int

centro3 xs =

listToMaybe [ k | (k,ys,_:zs) <- zip3 [0..] (inits xs) (tails xs)

, sum ys == sum zs]

-- Comparación de eficiencia

-- =========================

-- λ> let xs = [1..3000] in centro1 (xs ++ (0:xs))

-- Just 3000

-- (2.70 secs, 2,088,881,728 bytes)

-- λ> let xs = [1..3000] in centro2 (xs ++ (0:xs))

-- Just 3000

-- (0.03 secs, 0 bytes)

-- λ> let xs = [1..3000] in centro3 (xs ++ (0:xs))

-- Just 3000

-- (2.34 secs, 1,727,569,688 bytes)

El problema de las N torres

PorJosé A. Alonso 24-mayo-201625-abril-2021

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representa las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

   ( 0 1 0 )
   ( 1 0 0 )
   ( 0 0 1 )

( 0 1 0 )

( 1 0 0 )

( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

   torres  :: Int -> [Matrix Int]
   nTorres :: Int -> Integer

1 2	torres :: Int -> [Matrix Int] nTorres :: Int -> Integer

tales que
+ (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

      λ> torres 3
      [( 1 0 0 )
       ( 0 1 0 )
       ( 0 0 1 )
      ,( 1 0 0 )
       ( 0 0 1 )
       ( 0 1 0 )
      ,( 0 1 0 )
       ( 1 0 0 )
       ( 0 0 1 )
      ,( 0 1 0 )
       ( 0 0 1 )
       ( 1 0 0 )
      ,( 0 0 1 )
       ( 1 0 0 )
       ( 0 1 0 )
      ,( 0 0 1 )
       ( 0 1 0 )
       ( 1 0 0 )
      ]

λ> torres 3

[( 1 0 0 )

( 0 1 0 )

( 0 0 1 )

,( 1 0 0 )

( 0 0 1 )

( 0 1 0 )

,( 0 1 0 )

( 1 0 0 )

( 0 0 1 )

,( 0 1 0 )

( 0 0 1 )

( 1 0 0 )

,( 0 0 1 )

( 1 0 0 )

( 0 1 0 )

,( 0 0 1 )

( 0 1 0 )

( 1 0 0 )

]

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

      λ> nTorres 3
      6
      λ> length (show (nTorres (10^4)))
      35660

λ> nTorres 3

λ> length (show (nTorres (10^4)))

35660

Soluciones

[schedule expon=’2016-05-31′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 31 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-05-31′ at=»06:00″]

import Data.List (genericLength, sort, permutations)
import Data.Matrix 

-- 1ª definición de torres
-- =======================

torres1 :: Int -> [Matrix Int]
torres1 n = 
    [permutacionAmatriz n p | p <- sort (permutations [1..n])]

permutacionAmatriz :: Int -> [Int] -> Matrix Int
permutacionAmatriz n p =
    matrix n n f
    where f (i,j) | (i,j) `elem` posiciones = 1
                  | otherwise               = 0
          posiciones = zip [1..n] p    

-- 2ª definición de torres
-- =======================

torres2 :: Int -> [Matrix Int]
torres2 = map fromLists . permutations . toLists . identity

-- El cálculo con la definición anterior es:
--    λ> identity 3
--    ( 1 0 0 )
--    ( 0 1 0 )
--    ( 0 0 1 )
--    
--    λ> toLists it
--    [[1,0,0],[0,1,0],[0,0,1]]
--    λ> permutations it
--    [[[1,0,0],[0,1,0],[0,0,1]],
--     [[0,1,0],[1,0,0],[0,0,1]],
--     [[0,0,1],[0,1,0],[1,0,0]],
--     [[0,1,0],[0,0,1],[1,0,0]],
--     [[0,0,1],[1,0,0],[0,1,0]],
--     [[1,0,0],[0,0,1],[0,1,0]]]
--    λ> map fromLists it
--    [( 1 0 0 )
--     ( 0 1 0 )
--     ( 0 0 1 )
--    ,( 0 1 0 )
--     ( 1 0 0 )
--     ( 0 0 1 )
--    ,( 0 0 1 )
--     ( 0 1 0 )
--     ( 1 0 0 )
--    ,( 0 1 0 )
--     ( 0 0 1 )
--     ( 1 0 0 )
--    ,( 0 0 1 )
--     ( 1 0 0 )
--     ( 0 1 0 )
--    ,( 1 0 0 )
--     ( 0 0 1 )
--     ( 0 1 0 )
--    ]

-- 1ª definición de nTorres
-- ========================

nTorres1 :: Int -> Integer
nTorres1 = genericLength . torres1

-- 2ª definición de nTorres
-- ========================

nTorres2 :: Int -> Integer
nTorres2 n = product [1..fromIntegral n]

-- Comparación de eficiencia
-- =========================

--    λ> nTorres1 9
--    362880
--    (4.22 secs, 693,596,128 bytes)
--    λ> nTorres2 9
--    362880
--    (0.00 secs, 0 bytes)

import Data.List (genericLength, sort, permutations)

import Data.Matrix

-- 1ª definición de torres

-- =======================

torres1 :: Int -> [Matrix Int]

torres1 n =

[permutacionAmatriz n p | p <- sort (permutations [1..n])]

permutacionAmatriz :: Int -> [Int] -> Matrix Int

permutacionAmatriz n p =

matrix n n f

where f (i,j) | (i,j) `elem` posiciones = 1

| otherwise = 0

posiciones = zip [1..n] p

-- 2ª definición de torres

-- =======================

torres2 :: Int -> [Matrix Int]

torres2 = map fromLists . permutations . toLists . identity

-- El cálculo con la definición anterior es:

-- λ> identity 3

-- ( 1 0 0 )

-- ( 0 1 0 )

-- ( 0 0 1 )

-- λ> toLists it

-- [[1,0,0],[0,1,0],[0,0,1]]

-- λ> permutations it

-- [[[1,0,0],[0,1,0],[0,0,1]],

-- [[0,1,0],[1,0,0],[0,0,1]],

-- [[0,0,1],[0,1,0],[1,0,0]],

-- [[0,1,0],[0,0,1],[1,0,0]],

-- [[0,0,1],[1,0,0],[0,1,0]],

-- [[1,0,0],[0,0,1],[0,1,0]]]

-- λ> map fromLists it

-- [( 1 0 0 )

-- ( 0 1 0 )

-- ( 0 0 1 )

-- ,( 0 1 0 )

-- ( 1 0 0 )

-- ( 0 0 1 )

-- ,( 0 0 1 )

-- ( 0 1 0 )

-- ( 1 0 0 )

-- ,( 0 1 0 )

-- ( 0 0 1 )

-- ( 1 0 0 )

-- ,( 0 0 1 )

-- ( 1 0 0 )

-- ( 0 1 0 )

-- ,( 1 0 0 )

-- ( 0 0 1 )

-- ( 0 1 0 )

-- ]

-- 1ª definición de nTorres

-- ========================

nTorres1 :: Int -> Integer

nTorres1 = genericLength . torres1

-- 2ª definición de nTorres

-- ========================

nTorres2 :: Int -> Integer

nTorres2 n = product [1..fromIntegral n]

-- Comparación de eficiencia

-- =========================

-- λ> nTorres1 9

-- 362880

-- (4.22 secs, 693,596,128 bytes)

-- λ> nTorres2 9

-- 362880

-- (0.00 secs, 0 bytes)

[/schedule]

Sucesiones de listas de números

PorJosé A. Alonso 20-mayo-201626-marzo-2022

En la Olimpiada Internacional de Matemáticas del 2012 se propuso el siguiente problema:

Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos números adyacentes x e y tales que x > y y x está a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que sólo puede aplicar un número finito de dichas iteraciones.

Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformación).

Definir las funciones

   soluciones       :: [Int] -> [Estado]
   finales          :: [Int] -> [[Int]]
   finalesMaximales :: [Int] -> (Int,[[Int]])

soluciones :: [Int] -> [Estado]

finales :: [Int] -> [[Int]]

finalesMaximales :: [Int] -> (Int,[[Int]])

tales que

(soluciones xs) es la lista de pares (n,ys) tales que ys es una lista obtenida aplicándole n transformaciones a xs. Por ejemplo,

     λ> soluciones [1,3,2]
     [(1,[1,3,3]),(1,[1,2,3])]
     λ> sort (nub (soluciones [3,3,2]))
     [(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]
     λ> sort (nub (soluciones [3,2,1]))
     [(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]

λ> soluciones [1,3,2]

[(1,[1,3,3]),(1,[1,2,3])]

λ> sort (nub (soluciones [3,3,2]))

[(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]

λ> sort (nub (soluciones [3,2,1]))

[(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]

(finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar más transformaciones. Por ejemplo,

     finales [1,2,3]               ==  [[1,2,3]]
     finales [1,3,2]               ==  [[1,2,3],[1,3,3]]
     finales [3,2,1]               ==  [[2,2,3],[2,3,3],[3,3,3]]
     finales [1,3,2,4]             ==  [[1,2,3,4],[1,3,3,4]]
     finales [1,3,2,3]             ==  [[1,2,3,3],[1,3,3,3]]
     length (finales [9,6,0,7,2])  ==  19
     length (finales [80,60..0])   ==  420

finales [1,2,3] == [[1,2,3]]

finales [1,3,2] == [[1,2,3],[1,3,3]]

finales [3,2,1] == [[2,2,3],[2,3,3],[3,3,3]]

finales [1,3,2,4] == [[1,2,3,4],[1,3,3,4]]

finales [1,3,2,3] == [[1,2,3,3],[1,3,3,3]]

length (finales [9,6,0,7,2]) == 19

length (finales [80,60..0]) == 420

(finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas más largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo,

     finalesMaximales [9,5,7]   ==  (2,[[6,8,9],[8,8,9]])
     finalesMaximales [3,2,1]   ==  (4,[[2,3,3],[3,3,3]])
     finalesMaximales [3,2..0]  ==  (10,[[2,3,3,3],[3,3,3,3]])
     finalesMaximales [4,3..0]  ==  (20,[[3,4,4,4,4],[4,4,4,4,4]])

finalesMaximales [9,5,7] == (2,[[6,8,9],[8,8,9]])

finalesMaximales [3,2,1] == (4,[[2,3,3],[3,3,3]])

finalesMaximales [3,2..0] == (10,[[2,3,3,3],[3,3,3,3]])

finalesMaximales [4,3..0] == (20,[[3,4,4,4,4],[4,4,4,4,4]])

Soluciones

import Data.List (nub, sort)
import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

type Estado = (Int,[Int])

inicial :: [Int] -> Estado
inicial xs = (0,xs)

esFinal :: Estado -> Bool
esFinal e = null (sucesores e)

--    λ> sucesores [9,6,0,7,2]
--    [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]
sucesores :: Estado -> [Estado]
sucesores (_,[])  = []
sucesores (_,[_]) = []
sucesores (n,x:y:xs) | x > y     = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss
                     | otherwise = yss
    where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]
                       

soluciones :: [Int] -> [Estado]
soluciones xs =
    buscaEE sucesores esFinal (inicial xs)

finales :: [Int] -> [[Int]]
finales xs =
    sort (nub (map snd (soluciones xs)))
            
finalesMaximales :: [Int] -> (Int,[[Int]])
finalesMaximales xs =
    (m, [xs | (n,xs) <- es, n == m])
    where es    = sort (nub (soluciones xs))
          (m,_) = maximum es

import Data.List (nub, sort)

import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

type Estado = (Int,[Int])

inicial :: [Int] -> Estado

inicial xs = (0,xs)

esFinal :: Estado -> Bool

esFinal e = null (sucesores e)

-- λ> sucesores [9,6,0,7,2]

-- [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]

sucesores :: Estado -> [Estado]

sucesores (_,[]) = []

sucesores (_,[_]) = []

sucesores (n,x:y:xs) | x > y = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss

| otherwise = yss

where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]

soluciones :: [Int] -> [Estado]

soluciones xs =

buscaEE sucesores esFinal (inicial xs)

finales :: [Int] -> [[Int]]

finales xs =

sort (nub (map snd (soluciones xs)))

finalesMaximales :: [Int] -> (Int,[[Int]])

finalesMaximales xs =

(m, [xs | (n,xs) <- es, n == m])

where es = sort (nub (soluciones xs))

(m,_) = maximum es

Particiones de longitud fija

PorJosé A. Alonso 19-mayo-201626-mayo-2016

Definir la función

   particionesFijas :: Int -> Int -> [[Int]]

1	particionesFijas :: Int -> Int -> [[Int]]

tal que (particionesFijas n k) es la lista de listas de k números naturales no crecientes cuya suma es n. Por ejemplo,

   ghci> particionesFijas 8 2
   [[4,4],[5,3],[6,2],[7,1]]
   ghci> particionesFijas 8 3
   [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]
   ghci> particionesFijas 9 3
   [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]
   ghci> length (particionesFijas 67 5)
   8056

ghci> particionesFijas 8 2

[[4,4],[5,3],[6,2],[7,1]]

ghci> particionesFijas 8 3

[[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]

ghci> particionesFijas 9 3

[[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]

ghci> length (particionesFijas 67 5)

8056

Soluciones

-- 1ª definición
particionesFijas :: Int -> Int -> [[Int]]
particionesFijas n 1 = [[n]]
particionesFijas n k 
    | k < 1     = []
    | otherwise = [x:y:ys | x <- [1..n-1], 
                            (y:ys) <- particionesFijas (n-x) (k-1),
                            x >= y]

-- 2ª definición
particionesFijas2 :: Int -> Int -> [[Int]]
particionesFijas2 n k
    | k <= 0    = []
    | k == 1    = [[n]]
    | k == n    = [replicate k 1]
    | k > n     = []
    | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++
                  [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:
--    ghci> length (particionesFijas 800 3)
--    53333
--    (1.01 secs, 97696476 bytes)
--    
--    ghci> length (particionesFijas2 800 3)
--    53333
--    (4.52 secs, 693969028 bytes)

-- 1ª definición

particionesFijas :: Int -> Int -> [[Int]]

particionesFijas n 1 = [[n]]

particionesFijas n k

| k < 1 = []

| otherwise = [x:y:ys | x <- [1..n-1],

(y:ys) <- particionesFijas (n-x) (k-1),

x >= y]

-- 2ª definición

particionesFijas2 :: Int -> Int -> [[Int]]

particionesFijas2 n k

| k <= 0 = []

| k == 1 = [[n]]

| k == n = [replicate k 1]

| k > n = []

| otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++

[[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:

-- ghci> length (particionesFijas 800 3)

-- 53333

-- (1.01 secs, 97696476 bytes)

-- ghci> length (particionesFijas2 800 3)

-- 53333

-- (4.52 secs, 693969028 bytes)

Problema de las jarras

PorJosé A. Alonso 18-mayo-201626-marzo-2022

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.

Definir, mediante búsqueda en espacio de estados, la función

   jarras :: (Int,Int,Int) -> [[(Int,Int)]]

1	jarras :: (Int,Int,Int) -> [[(Int,Int)]]

tal (jarras (a,b,c)) es la lista de las soluciones del problema de las
jarras (a,b,c). Por ejemplo,

   λ> take 2 (map snd (sort [(length xs,xs) | xs <- jarras (4,3,2)]))
   [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

λ> take 2 (map snd (sort [(length xs,xs) | xs <- jarras (4,3,2)]))

[[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],

[(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:

(0,0) se inicia con las dos jarras vacías,
(4,0) se llena la jarra de 4 con el grifo,
(1,3) se llena la de 3 con la de 4,
(1,0) se vacía la de 3,
(0,1) se pasa el contenido de la primera a la segunda,
(4,1) se llena la primera con el grifo,
(2,3) se llena la segunda con la primera.

Otros ejemplos

   λ> (snd . head . sort) [(length xs,xs) | xs <- jarras (15,10,5)]
   [(0,0),(15,0),(5,10)]
   λ> jarras (15,10,4)
   []

λ> (snd . head . sort) [(length xs,xs) | xs <- jarras (15,10,5)]

[(0,0),(15,0),(5,10)]

λ> jarras (15,10,4)

[]

Nota: Las librerías necesarias se encuentran en la página de códigos.

Soluciones

import I1M.BusquedaEnEspaciosDeEstados

-- Un problema queda determinado por las capacidades de las dos jarras y
-- el contenido que se desea lograr 

-- Un estado es una lista de dos números. El primero es el contenido de
-- la jarra de 4 litros y el segundo el de la de 3 litros. 
type EstadoJarras = (Int,Int)

inicialJarras :: EstadoJarras
inicialJarras = (0,0)

esFinalJarras :: (Int,Int,Int) -> EstadoJarras -> Bool
esFinalJarras (_,_,c) (x,_) = x == c

sucesoresEjarras :: (Int,Int,Int) -> EstadoJarras -> [EstadoJarras]
sucesoresEjarras (a,b,_) (x,y) =
    [(a,y) | x < a] ++
    [(x,b) | y < b] ++
    [(0,y) | x > 0] ++
    [(x,0) | y > 0] ++
    [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++
    [(x-(b-y),b) | x > 0, y < b, x + y > b] ++
    [(x+y,0) | y > 0, x + y <= a] ++ 
    [(0,x+y) | x > 0, x + y <= b]

-- Los nodos son las soluciones parciales
type NodoJarras = [EstadoJarras]

inicialNjarras :: NodoJarras
inicialNjarras = [inicialJarras]

esFinalNjarras :: (Int,Int,Int) -> NodoJarras -> Bool
esFinalNjarras p (e:_) = esFinalJarras p e

sucesoresNjarras :: (Int,Int,Int) -> NodoJarras -> [NodoJarras]
sucesoresNjarras p n@(e:es) =
    [e':n | e' <- sucesoresEjarras p e,
            e' `notElem` n]

solucionesJarras :: (Int,Int,Int) -> [NodoJarras]
solucionesJarras p = buscaEE (sucesoresNjarras p)
                             (esFinalNjarras p)
                             inicialNjarras

jarras :: (Int,Int,Int) -> [[(Int,Int)]]
jarras p = map reverse (solucionesJarras p)

import I1M.BusquedaEnEspaciosDeEstados

-- Un problema queda determinado por las capacidades de las dos jarras y

-- el contenido que se desea lograr

-- Un estado es una lista de dos números. El primero es el contenido de

-- la jarra de 4 litros y el segundo el de la de 3 litros.

type EstadoJarras = (Int,Int)

inicialJarras :: EstadoJarras

inicialJarras = (0,0)

esFinalJarras :: (Int,Int,Int) -> EstadoJarras -> Bool

esFinalJarras (_,_,c) (x,_) = x == c

sucesoresEjarras :: (Int,Int,Int) -> EstadoJarras -> [EstadoJarras]

sucesoresEjarras (a,b,_) (x,y) =

[(a,y) | x < a] ++

[(x,b) | y < b] ++

[(0,y) | x > 0] ++

[(x,0) | y > 0] ++

[(a,y-(a-x)) | x < a, y > 0, x + y > a] ++

[(x-(b-y),b) | x > 0, y < b, x + y > b] ++

[(x+y,0) | y > 0, x + y <= a] ++

[(0,x+y) | x > 0, x + y <= b]

-- Los nodos son las soluciones parciales

type NodoJarras = [EstadoJarras]

inicialNjarras :: NodoJarras

inicialNjarras = [inicialJarras]

esFinalNjarras :: (Int,Int,Int) -> NodoJarras -> Bool

esFinalNjarras p (e:_) = esFinalJarras p e

sucesoresNjarras :: (Int,Int,Int) -> NodoJarras -> [NodoJarras]

sucesoresNjarras p n@(e:es) =

[e':n | e' <- sucesoresEjarras p e,

e' `notElem` n]

solucionesJarras :: (Int,Int,Int) -> [NodoJarras]

solucionesJarras p = buscaEE (sucesoresNjarras p)

(esFinalNjarras p)

inicialNjarras

jarras :: (Int,Int,Int) -> [[(Int,Int)]]

jarras p = map reverse (solucionesJarras p)

Problema del dominó

PorJosé A. Alonso 17-mayo-201626-marzo-2022

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir, mediante búsqueda en espacio de estados, la función

   domino :: [(Int,Int)] -> [[(Int,Int)]]

1	domino :: [(Int,Int)] -> [[(Int,Int)]]

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

   ghci> domino [(1,2),(2,3),(1,4)]
   [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]
   ghci> domino [(1,2),(1,1),(1,4)]
   [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]
   ghci> domino [(1,2),(3,4),(2,3)]
   [[(1,2),(2,3),(3,4)]]
   ghci> domino [(1,2),(2,3),(5,4)]
   []
   ghci> domino [(x,y) | x <- [1..2], y <- [x..2]]
   [[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]
   λ> [(x,y) | x <- [1..3], y <- [x..3]]
   [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
   λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])
   [(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]
   [(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]
   [(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]
   [(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]
   [(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]
   [(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]
   [(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]
   [(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]
   [(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]
   ghci> length (domino [(x,y) | x <- [1..4], y <- [x..4]])
   0

ghci> domino [(1,2),(2,3),(1,4)]

[[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]

ghci> domino [(1,2),(1,1),(1,4)]

[[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]

ghci> domino [(1,2),(3,4),(2,3)]

[[(1,2),(2,3),(3,4)]]

ghci> domino [(1,2),(2,3),(5,4)]

[]

ghci> domino [(x,y) | x <- [1..2], y <- [x..2]]

[[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]

λ> [(x,y) | x <- [1..3], y <- [x..3]]

[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])

[(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]

[(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]

[(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]

[(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]

[(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]

[(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]

[(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]

[(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]

[(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]

ghci> length (domino [(x,y) | x <- [1..4], y <- [x..4]])

Nota: Las librerías necesarias se encuentran en la página de códigos.

Soluciones

import I1M.BusquedaEnEspaciosDeEstados (buscaEE)
import Data.List (delete)

type Ficha  = (Int,Int)

-- Los estados son los pares formados por la listas sin colocar y las
-- colocadas. 
type EstadoDomino = ([Ficha],[Ficha])

inicialDomino :: [Ficha] -> EstadoDomino
inicialDomino fs = (fs,[])

esFinalDomino :: EstadoDomino -> Bool
esFinalDomino (fs,_) = null fs 

sucesoresDomino :: EstadoDomino -> [EstadoDomino]
sucesoresDomino (fs,[]) = [(delete f fs, [f]) | f <- fs]
sucesoresDomino (fs,n@((x,y):qs)) =
    [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u /= v, v == x] ++
    [(delete (u,v) fs,(v,u):n) | (u,v) <- fs, u /= v, u == x] ++
    [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u == v, u == x] 

solucionesDomino :: [Ficha] -> [EstadoDomino]
solucionesDomino ps = buscaEE sucesoresDomino
                              esFinalDomino         
                              (inicialDomino ps)

domino :: [(Int,Int)] -> [[(Int,Int)]]
domino ps = map snd (solucionesDomino ps)

import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

import Data.List (delete)

type Ficha = (Int,Int)

-- Los estados son los pares formados por la listas sin colocar y las

-- colocadas.

type EstadoDomino = ([Ficha],[Ficha])

inicialDomino :: [Ficha] -> EstadoDomino

inicialDomino fs = (fs,[])

esFinalDomino :: EstadoDomino -> Bool

esFinalDomino (fs,_) = null fs

sucesoresDomino :: EstadoDomino -> [EstadoDomino]

sucesoresDomino (fs,[]) = [(delete f fs, [f]) | f <- fs]

sucesoresDomino (fs,n@((x,y):qs)) =

[(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u /= v, v == x] ++

[(delete (u,v) fs,(v,u):n) | (u,v) <- fs, u /= v, u == x] ++

[(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u == v, u == x]

solucionesDomino :: [Ficha] -> [EstadoDomino]

solucionesDomino ps = buscaEE sucesoresDomino

esFinalDomino

(inicialDomino ps)

domino :: [(Int,Int)] -> [[(Int,Int)]]

domino ps = map snd (solucionesDomino ps)

Sucesión duplicadora

PorJosé A. Alonso 16-mayo-201625-abril-2021

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

3 = 2*1 +1

6 = 2*3

13 = 2*6 +1

Definir la función

   duplicadora :: Integer -> [Integer]

1	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

duplicadora 13 == [1,3,6,13]

duplicadora 17 == [1,2,4,8,17]

length (duplicadora (10^40000)) == 132878

Soluciones

-- 1ª solució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)

-- 1ª solució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)

Problema de las puertas

PorJosé A. Alonso 13-mayo-201625-abril-2021

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puestas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

Inicialmente todas las puertas están cerradas.
El primer camarero cambia de estado las puertas de todas las habitaciones.
El segundo cambia de estado de las puertas de las habitaciones pares.
El tercero cambia de estado todas las puertas que son múltiplos de 3.
El cuarto cambia de estado todas las puertas que son múltiplos de 4
Así, hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

   Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
   --------+----------+----------+----------+----------+----------
   Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
   Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
   Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
   Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
   Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
   Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

--------+----------+----------+----------+----------+----------

Los estados de las puertas se representan por el siguiente tipo de datos

   data Estado = Abierta | Cerrada 
                 deriving (Eq, Show)

1 2	data Estado = Abierta \| Cerrada deriving (Eq, Show)

Definir la función

   final :: Int -> [Estado]

1	final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después
de que hayan pasado los n camareros. Por
ejemplo,

   ghci> final 5
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
   ghci> final 7
   [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

ghci> final 5

[Abierta,Cerrada,Cerrada,Abierta,Cerrada]

ghci> final 7

[Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Soluciones

-- 1ª solución
-- ===========

data Estado = Abierta | Cerrada 
              deriving (Eq, Show)
 
cambia Abierta = Cerrada
cambia Cerrada = Abierta

-- (inicial n) es el estado inicial para el problema de las n
-- habitaciones. Por ejemplo,
--    inicial 5  ==  [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]
inicial :: Int -> [Estado]
inicial n = replicate n Cerrada

-- (pase k es) es la lista de los estados de las puertas después de pasar el
-- camarero k que las encuentra en los estados es. Por ejemplo,
--    ghci> pase 1 (inicial 5)
--    [Abierta,Abierta,Abierta,Abierta,Abierta]
--    ghci> pase 2 it
--    [Abierta,Cerrada,Abierta,Cerrada,Abierta]
--    ghci> pase 3 it
--    [Abierta,Cerrada,Cerrada,Cerrada,Abierta]
--    ghci> pase 4 it
--    [Abierta,Cerrada,Cerrada,Abierta,Abierta]
--    ghci> pase 5 it
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
pase :: [Estado] -> Int -> [Estado] 
pase es k = zipWith cambiaK  es[1..] 
  where cambiaK e n | n `mod` k == 0 = cambia e
                    | otherwise      = e
               
final :: Int -> [Estado]
final n = aux [1..n] (inicial n) 
    where aux []     es = es  
          aux (k:ks) es = aux ks (pase es k)

-- 2ª solución (con foldl')
-- ========================

final2 :: Int -> [Estado]
final2 n = foldl pase (inicial n) [1..n] 

-- 3ª definición (basada en los cambios de cada posición)
-- ======================================================

final3 :: Int -> [Estado]
final3 n = map f [1..n]
    where f x | even (length (divisores x)) = Cerrada
              | otherwise                   = Abierta

divisores :: Int -> [Int]
divisores n = [x| x <- [1..n], n `mod` x == 0]

-- 4ª definición (basada en posiciones de abiertas)
-- ================================================

-- En primer lugar, vamos a determinar la lista de las posiciones
-- (comenzando a contar en 1) de las puertas que quedan abierta en el
-- problema de las n puertas. 
posicionesAbiertas :: Int -> [Int]
posicionesAbiertas n = 
    [x | (x,y) <- zip [1..] (final n), y == Abierta]

-- Al calcularlas,
--    ghci> posicionesAbiertas 200
--    [1,4,9,16,25,36,49,64,81,100,121,144,169,196]
-- Se observa las que quedan abiertas son las que sus posiciones son
-- cuadrados perfectos. Usando esta observación se construye la
-- siguiente definición

final4 :: Int -> [Estado]
final4 n = aux [1..n] [k*k | k <- [1..]] 
    where aux (x:xs) (y:ys) | x == y  =  Abierta : aux xs ys
          aux (x:xs) ys               =  Cerrada : aux xs ys
          aux []     _                =  []

-- 1ª solución

-- ===========

data Estado = Abierta | Cerrada

deriving (Eq, Show)

cambia Abierta = Cerrada

cambia Cerrada = Abierta

-- (inicial n) es el estado inicial para el problema de las n

-- habitaciones. Por ejemplo,

-- inicial 5 == [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]

inicial :: Int -> [Estado]

inicial n = replicate n Cerrada

-- (pase k es) es la lista de los estados de las puertas después de pasar el

-- camarero k que las encuentra en los estados es. Por ejemplo,

-- ghci> pase 1 (inicial 5)

-- [Abierta,Abierta,Abierta,Abierta,Abierta]

-- ghci> pase 2 it

-- [Abierta,Cerrada,Abierta,Cerrada,Abierta]

-- ghci> pase 3 it

-- [Abierta,Cerrada,Cerrada,Cerrada,Abierta]

-- ghci> pase 4 it

-- [Abierta,Cerrada,Cerrada,Abierta,Abierta]

-- ghci> pase 5 it

-- [Abierta,Cerrada,Cerrada,Abierta,Cerrada]

pase :: [Estado] -> Int -> [Estado]

pase es k = zipWith cambiaK es[1..]

where cambiaK e n | n `mod` k == 0 = cambia e

| otherwise = e

final :: Int -> [Estado]

final n = aux [1..n] (inicial n)

where aux [] es = es

aux (k:ks) es = aux ks (pase es k)

-- 2ª solución (con foldl')

-- ========================

final2 :: Int -> [Estado]

final2 n = foldl pase (inicial n) [1..n]

-- 3ª definición (basada en los cambios de cada posición)

-- ======================================================

final3 :: Int -> [Estado]

final3 n = map f [1..n]

where f x | even (length (divisores x)) = Cerrada

| otherwise = Abierta

divisores :: Int -> [Int]

divisores n = [x| x <- [1..n], n `mod` x == 0]

-- 4ª definición (basada en posiciones de abiertas)

-- ================================================

-- En primer lugar, vamos a determinar la lista de las posiciones

-- (comenzando a contar en 1) de las puertas que quedan abierta en el

-- problema de las n puertas.

posicionesAbiertas :: Int -> [Int]

posicionesAbiertas n =

[x | (x,y) <- zip [1..] (final n), y == Abierta]

-- Al calcularlas,

-- ghci> posicionesAbiertas 200

-- [1,4,9,16,25,36,49,64,81,100,121,144,169,196]

-- Se observa las que quedan abiertas son las que sus posiciones son

-- cuadrados perfectos. Usando esta observación se construye la

-- siguiente definición

final4 :: Int -> [Estado]

final4 n = aux [1..n] [k*k | k <- [1..]]

where aux (x:xs) (y:ys) | x == y = Abierta : aux xs ys

aux (x:xs) ys = Cerrada : aux xs ys

aux [] _ = []

Juego de bloques con letras

PorJosé A. Alonso 12-mayo-201619-mayo-2016

Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.

Definir la función

   soluciones :: [String] -> String -> [[String]]

1	soluciones :: [String] -> String -> [[String]]

tal que (soluciones bs cs) es la lista de las soluciones del juego de los bloque usando los bloques bs (cada bloque es una cadena de dos letras mayúsculas) para formar la palabra cs. Por ejemplo,

   ghci> soluciones ["AB","NO","OA"] "ANA"
   [["AB","NO","OA"],["OA","NO","AB"]]
   ghci> soluciones ["AB","NE","OA"] "Bea"
   [["AB","NE","OA"]]
   ghci> soluciones ["AB","NE","OA"] "EvA"
   []
   ghci> soluciones ["AB","NO","OA","NC"] "ANA"
   [["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]
   ghci> soluciones ["AB","NO","OA","NC"] "Anca"
   [["AB","NO","NC","OA"],["OA","NO","NC","AB"]]
   ghci> soluciones (["AB","NO","OA"] ++ replicate (10^6) "PQ") "ANA"
   [["AB","NO","OA"],["OA","NO","AB"]]

ghci> soluciones ["AB","NO","OA"] "ANA"

[["AB","NO","OA"],["OA","NO","AB"]]

ghci> soluciones ["AB","NE","OA"] "Bea"

[["AB","NE","OA"]]

ghci> soluciones ["AB","NE","OA"] "EvA"

[]

ghci> soluciones ["AB","NO","OA","NC"] "ANA"

[["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]

ghci> soluciones ["AB","NO","OA","NC"] "Anca"

[["AB","NO","NC","OA"],["OA","NO","NC","AB"]]

ghci> soluciones (["AB","NO","OA"] ++ replicate (10^6) "PQ") "ANA"

[["AB","NO","OA"],["OA","NO","AB"]]

Soluciones

import Data.List (delete)
import Data.Char (toUpper)

soluciones :: [String] -> String -> [[String]]
soluciones _ []      = [[]]
soluciones bs (c:cs) = [b:rs | b <- bs, 
                               toUpper c `elem` b,
                               rs <- soluciones (delete b bs) cs]

import Data.List (delete)

import Data.Char (toUpper)

soluciones :: [String] -> String -> [[String]]

soluciones _ [] = [[]]

soluciones bs (c:cs) = [b:rs | b <- bs,

toUpper c `elem` b,

rs <- soluciones (delete b bs) cs]

Densidad de números no monótonos

PorJosé A. Alonso 11-mayo-201618-mayo-2016

Un número entero positivo se dice que es

creciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 134479.
decreciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 664210.
no monótono si no es creciente ni decreciente; por ejemplo, 155369.

Para cada entero positivo n, la densidad números no monótonos hasta n es el cociente entre la cantidad de n números no monótonos entre menores o iguales que n y el número n. Por ejemplo, hasta 150 hay 19 números no monótonos (101, 102, 103, 104, 105, 106, 107, 108, 109, 120, 121, 130, 131, 132, 140, 141, 142, 143 y 150); por tanto, la densidad hasta 150 es 19/150 = 0.12666667

Definir las siguientes funciones

   densidad              :: Integer -> Float
   menorConDensidadMayor :: Float -> Integer

1 2	densidad :: Integer -> Float menorConDensidadMayor :: Float -> Integer

tales que

(densidad n) es la densidad de números no monótonos hasta n. Por ejemplo,

     densidad 100  ==  0.0
     densidad 200  ==  0.265
     densidad 400  ==  0.4375
     densidad 800  ==  0.53375

densidad 100 == 0.0

densidad 200 == 0.265

densidad 400 == 0.4375

densidad 800 == 0.53375

(menorConDensidadMayor x) es el menor número n tal que la densidad de números no monótonos hasta n es mayor o igual que x. Por ejemplo,

     menorConDensidadMayor 0.5   ==  538
     densidad 537                ==  0.49906892
     densidad 538                ==  0.5
     menorConDensidadMayor 0.9   ==  21780
     densidad 21779              ==  0.8999954
     densidad 21780              ==  0.9
     menorConDensidadMayor 0.99  ==  1586996

menorConDensidadMayor 0.5 == 538

densidad 537 == 0.49906892

densidad 538 == 0.5

menorConDensidadMayor 0.9 == 21780

densidad 21779 == 0.8999954

densidad 21780 == 0.9

menorConDensidadMayor 0.99 == 1586996

Soluciones

import Data.List (genericLength, sort)

-- 1ª definición
-- =============

densidad :: Integer -> Float
densidad n = 
    genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n

esNoMonotono :: Integer -> Bool
esNoMonotono x = not (esCreciente x) && not (esDecreciente x)

esCreciente :: Integer -> Bool
esCreciente x = show x == sort (show x)

esDecreciente :: Integer -> Bool
esDecreciente x = reverse (show x) == sort (show x)

menorConDensidadMayor :: Float -> Integer 
menorConDensidadMayor x  = 
    buscaProporcion x (filter esNoMonotono [1..])
    where buscaProporcion x = 
              snd . head . filter condicion . zip [1..]
              where condicion (a,b) = a >= x * fromIntegral b

import Data.List (genericLength, sort)

-- 1ª definición

-- =============

densidad :: Integer -> Float

densidad n =

genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n

esNoMonotono :: Integer -> Bool

esNoMonotono x = not (esCreciente x) && not (esDecreciente x)

esCreciente :: Integer -> Bool

esCreciente x = show x == sort (show x)

esDecreciente :: Integer -> Bool

esDecreciente x = reverse (show x) == sort (show x)

menorConDensidadMayor :: Float -> Integer

menorConDensidadMayor x =

buscaProporcion x (filter esNoMonotono [1..])

where buscaProporcion x =

snd . head . filter condicion . zip [1..]

where condicion (a,b) = a >= x * fromIntegral b

Sucesión fractal

PorJosé A. Alonso 10-mayo-201625-abril-2021

La sucesión fractal

   0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 
   10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

1 2	0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

los términos pares forman la sucesión de los números naturales

     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

1	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

los términos impares forman la misma sucesión original

     0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

1	0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

   sucFractal     :: [Integer]
   sumaSucFractal :: Integer -> Integer

1 2	sucFractal :: [Integer] sumaSucFractal :: Integer -> Integer

tales que

sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

     take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
     sucFractal !! 30     == 15
     sucFractal !! (10^7) == 5000000

take 20 sucFractal == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]

sucFractal !! 30 == 15

sucFractal !! (10^7) == 5000000

(sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

     sumaSucFractal 10      ==  13
     sumaSucFractal (10^5)  == 1666617368
     sumaSucFractal (10^10) == 16666666661668691669
     sumaSucFractal (10^15) == 166666666666666166673722792954
     sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
     length (show (sumaSucFractal (10^15000))) == 30000
     sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

sumaSucFractal 10 == 13

sumaSucFractal (10^5) == 1666617368

sumaSucFractal (10^10) == 16666666661668691669

sumaSucFractal (10^15) == 166666666666666166673722792954

sumaSucFractal (10^20) == 1666666666666666666616666684103392376198

length (show (sumaSucFractal (10^15000))) == 30000

sumaSucFractal (10^15000) `mod` (10^9) == 455972157

Soluciones

-- 1ª definición de sucFractal
-- ===========================

sucFractal1 :: [Integer]
sucFractal1 = 
    map termino [0..]

-- (termino n) es el término n de la secuencia anterior. Por ejemplo,
--   termino 0            ==  0
--   termino 1            ==  0
--   map termino [0..10]  ==  [0,0,1,0,2,1,3,0,4,2,5]
termino :: Integer -> Integer
termino 0 = 0
termino n 
    | even n    = n `div` 2
    | otherwise = termino (n `div` 2)

-- 2ª definición de sucFractal
-- ===========================

sucFractal2 :: [Integer]
sucFractal2 =
    0 : 0 : mezcla [1..] (tail sucFractal2)

-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas
-- xs e ys. Por ejemplo,
--    take 10 (mezcla [0,2..] [0,-2..])  ==  [0,0,2,-2,4,-4,6,-6,8,-8]
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla (x:xs) (y:ys) =
    x:y:mezcla xs ys

-- Comparación de eficiencia de definiciones de sucFractal
-- =======================================================

--    λ> sum (take (10^6) sucFractal1)
--    166666169612
--    (5.56 secs, 842,863,264 bytes)
--    λ> sum (take (10^6) sucFractal2)
--    166666169612
--    (1.81 secs, 306,262,616 bytes)

-- En lo que sigue usaremos la 2ª definición
sucFractal :: [Integer]
sucFractal = sucFractal2

-- 1ª definición de sumaSucFractal
-- ===============================

sumaSucFractal1 :: Integer -> Integer
sumaSucFractal1 n =
    sum (map termino [0..n-1])

-- 2ª definición de sumaSucFractal
-- ===============================

sumaSucFractal2 :: Integer -> Integer
sumaSucFractal2 n =
    sum (take (fromIntegral n) sucFractal)

-- 3ª definición de sumaSucFractal
-- ===============================

sumaSucFractal3 :: Integer -> Integer
sumaSucFractal3 0 = 0
sumaSucFractal3 1 = 0
sumaSucFractal3 n
    | even n    = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)
    | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)
    where sumaN n = (n*(n-1)) `div` 2

-- Comparación de eficiencia de definiciones de sumaSucFractal
-- ===========================================================

--    λ> sumaSucFractal1 (10^6)
--    166666169612
--    (5.25 secs, 810,622,504 bytes)
--    λ> sumaSucFractal2 (10^6)
--    166666169612
--    (1.72 secs, 286,444,048 bytes)
--    λ> sumaSucFractal3 (10^6)
--    166666169612
--    (0.01 secs, 0 bytes)
--    
--    λ> sumaSucFractal2 (10^7)
--    16666661685034
--    (17.49 secs, 3,021,580,920 bytes)
--    λ> sumaSucFractal3 (10^7)
--    16666661685034
--    (0.01 secs, 0 bytes)

-- 1ª definición de sucFractal

-- ===========================

sucFractal1 :: [Integer]

sucFractal1 =

map termino [0..]

-- (termino n) es el término n de la secuencia anterior. Por ejemplo,

-- termino 0 == 0

-- termino 1 == 0

-- map termino [0..10] == [0,0,1,0,2,1,3,0,4,2,5]

termino :: Integer -> Integer

termino 0 = 0

termino n

| even n = n `div` 2

| otherwise = termino (n `div` 2)

-- 2ª definición de sucFractal

-- ===========================

sucFractal2 :: [Integer]

sucFractal2 =

0 : 0 : mezcla [1..] (tail sucFractal2)

-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas

-- xs e ys. Por ejemplo,

-- take 10 (mezcla [0,2..] [0,-2..]) == [0,0,2,-2,4,-4,6,-6,8,-8]

mezcla :: [Integer] -> [Integer] -> [Integer]

mezcla (x:xs) (y:ys) =

x:y:mezcla xs ys

-- Comparación de eficiencia de definiciones de sucFractal

-- =======================================================

-- λ> sum (take (10^6) sucFractal1)

-- 166666169612

-- (5.56 secs, 842,863,264 bytes)

-- λ> sum (take (10^6) sucFractal2)

-- 166666169612

-- (1.81 secs, 306,262,616 bytes)

-- En lo que sigue usaremos la 2ª definición

sucFractal :: [Integer]

sucFractal = sucFractal2

-- 1ª definición de sumaSucFractal

-- ===============================

sumaSucFractal1 :: Integer -> Integer

sumaSucFractal1 n =

sum (map termino [0..n-1])

-- 2ª definición de sumaSucFractal

-- ===============================

sumaSucFractal2 :: Integer -> Integer

sumaSucFractal2 n =

sum (take (fromIntegral n) sucFractal)

-- 3ª definición de sumaSucFractal

-- ===============================

sumaSucFractal3 :: Integer -> Integer

sumaSucFractal3 0 = 0

sumaSucFractal3 1 = 0

sumaSucFractal3 n

| even n = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)

| otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)

where sumaN n = (n*(n-1)) `div` 2

-- Comparación de eficiencia de definiciones de sumaSucFractal

-- ===========================================================

-- λ> sumaSucFractal1 (10^6)

-- 166666169612

-- (5.25 secs, 810,622,504 bytes)

-- λ> sumaSucFractal2 (10^6)

-- 166666169612

-- (1.72 secs, 286,444,048 bytes)

-- λ> sumaSucFractal3 (10^6)

-- 166666169612

-- (0.01 secs, 0 bytes)

-- λ> sumaSucFractal2 (10^7)

-- 16666661685034

-- (17.49 secs, 3,021,580,920 bytes)

-- λ> sumaSucFractal3 (10^7)

-- 16666661685034

-- (0.01 secs, 0 bytes)

Referencia

Fractal sequences and restricted Nim por Lionel Levine.

Conjuntos de primos emparejables

PorJosé A. Alonso 9-mayo-201625-abril-2021

Un conjunto de primos emparejables es un conjunto S de números primos tales que al concatenar cualquier par de elementos de S se obtiene un número primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.

Definir la función

   emparejables :: Integer -> Integer -> [[Integer]]

1	emparejables :: Integer -> Integer -> [[Integer]]

tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,

   take 5 (emparejables 2   10)  ==  [[3,7]]
   take 5 (emparejables 3   10)  ==  []
   take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]
   take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]
   take 5 (emparejables 4  100)  ==  []
   take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]

take 5 (emparejables 2 10) == [[3,7]]

take 5 (emparejables 3 10) == []

take 5 (emparejables 2 100) == [[3,7],[3,11],[3,17],[3,31],[3,37]]

take 5 (emparejables 3 100) == [[3,37,67],[7,19,97]]

take 5 (emparejables 4 100) == []

take 5 (emparejables 4 1000) == [[3,7,109,673],[23,311,677,827]]

Soluciones

import Data.Numbers.Primes (primes, isPrime)
import Data.List (nub, sort)
import qualified Data.Set as S

-- 1ª definición
-- =============

emparejables :: Integer -> Integer -> [[Integer]]
emparejables 0 _ = [[]]
emparejables n m = 
    nub [sort (x:xs) | x <- takeWhile (<=m) primes,
                       xs <- xss,
                       all (x `emparejable`) xs]
    where xss = emparejables (n-1) m

emparejable :: Integer -> Integer -> Bool
emparejable x y =
    isPrime (concatenacion x y) &&
    isPrime (concatenacion y x)

concatenacion :: Integer -> Integer -> Integer
concatenacion x y =
    read (show x ++ show y)

-- 2ª definición
-- =============

emparejables2 :: Integer -> Integer -> [[Integer]]
emparejables2 n m = map reverse (aux n m)
    where aux 1 m = [[x] | x <- takeWhile (<=m) primes]
          aux n m = 
              [p:ys | ys@(x:xs) <- xss,
                      p <- dropWhile (<x) ps,
                      all (p `emparejable`) ys]
              where ps  = takeWhile (<=m) primes
                    xss = aux (n-1) m

-- 3ª definición
-- =============

emparejables3 :: Integer -> Integer -> [[Integer]]
emparejables3 n m = map S.toList (aux n m)
    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]
          aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,
                                     xs <- xss,
                                     all (x `emparejable`) xs]
              where xss = aux (n-1) m

-- 2ª definición
-- =============

emparejables4 :: Integer -> Integer -> [[Integer]]
emparejables4 n m = map S.toList (aux n m)
    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]
          aux n m = 
              [S.insert p ys | ys <- xss,
                               let (x,xs) = S.deleteFindMax ys,
                               p <- dropWhile (<x) ps,
                               all (p `emparejable`) ys]
              where ps  = takeWhile (<=m) primes
                    xss = aux (n-1) m

-- Comparación de eficiencia
-- =========================

--    λ> head (emparejables 4 1000)
--    [3,7,109,673]
--    (20.36 secs, 11,781,891,120 bytes)
--    
--    λ> head (emparejables2 4 1000)
--    [3,7,109,673]
--    (0.02 secs, 0 bytes)
--    
--    λ> head (emparejables3 4 1000)
--    [3,7,109,673]
--    (38.04 secs, 21,542,334,024 bytes)
--    
--    λ> head (emparejables4 4 1000)
--    [3,7,109,673]
--    (0.03 secs, 0 bytes)

import Data.Numbers.Primes (primes, isPrime)

import Data.List (nub, sort)

import qualified Data.Set as S

-- 1ª definición

-- =============

emparejables :: Integer -> Integer -> [[Integer]]

emparejables 0 _ = [[]]

emparejables n m =

nub [sort (x:xs) | x <- takeWhile (<=m) primes,

xs <- xss,

all (x `emparejable`) xs]

where xss = emparejables (n-1) m

emparejable :: Integer -> Integer -> Bool

emparejable x y =

isPrime (concatenacion x y) &&

isPrime (concatenacion y x)

concatenacion :: Integer -> Integer -> Integer

concatenacion x y =

read (show x ++ show y)

-- 2ª definición

-- =============

emparejables2 :: Integer -> Integer -> [[Integer]]

emparejables2 n m = map reverse (aux n m)

where aux 1 m = [[x] | x <- takeWhile (<=m) primes]

aux n m =

[p:ys | ys@(x:xs) <- xss,

p <- dropWhile (<x) ps,

all (p `emparejable`) ys]

where ps = takeWhile (<=m) primes

xss = aux (n-1) m

-- 3ª definición

-- =============

emparejables3 :: Integer -> Integer -> [[Integer]]

emparejables3 n m = map S.toList (aux n m)

where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]

aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,

xs <- xss,

all (x `emparejable`) xs]

where xss = aux (n-1) m

-- 2ª definición

-- =============

emparejables4 :: Integer -> Integer -> [[Integer]]

emparejables4 n m = map S.toList (aux n m)

where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]

aux n m =

[S.insert p ys | ys <- xss,

let (x,xs) = S.deleteFindMax ys,

p <- dropWhile (<x) ps,

all (p `emparejable`) ys]

where ps = takeWhile (<=m) primes

xss = aux (n-1) m

-- Comparación de eficiencia

-- =========================

-- λ> head (emparejables 4 1000)

-- [3,7,109,673]

-- (20.36 secs, 11,781,891,120 bytes)

-- λ> head (emparejables2 4 1000)

-- [3,7,109,673]

-- (0.02 secs, 0 bytes)

-- λ> head (emparejables3 4 1000)

-- [3,7,109,673]

-- (38.04 secs, 21,542,334,024 bytes)

-- λ> head (emparejables4 4 1000)

-- [3,7,109,673]

-- (0.03 secs, 0 bytes)

Cadenas de divisores

PorJosé A. Alonso 6-mayo-201625-abril-2021

Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].

Definir la función

   cadenasDivisores :: Int -> [[Int]]

1	cadenasDivisores :: Int -> [[Int]]

tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,

   λ> cadenasDivisores 12
   [[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]
   λ> length (cadenaDivisores 48)
   48
   λ> length (cadenaDivisores 120)
   132

λ> cadenasDivisores 12

[[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]

λ> length (cadenaDivisores 48)

λ> length (cadenaDivisores 120)

132

Soluciones

import Data.List (sort)
import Data.Numbers.Primes (isPrime)

-- 1ª definición
-- =============

cadenasDivisores :: Int -> [[Int]]
cadenasDivisores n = sort (extiendeLista [[n]])
    where extiendeLista []           = []
          extiendeLista ((1:xs):yss) = xs : extiendeLista yss
          extiendeLista ((x:xs):yss) =
              extiendeLista ([y:x:xs | y <- divisores x] ++ yss)

-- (divisores x) es la lista decreciente de los divisores de x distintos
-- de x. Por ejemplo,
--    divisores 12  ==  [6,4,3,2,1]
divisores :: Int -> [Int]
divisores x = 
    [y | y <- [a,a-1..1], x `mod` y == 0]
    where a = x `div` 2

-- 2ª definición
-- =============

cadenasDivisores2 :: Int -> [[Int]]
cadenasDivisores2 = sort . aux
    where aux 1 = [[]]
          aux n = [xs ++ [n] | xs <- concatMap aux (divisores n)]

-- 3ª definición
-- =============

cadenasDivisores3 :: Int -> [[Int]]
cadenasDivisores3 = sort . map reverse . aux
    where aux 1 = [[]]
          aux n = map (n:) (concatMap aux (divisores3 n))

-- (divisores3 x) es la lista creciente de los divisores de x distintos
-- de x. Por ejemplo,
--    divisores3 12  ==  [1,2,3,4,6]
divisores3 :: Int -> [Int]
divisores3 x = 
    [y | y <- [1..a], x `mod` y == 0]
    where a = x `div` 2

-- 1ª definición de nCadenasDivisores
-- ==================================

nCadenasDivisores1 :: Int -> Int
nCadenasDivisores1 = length . cadenasDivisores

-- 2ª definición de nCadenasDivisores
-- ==================================

nCadenasDivisores2 :: Int -> Int
nCadenasDivisores2 1 = 1
nCadenasDivisores2 n = 
    sum [nCadenasDivisores2 x | x <- divisores n]

import Data.List (sort)

import Data.Numbers.Primes (isPrime)

-- 1ª definición

-- =============

cadenasDivisores :: Int -> [[Int]]

cadenasDivisores n = sort (extiendeLista [[n]])

where extiendeLista [] = []

extiendeLista ((1:xs):yss) = xs : extiendeLista yss

extiendeLista ((x:xs):yss) =

extiendeLista ([y:x:xs | y <- divisores x] ++ yss)

-- (divisores x) es la lista decreciente de los divisores de x distintos

-- de x. Por ejemplo,

-- divisores 12 == [6,4,3,2,1]

divisores :: Int -> [Int]

divisores x =

[y | y <- [a,a-1..1], x `mod` y == 0]

where a = x `div` 2

-- 2ª definición

-- =============

cadenasDivisores2 :: Int -> [[Int]]

cadenasDivisores2 = sort . aux

where aux 1 = [[]]

aux n = [xs ++ [n] | xs <- concatMap aux (divisores n)]

-- 3ª definición

-- =============

cadenasDivisores3 :: Int -> [[Int]]

cadenasDivisores3 = sort . map reverse . aux

where aux 1 = [[]]

aux n = map (n:) (concatMap aux (divisores3 n))

-- (divisores3 x) es la lista creciente de los divisores de x distintos

-- de x. Por ejemplo,

-- divisores3 12 == [1,2,3,4,6]

divisores3 :: Int -> [Int]

divisores3 x =

[y | y <- [1..a], x `mod` y == 0]

where a = x `div` 2

-- 1ª definición de nCadenasDivisores

-- ==================================

nCadenasDivisores1 :: Int -> Int

nCadenasDivisores1 = length . cadenasDivisores

-- 2ª definición de nCadenasDivisores

-- ==================================

nCadenasDivisores2 :: Int -> Int

nCadenasDivisores2 1 = 1

nCadenasDivisores2 n =

sum [nCadenasDivisores2 x | x <- divisores n]

Referencias

Sucesión A163272 de OEIS.
Ordered and unordered factorizations of integers por A. Knopfmacher y M. Mays

Número de divisiones en el algoritmo de Euclides

PorJosé A. Alonso 5-mayo-201612-mayo-2016

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = b,                   si a = 0               
            = mcd (a módulo b, b), si a > b
            = mcd (a, b módulo a), si b >= a

mcd(a,b) = a, si b = 0

= b, si a = 0

= mcd (a módulo b, b), si a > b

= mcd (a, b módulo a), si b >= a

Definir la función

   mcdYdivisiones :: Int -> Int -> (Int,Int)

1	mcdYdivisiones :: Int -> Int -> (Int,Int)

tal que (mcdYdivisiones a b) es el número de divisiones usadas en el cálculo del máximo común divisor de a y b mediante el algoritmo de Euclides. Por ejemplo,

   mcdYdivisiones 252 198 == (18,4)

1	mcdYdivisiones 252 198 == (18,4)

ya que los 4 divisiones del cálculo son

     mcd 252 198
   = mcd  54 198
   = mcd  54  36
   = mcd  18  36
   = mcd  18   0

mcd 252 198

= mcd 54 198

= mcd 54 36

= mcd 18 36

= mcd 18 0

Comprobar con QuickCheck que el número de divisiones requeridas por el algoritmo de Euclides para calcular el MCD de a y b es igual o menor que cinco veces el número de dígitos de menor de los números a y b.

Soluciones

import Test.QuickCheck
import Debug.Trace 

mcdYdivisiones :: Int -> Int -> (Int,Int)
mcdYdivisiones a b = mcd a b 0
    where mcd a 0 n = (a,n)
          mcd 0 b n = (b,n)
          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)
                    | otherwise = mcd a (b `mod` a) (n+1) 

-- La propiedad es
prop_mcdYdivisiones :: Int -> Int -> Property
prop_mcdYdivisiones a b =
    a > 0 && b > 0 ==>
      n < 5 * length (show (min a b))  
    where (_,n) = mcdYdivisiones a b
                 
-- La comprobación es
--    λ> quickCheck prop_mcdYdivisiones
--    +++ OK, passed 100 tests.

-- 2ª definición (con traza)
mcdYdivisiones2 :: Int -> Int -> (Int,Int)
mcdYdivisiones2 a b = mcd a b 0
    where mcd a b n
              | trace (show a ++ ", " ++ show b) False = undefined
          mcd a 0 n = (a,n)
          mcd 0 b n = (b,n)
          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)
                    | otherwise = mcd a (b `mod` a) (n+1) 

-- Por ejemplo,
--    λ> mcdYdivisiones2 252 198
--    252, 198
--    54, 198
--    54, 36
--    18, 36
--    18, 0
--    (18,4)

import Test.QuickCheck

import Debug.Trace

mcdYdivisiones :: Int -> Int -> (Int,Int)

mcdYdivisiones a b = mcd a b 0

where mcd a 0 n = (a,n)

mcd 0 b n = (b,n)

mcd a b n | a > b = mcd (a `mod` b) b (n+1)

| otherwise = mcd a (b `mod` a) (n+1)

-- La propiedad es

prop_mcdYdivisiones :: Int -> Int -> Property

prop_mcdYdivisiones a b =

a > 0 && b > 0 ==>

n < 5 * length (show (min a b))

where (_,n) = mcdYdivisiones a b

-- La comprobación es

-- λ> quickCheck prop_mcdYdivisiones

-- +++ OK, passed 100 tests.

-- 2ª definición (con traza)

mcdYdivisiones2 :: Int -> Int -> (Int,Int)

mcdYdivisiones2 a b = mcd a b 0

where mcd a b n

| trace (show a ++ ", " ++ show b) False = undefined

mcd a 0 n = (a,n)

mcd 0 b n = (b,n)

mcd a b n | a > b = mcd (a `mod` b) b (n+1)

| otherwise = mcd a (b `mod` a) (n+1)

-- Por ejemplo,

-- λ> mcdYdivisiones2 252 198

-- 252, 198

-- 54, 198

-- 54, 36

-- 18, 36

-- 18, 0

-- (18,4)

Período de una lista

PorJosé A. Alonso 4-mayo-201625-abril-2021

El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período «abababab» es «ab» ya que «abababab» se obtiene repitiendo tres veces la lista «ab».

Definir la función

   periodo :: Eq a => [a] -> [a]

1	periodo :: Eq a => [a] -> [a]

tal que (periodo xs) es el período de xs. Por ejemplo,

   periodo "ababab"      ==  "ab"
   periodo "buenobueno"  ==  "bueno"
   periodo "oooooo"      ==  "o"
   periodo "sevilla"     ==  "sevilla"

periodo "ababab" == "ab"

periodo "buenobueno" == "bueno"

periodo "oooooo" == "o"

periodo "sevilla" == "sevilla"

Soluciones

periodo :: Eq a => [a] -> [a]
periodo xs = take n xs
    where l = length xs
          n = head [m | m <- divisores l, 
                        concat (replicate (l `div` m) (take m xs)) == xs]

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 96  ==  [1,2,3,4,6,8,12,16,24,32,48,96]
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `mod` x == 0]

periodo :: Eq a => [a] -> [a]

periodo xs = take n xs

where l = length xs

n = head [m | m <- divisores l,

concat (replicate (l `div` m) (take m xs)) == xs]

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 96 == [1,2,3,4,6,8,12,16,24,32,48,96]

divisores :: Int -> [Int]

divisores n = [x | x <- [1..n], n `mod` x == 0]

Mezcla de infinitas listas infinitas

PorJosé A. Alonso 3-mayo-201610-mayo-2016

Definir la función

   mezclaTodas :: Ord a => [[a]] -> [a]

1	mezclaTodas :: Ord a => [[a]] -> [a]

tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,

   ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
   [2,3,4,5,6,7,8,9,10,11]
   ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
   [2,4,6,8,9,10,12,14,16,18]

ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])

[2,3,4,5,6,7,8,9,10,11]

ghci> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])

[2,4,6,8,9,10,12,14,16,18]

Soluciones

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
    where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys

mezclaTodas :: Ord a => [[a]] -> [a]

mezclaTodas = foldr1 xmezcla

where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x == y = x : mezcla xs ys

| x > y = y : mezcla (x:xs) ys

Expresiones aritmética normalizadas

PorJosé A. Alonso 2-mayo-201625-abril-2021

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

   data Expr = Var String
             | S Expr Expr
             | P Expr Expre

data Expr = Var String

| S Expr Expr

| P Expr Expre

Por ejemplo, x.(y+z) se representa por (P (V «x») (S (V «y») (V «z»)))

Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.

Definir las funciones

   esTermino, esNormal :: Expr -> Bool

1	esTermino, esNormal :: Expr -> Bool

tales que

(esTermino a) se verifica si a es un término. Por ejemplo,

     esTermino (V "x")                                    == True
     esTermino (P (V "x") (P (V "y") (V "z")))            == True
     esTermino (P (V "x") (S (V "y") (V "z")))            == False
     esTermino (S (V "x") (P (V "y") (V "z")))            == False

esTermino (V "x") == True

esTermino (P (V "x") (P (V "y") (V "z"))) == True

esTermino (P (V "x") (S (V "y") (V "z"))) == False

esTermino (S (V "x") (P (V "y") (V "z"))) == False

(esNormal a) se verifica si a está en forma normal. Por ejemplo,

     esNormal (V "x")                                     == True
     esNormal (P (V "x") (P (V "y") (V "z")))             == True
     esNormal (S (V "x") (P (V "y") (V "z")))             == True
     esNormal (P (V "x") (S (V "y") (V "z")))             == False
     esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

esNormal (V "x") == True

esNormal (P (V "x") (P (V "y") (V "z"))) == True

esNormal (S (V "x") (P (V "y") (V "z"))) == True

esNormal (P (V "x") (S (V "y") (V "z"))) == False

esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

Soluciones

data Expr = V String
          | S Expr Expr
          | P Expr Expr

esTermino :: Expr -> Bool
esTermino (V _)   = True
esTermino (S _ _) = False
esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool
esNormal (S a b) = esNormal a && esNormal b
esNormal a       = esTermino a

data Expr = V String

| S Expr Expr

| P Expr Expr

esTermino :: Expr -> Bool

esTermino (V _) = True

esTermino (S _ _) = False

esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool

esNormal (S a b) = esNormal a && esNormal b

esNormal a = esTermino a

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencia

Soluciones

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico