Máximo de las rotaciones restringidas

PorJosé A. Alonso 6-diciembre-201713-diciembre-2017

Rotar un número a la iquierda significa pasar su primer dígito al final. Por ejemplo, rotando a la izquierda el 56789 se obtiene 67895.

Las rotaciones restringidas del número 56789 se obtienen como se indica a continución:

Se inicia con el propio número: 56789
El anterior se rota a la izquierda y se obtiene el 67895.
Del anterior se fija el primer dígito y se rota a la iquierda los otros. Se obtiene 68957.
Del anterior se fijan los 2 primeros dígito y se rota a la iquierda los otros. Se obtiene 68579.
Del anterior se fijan los 3 primeros dígito y se rota a la iquierda los otros. Se obtiene 68597.

El proceso ha terminado ya que conservando los cuatro primeros queda sólo un dígito que al girar es él mismo. Por tanto, la sucesión de las rotaciones restringidas de 56789 es

   56789 -> 67895 -> 68957 -> 68579 -> 68597

1	56789 -> 67895 -> 68957 -> 68579 -> 68597

y su mayor elemento es 68957.

Definir la función

   maxRotaciones :: Integer -> Integer

1	maxRotaciones :: Integer -> Integer

tal que (maxRotaciones n) es el máximo de las rotaciones restringidas del número n. Por ejemplo,

   maxRotaciones 56789       ==  68957
   maxRotaciones 1347902468  ==  3790246814
   maxRotaciones 6           ==  6
   maxRotaciones 2017        ==  2017

maxRotaciones 56789 == 68957

maxRotaciones 1347902468 == 3790246814

maxRotaciones 6 == 6

maxRotaciones 2017 == 2017

Soluciones

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

maxRotaciones :: Integer -> Integer
maxRotaciones = read . aux . show
  where aux n@[_]        = n
        aux n@(x1:x2:xs) = max n (x2:aux (xs ++ [x1]))

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

maxRotaciones2 :: Integer -> Integer
maxRotaciones2 n
  | n < 10    = n
  | otherwise = maximum [ read (us ++ vs)
                        | (us,vs) <- take m (iterate siguiente ("",xs)) ]
  where xs = show n
        m  = length xs

-- siguiente ("","56789")  ==  ("6","7895")
-- siguiente ("6","7895")  ==  ("68","957")
-- siguiente ("68","957")  ==  ("685","79")
-- siguiente ("685","79")  ==  ("6859","7")
-- siguiente ("6859","7")  ==  ("6859","7")
siguiente :: (String,String) -> (String,String)
siguiente (xs,a:b:ys) = (xs ++ [b], ys ++ [a])
siguiente (xs,[a])    = (xs,[a])

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

maxRotaciones3 :: Integer -> Integer
maxRotaciones3 = read . aux . show
  where aux (x:y:xs) | x > y     = x : y : xs
                     | otherwise = y : (aux $ xs ++ [x])
        aux [x]                  = [x]
        aux _                    = []

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

--    λ> length (show (maxRotaciones (n (5*10^3))))
--    5001
--    (2.74 secs, 802,282,616 bytes)
--    λ> length (show (maxRotaciones2 (n (5*10^3))))
--    5001
--    (18.23 secs, 12,375,579,216 bytes)
--    λ> length (show (maxRotaciones3 (n (5*10^3))))
--    5001
--    (0.67 secs, 729,155,056 bytes)

-- 1ª solución

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

maxRotaciones :: Integer -> Integer

maxRotaciones = read . aux . show

where aux n@[_] = n

aux n@(x1:x2:xs) = max n (x2:aux (xs ++ [x1]))

-- 2ª solución

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

maxRotaciones2 :: Integer -> Integer

maxRotaciones2 n

| n < 10 = n

| otherwise = maximum [ read (us ++ vs)

| (us,vs) <- take m (iterate siguiente ("",xs)) ]

where xs = show n

m = length xs

-- siguiente ("","56789") == ("6","7895")

-- siguiente ("6","7895") == ("68","957")

-- siguiente ("68","957") == ("685","79")

-- siguiente ("685","79") == ("6859","7")

-- siguiente ("6859","7") == ("6859","7")

siguiente :: (String,String) -> (String,String)

siguiente (xs,a:b:ys) = (xs ++ [b], ys ++ [a])

siguiente (xs,[a]) = (xs,[a])

-- 3ª solución

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

maxRotaciones3 :: Integer -> Integer

maxRotaciones3 = read . aux . show

where aux (x:y:xs) | x > y = x : y : xs

| otherwise = y : (aux $ xs ++ [x])

aux [x] = [x]

aux _ = []

-- Comparación de eficiencia

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

-- λ> length (show (maxRotaciones (n (5*10^3))))

-- 5001

-- (2.74 secs, 802,282,616 bytes)

-- λ> length (show (maxRotaciones2 (n (5*10^3))))

-- 5001

-- (18.23 secs, 12,375,579,216 bytes)

-- λ> length (show (maxRotaciones3 (n (5*10^3))))

-- 5001

-- (0.67 secs, 729,155,056 bytes)

6 Comentarios

maxRotaciones :: Integer -> Integer
maxRotaciones = maximum . rotaciones
 
rotaciones :: Integer -> [Integer]
rotaciones n = n : map read (aux (show n) 0)
  where aux xs y | length xs < y + 2 = []
                 | otherwise         = z : aux z (y+1)
          where z = take y xs ++ rotar (drop y xs)
 
