Rotaciones divisibles por 4
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
1 |
nRotacionesDivisibles :: Integer -> Int |
tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,
1 2 3 4 |
nRotacionesDivisibles 928160 == 4 nRotacionesDivisibles 44 == 2 nRotacionesDivisibles (1234^50000) == 38684 nRotacionesDivisibles (1234^300000) == 231853 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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) |
Falla para 44 (que tienes 2 rotaciones divisibles, aunque las dos son 44).
Se puede calcular el 2ª ejemplo en menos de 3 segundos, aunque con esta definición no se puede.
Falla para 44 (que tienes 2 rotaciones divisibles, aunque las dos son 44).
import Data.List
import Test.QuickCheck
— Primera definición (poco eficiente):
rotaciones :: Integer -> [Integer]
rotaciones x = map read [drop n xs ++ take n xs | n [Integer]
rotaciones’ x = map read (tail (zipWith (++) (tails xs) (inits xs)))
where xs = show x
nRotacionesDivisibles :: Integer -> Int
nRotacionesDivisibles = length . filter (\x -> x
mod
4 == 0) . rotaciones’— Sabiendo que un número es divisible por 4 si sus dos últimas cifras lo son, se crean las siguientes funciones:
digitos :: Integer -> [String]
digitos a = [[x] | x [Int]
lista n = map read (zipWith (++) (x:xs) (xs++[x]))
where (x:xs) = digitos n
nRotacionesDivisibles’ :: Integer -> Int
nRotacionesDivisibles’ = length . filter (\x -> x
mod
4 == 0) . lista— Se comprueba con QuickCheck la equivalencia entre definiciones:
prop :: Integer -> Property
prop x = x > 0 ==> nRotacionesDivisibles x == nRotacionesDivisibles’ x
— La comprobación es:
— *Main> quickCheck prop
— +++ OK, passed 100 tests.
— El cálculo del último ejemplo:
— *Main> nRotacionesDivisibles’ (1234^50000)
— 38684
— (0.35 secs, 709,561,984 bytes)
Y ahora en estilo haskell… :D
A la tercera va la vencida…