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)