rotar :: String -> String
rotar []     = []
rotar (x:xs) = reverse (x : reverse xs)

maxRotaciones :: Integer -> Integer

maxRotaciones = maximum . rotaciones

rotaciones :: Integer -> [Integer]

rotaciones n = n : map read (aux (show n) 0)

where aux xs y | length xs < y + 2 = []

| otherwise = z : aux z (y+1)

where z = take y xs ++ rotar (drop y xs)

rotar :: String -> String

rotar [] = []

rotar (x:xs) = reverse (x : reverse xs)

Responder

Es probable que se pueda simplificar, así como mejorar el rendimiento pero aquí va una primera definición.

maxRotaciones :: Integer -> Integer
maxRotaciones x =
  maximum (map numero (rotaciones (cifras x)))

cifras :: Integer -> [Integer]
cifras x = [read [d] | d <- show x]

rotaciones :: [a] -> [[a]]
rotaciones xs =
  take (length xs)
       (xs: rota xs : [aux n (aux (n-1) xs) | n <- [1..length xs - 1]])

rota :: [a] -> [a]
rota (x:xs) = xs ++ [x]

aux :: Int -> [a] -> [a]
aux 0 xs = xs
aux 1 xs = head (rota xs) : rota (tail (rota xs))
aux n xs = take n  xs ++ rota (drop n xs)

numero :: [Integer] -> Integer
numero xs = sum [x*10^y | (x,y) <- zip (reverse xs) [0..]]

maxRotaciones :: Integer -> Integer

maxRotaciones x =

maximum (map numero (rotaciones (cifras x)))

cifras :: Integer -> [Integer]

cifras x = [read [d] | d <- show x]

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

rotaciones xs =

take (length xs)

(xs: rota xs : [aux n (aux (n-1) xs) | n <- [1..length xs - 1]])

rota :: [a] -> [a]

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

aux :: Int -> [a] -> [a]

aux 0 xs = xs

aux 1 xs = head (rota xs) : rota (tail (rota xs))

aux n xs = take n xs ++ rota (drop n xs)

numero :: [Integer] -> Integer

numero xs = sum [x*10^y | (x,y) <- zip (reverse xs) [0..]]

Responder

Aquí un intento

maxRotaciones :: Integer -> Integer
maxRotaciones n = maximum $ n : map read ((rotaciones . show) n)
 
rotaciones :: [a] -> [[a]]
rotaciones [x]      = [[x]]
rotaciones (x:y:xs) = (y : m) : map (y:) (rotaciones m)
  where m = xs ++ [x]

maxRotaciones :: Integer -> Integer

maxRotaciones n = maximum $ n : map read ((rotaciones . show) n)

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

rotaciones [x] = [[x]]

rotaciones (x:y:xs) = (y : m) : map (y:) (rotaciones m)

where m = xs ++ [x]

Responder

Se calcula directamente el máximo, sin iterar entre todas las rotaciones posibles.

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}
import Data.Foldable (toList)
import Data.Sequence ((<|), (|>), fromList, Seq, viewl, ViewL(..))

rot :: Seq Char -> Seq Char
rot xss@(a :<: (b :<: xs)) = if a < b then b <| rot (xs |> a) else xss
rot                   xs   = xs

maxRotaciones :: Integer -> Integer
maxRotaciones = read . toList . rot . fromList . show

pattern x :<: xs <- (viewl -> x :< xs)

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}

import Data.Foldable (toList)

import Data.Sequence ((<|), (|>), fromList, Seq, viewl, ViewL(..))

rot :: Seq Char -> Seq Char

rot xss@(a :<: (b :<: xs)) = if a < b then b <| rot (xs |> a) else xss

rot xs = xs

maxRotaciones :: Integer -> Integer

maxRotaciones = read . toList . rot . fromList . show

pattern x :<: xs <- (viewl -> x :< xs)

Responder

maxRotaciones :: Integer -> Integer
maxRotaciones = read . rotaciones . show

rotaciones :: String -> String
rotaciones (x:y:xs) | x > y     = x : y : xs
                    | otherwise = y : (rotaciones $ xs ++ [x])
rotaciones [x]      = [x]
rotaciones _        = []

maxRotaciones :: Integer -> Integer

maxRotaciones = read . rotaciones . show

rotaciones :: String -> String

rotaciones (x:y:xs) | x > y = x : y : xs

| otherwise = y : (rotaciones $ xs ++ [x])

rotaciones [x] = [x]

rotaciones _ = []

Responder

josejuan dice:

7-diciembre-2017 a las 09:56

Coste cuadrático:

Haskell

> length $ rotaciones $ replicate 34512 '1' ++ ['9'] 34513 (42.39 secs, 38,999,331,376 bytes)

1
2
3

> length $ rotaciones $ replicate 34512 '1' ++ ['9']
34513
(42.39 secs, 38,999,331,376 bytes)

Respecto coste lineal:

Haskell

> length $ rot $ fromList $ replicate 34512 '1' ++ ['9'] 34513 (0.01 secs, 7,687,032 bytes)

1
2
3

> length $ rot $ fromList $ replicate 34512 '1' ++ ['9']
34513
(0.01 secs, 7,687,032 bytes)

Responder

Máximo de las rotaciones restringidas

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico