import Data.List (genericLength)
-- 1ª definición de capicuas
-- =========================
capicuas1 :: [Integer]
capicuas1 = [n | n <- [0..]
, esCapicua n]
-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
-- esCapicua 353 == True
-- esCapicua 3553 == True
-- esCapicua 3535 == False
esCapicua :: Integer -> Bool
esCapicua x =
xs == reverse xs
where xs = show x
-- 2ª definición de capicuas
-- =========================
capicuas2 :: [Integer]
capicuas2 = capicuasImpares `mezcla` capicuasPares
-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,
-- λ> take 17 capicuasPares
-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
[read (ns ++ reverse ns) | n <- [0..]
, let ns = show n]
-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,
-- λ> take 20 capicuasImpares
-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
[1..9] ++ [read (ns ++ [z] ++ reverse ns)
| n <- [1..]
, let ns = show n
, z <- "0123456789"]
-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]
-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
| x < y = x : mezcla xs vs
| otherwise = y : mezcla us ys
-- 3ª definición de capicuas
-- =========================
capicuas3 :: [Integer]
capicuas3 = iterate sigCapicua 0
-- (sigCapicua x) es el capicúa siguiente del número x. Por ejemplo,
-- sigCapicua 12321 == 12421
-- sigCapicua 1298921 == 1299921
-- sigCapicua 999 == 1001
-- sigCapicua 9999 == 10001
-- sigCapicua 898 == 909
-- sigCapicua 123456777654321 == 123456787654321
sigCapicua :: Integer -> Integer
sigCapicua n = read cs
where l = length (show (n+1))
k = l `div` 2
xs = show ((n `div` (10^k)) + 1)
cs = xs ++ drop (l `rem` 2) (reverse xs)
-- 4ª definición de capicuas
-- =========================
capicuas4 :: [Integer]
capicuas4 =
concatMap generaCapicuas4 [1..]
generaCapicuas4 :: Integer -> [Integer]
generaCapicuas4 1 = [0..9]
generaCapicuas4 n
| even n = [read (xs ++ reverse xs)
| xs <- map show [10^(m-1)..10^m-1]]
| otherwise = [read (xs ++ (y : reverse xs))
| xs <- map show [10^(m-1)..10^m-1]
, y <- "0123456789"]
where m = n `div` 2
-- 5ª definición de capicuas
-- =========================
capicuas5 :: [Integer]
capicuas5 = 0 : aux 1
where aux n = [read (show x ++ tail (reverse (show x)))
| x <- [10^(n-1)..10^n-1]]
++ [read (show x ++ reverse (show x))
| x <- [10^(n-1)..10^n-1]]
++ aux (n+1)
-- 6ª definición de capicuas
-- =========================
capicuas6 :: [Integer]
capicuas6 = 0 : map read (capicuas6Aux [1..9])
capicuas6Aux :: [Integer] -> [String]
capicuas6Aux xs = map duplica1 ys
++ map duplica2 ys
++ capicuas6Aux [head xs * 10 .. last xs * 10 + 9]
where
ys = map show xs
duplica1 cs = cs ++ tail (reverse cs)
duplica2 cs = cs ++ reverse cs
-- 7ª definición de capicuas
-- =========================
capicuas7 :: [Integer]
capicuas7 = 0 : map read (capicuas7Aux [1..9])
capicuas7Aux :: [Integer] -> [String]
capicuas7Aux xs = map duplica1 ys
++ map duplica2 ys
++ capicuas7Aux [head xs * 10 .. last xs * 10 + 9]
where
ys = map show xs
duplica1 = (++) <$> id <*> tail . reverse
duplica2 = (++) <$> id <*> reverse
-- Comparación de eficiencia
-- =========================
-- λ> capicuas1 !! 2000
-- 1001001
-- (2.25 secs, 598,879,552 bytes)
-- λ> capicuas2 !! 2000
-- 1001001
-- (0.05 secs, 28,630,552 bytes)
-- λ> capicuas3 !! 2000
-- 1001001
-- (0.06 secs, 14,721,360 bytes)
-- λ> capicuas4 !! 2000
-- 1001001
-- (0.01 secs, 0 bytes)
-- λ> capicuas5 !! 2000
-- 1001001
-- (0.01 secs, 0 bytes)
-- λ> capicuas6 !! 2000
-- 1001001
-- (0.01 secs, 0 bytes)
-- λ> capicuas7 !! 2000
-- 1001001
-- (0.01 secs, 0 bytes)
--
-- λ> capicuas2 !! (10^5)
-- 900010009
-- (2.03 secs, 1,190,503,952 bytes)
-- λ> capicuas3 !! (10^5)
-- 900010009
-- (5.12 secs, 1,408,876,328 bytes)
-- λ> capicuas4 !! (10^5)
-- 900010009
-- (0.21 secs, 8,249,296 bytes)
-- λ> capicuas5 !! (10^5)
-- 900010009
-- (0.10 secs, 31,134,176 bytes)
-- λ> capicuas6 !! (10^5)
-- 900010009
-- (0.14 secs, 55,211,272 bytes)
-- λ> capicuas7 !! (10^5)
-- 900010009
-- (0.03 secs, 0 bytes)
-- 1ª definición de posicionCapicua
posicionCapicua1 :: Integer -> Integer
posicionCapicua1 x =
genericLength (takeWhile (< x) capicuas7)
-- 2ª definición
posicionCapicua2 :: Integer -> Integer
posicionCapicua2 x
| even n = read ('1' : take (n `div` 2) xs) - 1
| otherwise = read (show (1 + read [y]) ++ take (n `div` 2) ys) - 1
where xs@(y:ys) = show x
n = genericLength xs
-- Comparación de eficiencia
-- λ> posicionCapicua1 (10^9 - 1)
-- 109998
-- (1.98 secs, 1,112,991,520 bytes)
-- λ> posicionCapicua2 (10^9 - 1)
-- 109998
-- (0.01 secs, 0 bytes)