Menu Close

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

   maximoRotaciones :: Integer -> Integer

tal que (maximoRotaciones n) es el mayor número obtenido rotando los dígitos de n. Por ejemplo,

   maximoRotaciones 3252    ==  5232
   maximoRotaciones 913942  ==  942913
   maximoRotaciones (234 + 10^(10^6)) `div` (10^(10^6))  ==  4

Soluciones

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>
Medio

4 soluciones de “Máximo de las rotaciones

  1. Rubén Muñoz Mkrtchian
    import Data.List (tails, inits)
     
    -- Vamos a emplear la función particiones xs y definida ayer para resolver este
    -- ejercicio.
     
    maximoRotaciones :: Integer -> Integer
    maximoRotaciones n = maximum
                       $ map read
                       $ aux
                       $ particiones xs (maximum xs)
                           where xs = show n
     
    -- Dada una lista de pares de listas, la función aux ps concatena el segundo
    -- elemento de cada par con el primero. Por ejemplo,
    --   λ> particiones [9,1,3,9,4,2] 9
    --   [([],[9,1,3,9,4,2]),([9,1,3],[9,4,2])]
    --   λ> aux it
    --   [[9,1,3,9,4,2],[9,4,2,9,1,3]]
     
    aux :: [([a],[a])] -> [[a]]
    aux [] = []
    aux (p:ps) = (snd p ++ fst p) : aux ps
     
    -- A partir de aquí, la definición de particiones xs y coincide con la
    -- planteada ayer. La eficiencia de maximoRotaciones n dependerá en gran parte
    -- de la eficiencia de la función particiones xs y.
     
    particiones :: Eq a => [a] -> a -> [([a],[a])]
    particiones xs y = [(primerPar xs zs2,zs2) | zs2 <- segundosPares xs y]
     
    segundosPares :: Eq a => [a] -> a -> [[a]]
    segundosPares xs y = filter ((== y) . head) (init (tails xs))
     
    primerPar :: [a] -> [a] -> [a]
    primerPar xs zs = (inits xs) !! (length xs - length zs)
  2. Joaquín Infante Rodríguez
    import Data.List
     
    enteroADigitos :: Integer -> [Integer]
    enteroADigitos n = [read [x] | x<-show n]
     
    digitosAEntero :: [Integer] -> Integer
    digitosAEntero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]
     
    rotacionesSublistas :: [Integer] -> [[Integer]]
    rotacionesSublistas (x:xs) = [(x:xs)] ++ [(xs++[x])] ++ (rotacionesSublistas (xs++[x]))
     
    maximoRotaciones :: Integer -> Integer
    maximoRotaciones x =   maximum
                         $ take (genericLength t)
                         $ nub
                         $ map (digitosAEntero)
                         $ rotacionesSublistas t
                          where t = enteroADigitos x
  3. Alejandro García Alcaide
    maximoRotaciones :: Integer -> Integer
    maximoRotaciones x = maximum [lee (rota r n) | n <- [1..(genericLength r)]]
      where r = digitos x                                               
     
    -- La función dígitos descompone un número en una lista formada por sus
    -- digitos. Veamos un ejemplo:
    -- digitos 3252 == [3,2,5,2]
    digitos :: Integer -> [Integer]
    digitos x = [read [y]::Integer | y <- show x]
     
    -- La función rota xs n, por su parte, toma un elemento de xs y lo coloca al
    -- final de la lista (para n = 1). Por ejemplo:
    --  rota [1..10] 1 == [2,3,4,5,6,7,8,9,10,1]
    --  rota [1..10] 4 == [5,6,7,8,9,10,1,2,3,4]
    rota :: [Integer] -> Integer -> [Integer] 
    rota []     _ = []
    rota xs     0 = xs
    rota (x:xs) n = rota (xs ++ [x]) (n-1)
     
    -- Por ultimo, la función lee toma los dígitos de un número en una lista y los
    -- transforma en el numero original. Por ejemplo:
    -- lee [3,2,5,2] == 3252
    lee :: [Integer] -> Integer
    lee xs = sum [x*10^n | (x,n) <- zip (reverse xs) [0.. (length xs)]]
  4. ADOLFO ENRIQUE VÁZQUEZ RUIZ
     
    digitos :: Integer -> [Integer]
    digitos n = [ read [x] | x <- show n]
    --La función digitos es una función definida por comprensión que, dado un
    --número entero, devuelve la lista conformada por sus dígitos.
     
    rotaciones :: [Integer] -> [[Integer]]
    rotaciones (x:xs) | null xs   = [[x]]
                      | otherwise = (xs ++ [x]):(rotaciones (xs ++ [x]))
    --La función rotaciones es una función infinita (en el caso de longitud mayor
    --que 1) definida por recursión que, dada una
    --lista, nos devuelve el conjunto de sus rotaciones. Entendemos rotación por el
    --algoritmo consistente en pasar el último elemento de una lista a la primera
    --posición de la misma.
     
    digitosANumero :: [Integer] -> Integer
    digitosANumero [] = 0
    digitosANumero (x:xs) = (x) * 10^((length (x:xs))- 1) + digitosANumero xs
    --La función digitosaNumero es una función de carácter recursivo que, dada una
    --lista de enteros, nos devuelve el número cuyos dígitos son los números de la
    --lista.
     
    maximoRotaciones :: Integer -> Integer
    maximoRotaciones n = maximum ( map (digitosANumero) ( take (length (digitos n)) (rotaciones (digitos n))))

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.