Sucesión de capicúas
Definir las funciones
1 2 |
capicuas :: [Integer] posicionCapicua :: Integer -> Integer |
tales que
- capicuas es la sucesión de los números capicúas. Por ejemplo,
1 2 3 4 5 6 |
λ> take 45 capicuas [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131, 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292, 303,313,323,333,343,353] λ> capicuas !! (10^5) 900010009 |
- (posicionCapicua x) es la posición del número capicúa x en la sucesión de los capicúas. Por ejemplo,
1 2 3 4 5 6 7 8 9 |
λ> posicionCapicua 353 44 λ> posicionCapicua 900010009 100000 λ> let xs = show (123^30) λ> posicionCapicua (read (xs ++ reverse xs)) 1497912859868342793044999075260564303046944727069807798026337448 λ> posicionCapicua (read (xs ++ "7" ++ reverse xs)) 5979128598683427930449990752605643030469447270698077980263374496 |
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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 |
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) |
Una refactorización del mismo código: