Máximo de las rotaciones
Las rotaciones del número 3252 son [3252, 2523, 5232, 2325] y el mayor de dichos números es 5232.
Definir la función
1 |
maximoRotaciones :: Integer -> Integer |
tal que (maximoRotaciones n) es el mayor número obtenido rotando los dígitos de n. Por ejemplo,
1 2 3 |
maximoRotaciones 3252 == 5232 maximoRotaciones 913942 == 942913 maximoRotaciones (234 + 10^(10^6)) `div` (10^(10^6)) == 4 |
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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
import Data.List (inits, tails) -- 1ª solución -- =========== maximoRotaciones :: Integer -> Integer maximoRotaciones = maximum . rotacionesNumero -- (rotacionesNumero n) es la lista de las rotaciones obtenidas desplazando -- el primer dígito de n al final. Por ejemplo, -- rotacionesNumero 325 == [325,253,532] 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ª solución -- =========== maximoRotaciones2 :: Integer -> Integer maximoRotaciones2 n = maximum (rotacionesDigito n (maximoDigito n)) -- (maximoDigito n) es el máximo de los dígitos de n. Por ejemplo, -- maximoDigito 291394 == 9 maximoDigito :: Integer -> Integer maximoDigito n = read [maximum (show n)] -- (rotacionesDigito n k) es la lista de las rotaciones de n cuyo primer -- dígito es k. Por ejemplo, -- rotacionesDigito 291394 9 == [913942,942913] rotacionesDigito :: Integer -> Integer -> [Integer] rotacionesDigito n k = [read (vs ++ us) | (us,vs) <- particiones (show n) (head (show k))] -- (particiones xs y) es la lista de las particiones de xs en dos partes -- tales que el primer elemento de la segunda parte es y. Por -- ejemplo, -- particiones [2,9,1,3,9,4] 9 == [([2],[9,1,3,9,4]),([2,9,1,3],[9,4])] -- particiones [2,9,1,3,9,4] 3 == [([2,9,1],[3,9,4])] -- particiones [2,9,1,3,9,4] 7 == [] -- particiones "Particiones" 'i' == [("Part","iciones"),("Partic","iones")] particiones :: Eq a => [a] -> a -> [([a],[a])] particiones xs y = [(prefijoSufijo xs zs,zs) | zs <- sufijos xs y] -- (sufijos xs y) es la lista de los sufijos de xs que empiezan por -- y. Por ejemplo, -- λ> sufijos "particiones" 'i' -- ["iciones","iones"] sufijos :: Eq a => [a] -> a -> [[a]] sufijos xs y = filter ((== y) . head) (init (tails xs)) -- (prefijoSufijo xs zs) es el prefijo de xs que junto con el sufijo zs -- forma la lista xs. Por ejemplo, -- λ> prefijoSufijo "particiones" "iciones" -- "part" prefijoSufijo :: [a] -> [a] -> [a] prefijoSufijo xs zs = (inits xs) !! (length xs - length zs) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equivalencia :: Integer -> Property prop_equivalencia n = n > 0 ==> maximoRotaciones n == maximoRotaciones2 n -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximoRotaciones (product [1..2000]) `mod` (10^20) -- 64970515522882052348 -- (4.59 secs, 13,275,801,696 bytes) -- λ> maximoRotaciones2 (product [1..2000]) `mod` (10^20) -- 64970515522882052348 -- (0.41 secs, 1,132,544,240 bytes) -- -- λ> read (take 9 (show (maximoRotaciones (234 + 10^(10^4))))) :: Integer -- 410000000 -- (12.53 secs, 36,326,102,416 bytes) -- λ> read (take 9 (show (maximoRotaciones2 (234 + 10^(10^4))))) :: Integer -- 410000000 -- (0.03 secs, 6,227,024 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
4 Comentarios