zip

Recorrido en ZigZag

PorJosé A. Alonso 25-abril-201725-abril-2021

El recorrido en ZigZag de una matriz consiste en pasar de la primera fila hasta la última, de izquierda a derecha en las filas impares y de derecha a izquierda en las filas pares, como se indica en la figura.

         /             \
         | 1 -> 2 -> 3 |
         |           | |
         |           v |
         | 4 <- 5 <- 6 |   =>  Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]
         | |           |
         | v           |
         | 7 -> 8 -> 9 |
         \             /

/ \

| 1 -> 2 -> 3 |

| | |

| v |

| 4 <- 5 <- 6 | => Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]

| | |

| v |

| 7 -> 8 -> 9 |

\ /

Definir la función

   recorridoZigZag :: Matrix a -> [a]

1	recorridoZigZag :: Matrix a -> [a]

tal que (recorridoZigZag m) es la lista con los elementos de la matriz m cuando se recorre esta en ZigZag. Por ejemplo,

   λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])
   [1,2,3,6,5,4,7,8,9]
   λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])
   [1,2,4,3,5,6,8,7]
   λ> recorridoZigZag (fromLists [[1,2,3,4],[5,6,7,8],[9,10,11,12]])
   [1,2,3,4,8,7,6,5,9,10,11,12]
   λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")
   "Cadasap o es al meta"
   λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")
   "Cada  osapes laatem "
   λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")
   "Caad psao se l ameat"
   λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")
   "Cada paso atem al se"

λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])

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

λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])

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

λ> recorridoZigZag (fromLists [[1,2,3,4],[5,6,7,8],[9,10,11,12]])

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

λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")

"Cadasap o es al meta"

λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")

"Cada osapes laatem "

λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")

"Caad psao se l ameat"

λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")

"Cada paso atem al se"

Soluciones

import Data.Matrix (Matrix, toLists, fromLists, fromList)

recorridoZigZag :: Matrix a -> [a]
recorridoZigZag m =
  concat [f xs | (f,xs) <- zip (cycle [id,reverse]) (toLists m)]

import Data.Matrix (Matrix, toLists, fromLists, fromList)

recorridoZigZag :: Matrix a -> [a]

recorridoZigZag m =

concat [f xs | (f,xs) <- zip (cycle [id,reverse]) (toLists m)]

Subnúmeros pares

PorJosé A. Alonso 18-abril-201725-abril-2017

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

   subnumeros       :: Integer -> [Integer]
   nSubnumerosPares :: Integer -> Integer

1 2	subnumeros :: Integer -> [Integer] nSubnumerosPares :: Integer -> Integer

tales que

(subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,

     subnumerosPares 254   ==  [2,254,54,4]
     subnumerosPares 154   ==  [154,54,4]
     subnumerosPares 15    ==  []

subnumerosPares 254 == [2,254,54,4]

subnumerosPares 154 == [154,54,4]

subnumerosPares 15 == []

(nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,

     nSubnumerosPares 254   ==  4
     nSubnumerosPares2 (4^(10^6))  ==  90625258498

1 2	nSubnumerosPares 254 == 4 nSubnumerosPares2 (4^(10^6)) == 90625258498

Soluciones

import Data.List ( genericLength
                 , inits
                 , tails
                 )

subnumerosPares :: Integer -> [Integer]
subnumerosPares n =
  filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,
--    subnumeros 254  ==  [2,25,5,254,54,4]
subnumeros :: Integer -> [Integer]
subnumeros n =
  [read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo, 
--    sublistas "abc"  ==  ["a","ab","b","abc","bc","c"]
sublistas :: [a] -> [[a]]
sublistas xs =
  concat [init (tails ys) | ys <- tail (inits xs)]

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

nSubnumerosPares :: Integer -> Integer
nSubnumerosPares =
  genericLength . subnumerosPares

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

nSubnumerosPares2 :: Integer -> Integer
nSubnumerosPares2 =
  sum . posicionesDigitosPares 

-- (posicionesDigitosPares x) es la lista de las posiciones de los
-- dígitos pares de x. Por ejemplo,
--    posicionesDigitosPares 254  ==  [1,3]
posicionesDigitosPares :: Integer -> [Integer]
posicionesDigitosPares x =
  [n | (n,y) <- zip [1..] (show x)
     , y `elem` "02468"]

-- Comparación de eficiencia
--    λ> nSubnumerosPares (2^(10^3))
--    22934
--    (2.83 secs, 3,413,414,872 bytes)
--    λ> nSubnumerosPares2 (2^(10^3))
--    22934
--    (0.01 secs, 0 bytes)

import Data.List ( genericLength

, inits

, tails

)

subnumerosPares :: Integer -> [Integer]

subnumerosPares n =

filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,

-- subnumeros 254 == [2,25,5,254,54,4]

subnumeros :: Integer -> [Integer]

subnumeros n =

[read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,

-- sublistas "abc" == ["a","ab","b","abc","bc","c"]

sublistas :: [a] -> [[a]]

sublistas xs =

concat [init (tails ys) | ys <- tail (inits xs)]

-- 1ª definición

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

nSubnumerosPares :: Integer -> Integer

nSubnumerosPares =

genericLength . subnumerosPares

-- 2ª definición

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

nSubnumerosPares2 :: Integer -> Integer

nSubnumerosPares2 =

sum . posicionesDigitosPares

-- (posicionesDigitosPares x) es la lista de las posiciones de los

-- dígitos pares de x. Por ejemplo,

-- posicionesDigitosPares 254 == [1,3]

posicionesDigitosPares :: Integer -> [Integer]

posicionesDigitosPares x =

[n | (n,y) <- zip [1..] (show x)

, y `elem` "02468"]

-- Comparación de eficiencia

-- λ> nSubnumerosPares (2^(10^3))

-- 22934

-- (2.83 secs, 3,413,414,872 bytes)

-- λ> nSubnumerosPares2 (2^(10^3))

-- 22934

-- (0.01 secs, 0 bytes)

El problema de las N torres

PorJosé A. Alonso 10-abril-201725-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 representan 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

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)

Distancias entre primos consecutivos

PorJosé A. Alonso 4-abril-201711-abril-2017

Los 15 primeros números primos son

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

   1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

1	1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4

La distribución de las distancias es

   (1,1), (2,6), (4,5), (6,2)

1	(1,1), (2,6), (4,5), (6,2)

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

   (1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

1	(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

  cuentaDistancias        :: Int -> [(Int,Int)]
  frecuenciasDistancias   :: Int -> [(Int,Float)]
  graficas                :: [Int] -> IO ()
  distanciasMasFrecuentes :: Int -> [Int]

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

frecuenciasDistancias :: Int -> [(Int,Float)]

graficas :: [Int] -> IO ()

distanciasMasFrecuentes :: Int -> [Int]

tales que

(cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> cuentaDistancias 15
     [(1,1),(2,6),(4,5),(6,2)]
     λ> cuentaDistancias 100
     [(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

λ> cuentaDistancias 15

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

λ> cuentaDistancias 100

[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

(frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> frecuenciasDistancias 15
     [(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
     λ> frecuenciasDistancias 30
     [(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

λ> frecuenciasDistancias 15

[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]

λ> frecuenciasDistancias 30

[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

(graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

(graficas [1000,2000,3000]) dibuja

y (graficas [100000,200000,300000]) dibuja
(distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,

     distanciasMasFrecuentes 15     ==  [2]
     distanciasMasFrecuentes 26     ==  [2,4]
     distanciasMasFrecuentes 32     ==  [4]
     distanciasMasFrecuentes 41     ==  [2,4,6]
     distanciasMasFrecuentes 77     ==  [6]
     distanciasMasFrecuentes 160    ==  [4,6]
     distanciasMasFrecuentes (10^6) == [6]

distanciasMasFrecuentes 15 == [2]

distanciasMasFrecuentes 26 == [2,4]

distanciasMasFrecuentes 32 == [4]

distanciasMasFrecuentes 41 == [2,4,6]

distanciasMasFrecuentes 77 == [6]

distanciasMasFrecuentes 160 == [4,6]

distanciasMasFrecuentes (10^6) == [6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Soluciones

import Data.Numbers.Primes
import qualified Data.Map as M 
import Graphics.Gnuplot.Simple
import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]
cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int
dicDistancias n =
  M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]
distancias n =
  zipWith (-) (tail xs) xs
  where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]
frecuenciasDistancias n =
  [(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]
  where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()
graficas ns =
  plotLists [Key Nothing]
            (map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]
distanciasMasFrecuentes n =
  M.keys (M.filter (==m) d)
  where d = dicDistancias n
        m = maximum (M.elems d)

-- La propiedad es
prop_distanciasMasFrecuentes :: Int -> Bool
prop_distanciasMasFrecuentes n =
  distanciasMasFrecuentes (161 + abs n) == [6]

import Data.Numbers.Primes

import qualified Data.Map as M

import Graphics.Gnuplot.Simple

import Test.QuickCheck

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

cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int

dicDistancias n =

M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]

distancias n =

zipWith (-) (tail xs) xs

where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]

frecuenciasDistancias n =

[(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]

where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()

graficas ns =

plotLists [Key Nothing]

(map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]

distanciasMasFrecuentes n =

M.keys (M.filter (==m) d)

where d = dicDistancias n

m = maximum (M.elems d)

-- La propiedad es

prop_distanciasMasFrecuentes :: Int -> Bool

prop_distanciasMasFrecuentes n =

distanciasMasFrecuentes (161 + abs n) == [6]

Rotaciones divisibles por 4

PorJosé A. Alonso 3-abril-201710-abril-2017

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816. De las cuales, las divisibles por 4 son 928160, 816092, 160928 y 92816.

Definir la función

   nRotacionesDivisibles :: Integer -> Int

1	nRotacionesDivisibles :: Integer -> Int

tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,

   nRotacionesDivisibles 928160          ==  4
   nRotacionesDivisibles 44              ==  2
   nRotacionesDivisibles (1234^50000)    ==  38684
   nRotacionesDivisibles (1234^300000)   ==  231853

nRotacionesDivisibles 928160 == 4

nRotacionesDivisibles 44 == 2

nRotacionesDivisibles (1234^50000) == 38684

nRotacionesDivisibles (1234^300000) == 231853

Soluciones

import Data.Char (digitToInt)

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

nRotacionesDivisibles :: Integer -> Int
nRotacionesDivisibles n =
  length [x | x <- rotacionesNumero n, x `mod` 4 == 0]


-- (rotacionesNumero) es la lista de la rotaciones del número n. Por
-- ejemplo,
--    rotacionesNumero 235  ==  [235,352,523]
rotacionesNumero :: Integer -> [Integer]
rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando
-- el primer elemento xs al final. Por ejemplo,
--    rotaciones [2,3,5]  ==  [[2,3,5],[3,5,2],[5,2,3]]
rotaciones :: [a] -> [[a]]
rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al
-- final. Por ejemplo, 
--    rota [3,2,5,7]  ==  [2,5,7,3]
rota :: [a] -> [a]
rota (x:xs) = xs ++ [x]

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

nRotacionesDivisibles2 :: Integer -> Int
nRotacionesDivisibles2 n = 
  length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo
-- el último con el primero. Por ejemplo,
--    pares 928160  ==  [9,92,28,81,16,60]
pares :: Integer -> [Int]
pares n =
  read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]
  where ns = show n

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

nRotacionesDivisibles3 :: Integer -> Int
nRotacionesDivisibles3 n =
  ( length
  . filter (0 ==)
  . map (`mod` 4)
  . zipWith (\x y -> 2*x + y) d
  . tail
  . (++[i])) d
  where
    d@(i:dn) = (map digitToInt . show) n

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

--    λ> nRotacionesDivisibles (123^1500)
--    803
--    (8.15 secs, 7,109,852,800 bytes)
--    λ> nRotacionesDivisibles2 (123^1500)
--    803
--    (0.05 secs, 0 bytes)
--    λ> nRotacionesDivisibles3 (123^1500)
--    803
--    (0.02 secs, 0 bytes)
--
--    λ> nRotacionesDivisibles2 (1234^50000)
--    38684
--    (2.24 secs, 1,160,467,472 bytes)
--    λ> nRotacionesDivisibles3 (1234^50000)
--    38684
--    (0.31 secs, 68,252,040 bytes)

import Data.Char (digitToInt)

-- 1ª definición

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

nRotacionesDivisibles :: Integer -> Int

nRotacionesDivisibles n =

length [x | x <- rotacionesNumero n, x `mod` 4 == 0]

-- (rotacionesNumero) es la lista de la rotaciones del número n. Por

-- ejemplo,

-- rotacionesNumero 235 == [235,352,523]

rotacionesNumero :: Integer -> [Integer]

rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando

-- el primer elemento xs al final. Por ejemplo,

-- rotaciones [2,3,5] == [[2,3,5],[3,5,2],[5,2,3]]

rotaciones :: [a] -> [[a]]

rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al

-- final. Por ejemplo,

-- rota [3,2,5,7] == [2,5,7,3]

rota :: [a] -> [a]

rota (x:xs) = xs ++ [x]

-- 2ª definición

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

nRotacionesDivisibles2 :: Integer -> Int

nRotacionesDivisibles2 n =

length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo

-- el último con el primero. Por ejemplo,

-- pares 928160 == [9,92,28,81,16,60]

pares :: Integer -> [Int]

pares n =

read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]

where ns = show n

-- 3ª definición

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

nRotacionesDivisibles3 :: Integer -> Int

nRotacionesDivisibles3 n =

( length

. filter (0 ==)

. map (`mod` 4)

. zipWith (\x y -> 2*x + y) d

. tail

. (++[i])) d

where

d@(i:dn) = (map digitToInt . show) n

-- Comparación de eficiencia

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

-- λ> nRotacionesDivisibles (123^1500)

-- 803

-- (8.15 secs, 7,109,852,800 bytes)

-- λ> nRotacionesDivisibles2 (123^1500)

-- 803

-- (0.05 secs, 0 bytes)

-- λ> nRotacionesDivisibles3 (123^1500)

-- 803

-- (0.02 secs, 0 bytes)

-- λ> nRotacionesDivisibles2 (1234^50000)

-- 38684

-- (2.24 secs, 1,160,467,472 bytes)

-- λ> nRotacionesDivisibles3 (1234^50000)

-- 38684

-- (0.31 secs, 68,252,040 bytes)

Recorrido en ZigZag

Soluciones

Subnúmeros pares

Soluciones

El problema de las N torres

Soluciones

Distancias entre primos consecutivos

Soluciones

Rotaciones divisibles por 4

Soluciones

Entradas recientes

Buscar

Correo electrónico