{"id":2800,"date":"2017-01-11T06:00:37","date_gmt":"2017-01-11T04:00:37","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2800"},"modified":"2017-01-18T13:58:02","modified_gmt":"2017-01-18T11:58:02","slug":"sucesion-de-capicuas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sucesion-de-capicuas\/","title":{"rendered":"Sucesi\u00f3n de capic\u00faas"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   capicuas        :: [Integer] \n   posicionCapicua :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>capicuas es la sucesi\u00f3n de los n\u00fameros capic\u00faas. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n   \u03bb> take 45 capicuas\n   [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,\n    141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,\n    303,313,323,333,343,353]\n   \u03bb> capicuas !! (10^5)  \n   900010009\n<\/pre>\n<ul>\n<li>(posicionCapicua x) es la posici\u00f3n del n\u00famero capic\u00faa x en la sucesi\u00f3n de los capic\u00faas. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n   \u03bb> posicionCapicua 353\n   44\n   \u03bb> posicionCapicua 900010009\n   100000\n   \u03bb> let xs = show (123^30)\n   \u03bb> posicionCapicua (read (xs ++ reverse xs))\n   1497912859868342793044999075260564303046944727069807798026337448\n   \u03bb> posicionCapicua (read (xs ++ \"7\" ++ reverse xs))\n   5979128598683427930449990752605643030469447270698077980263374496\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\n\n-- 1\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas1 :: [Integer]\ncapicuas1 = [n | n <- [0..]\n               , esCapicua n]\n\n-- (esCapicua x) se verifica si x es capic\u00faa. Por ejemplo,\n--    esCapicua 353   ==  True\n--    esCapicua 3553  ==  True\n--    esCapicua 3535  ==  False\nesCapicua :: Integer -> Bool\nesCapicua x =\n  xs == reverse xs\n  where xs = show x\n\n\n-- 2\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas2 :: [Integer]\ncapicuas2 = capicuasImpares `mezcla` capicuasPares\n\n-- capicuasPares es la sucesi\u00f3n del cero y las capic\u00faas con un n\u00famero\n-- par de d\u00edgitos. Por ejemplo,  \n--    \u03bb> take 17 capicuasPares\n--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]\ncapicuasPares :: [Integer]\ncapicuasPares =\n  [read (ns ++ reverse ns) | n <- [0..]\n                           , let ns = show n]   \n\n-- capicuasImpares es la sucesi\u00f3n de las capic\u00faas con un n\u00famero\n-- impar de d\u00edgitos a partir de 1. Por ejemplo,  \n--    \u03bb> take 20 capicuasImpares\n--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]\ncapicuasImpares :: [Integer]\ncapicuasImpares =\n  [1..9] ++ [read (ns ++ [z] ++ reverse ns)\n            | n <- [1..]\n            , let ns = show n\n            , z <- \"0123456789\"]   \n\n-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas\n-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos\n-- distintos. Por ejemplo,\n--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]\n--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]\nmezcla :: Ord a => [a] -> [a] -> [a]\nmezcla us@(x:xs) vs@(y:ys)\n  | x < y     = x : mezcla xs vs\n  | otherwise = y : mezcla us ys\n\n-- 3\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas3 :: [Integer]\ncapicuas3 = iterate sigCapicua 0\n\n-- (sigCapicua x) es el capic\u00faa siguiente del n\u00famero x. Por ejemplo,\n--    sigCapicua 12321           == 12421\n--    sigCapicua 1298921         == 1299921\n--    sigCapicua 999             == 1001\n--    sigCapicua 9999            == 10001\n--    sigCapicua 898             == 909\n--    sigCapicua 123456777654321 == 123456787654321\nsigCapicua :: Integer -> Integer\nsigCapicua n = read cs\n    where l  = length (show (n+1))\n          k  = l `div` 2\n          xs = show ((n `div` (10^k)) + 1) \n          cs = xs ++ drop (l `rem` 2) (reverse xs)\n\n-- 4\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas4 :: [Integer]\ncapicuas4 =\n  concatMap generaCapicuas4 [1..]\n\ngeneraCapicuas4 :: Integer -> [Integer]\ngeneraCapicuas4 1 = [0..9]\ngeneraCapicuas4 n\n  | even n    = [read (xs ++ reverse xs)\n                | xs <- map show [10^(m-1)..10^m-1]]\n  | otherwise = [read (xs ++ (y : reverse xs))\n                | xs <- map show [10^(m-1)..10^m-1]\n                , y <- \"0123456789\"]\n  where m = n `div` 2\n\n-- 5\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas5 :: [Integer]\ncapicuas5 = 0 : aux 1\n  where aux n =    [read (show x ++ tail (reverse (show x)))\n                   | x <- [10^(n-1)..10^n-1]]\n                ++ [read (show x ++ reverse (show x))\n                   | x <- [10^(n-1)..10^n-1]]\n                ++ aux (n+1)\n\n-- 6\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas6 :: [Integer]\ncapicuas6 = 0 : map read (capicuas6Aux [1..9])\n \ncapicuas6Aux :: [Integer] -> [String]\ncapicuas6Aux xs =  map duplica1 ys\n                ++ map duplica2 ys\n                ++ capicuas6Aux [head xs * 10 .. last xs * 10 + 9]\n  where\n    ys          = map show xs\n    duplica1 cs = cs ++ tail (reverse cs)\n    duplica2 cs = cs ++ reverse cs\n\n-- 7\u00aa definici\u00f3n de capicuas\n-- =========================\n\ncapicuas7 :: [Integer]\ncapicuas7 = 0 : map read (capicuas7Aux [1..9])\n \ncapicuas7Aux :: [Integer] -> [String]\ncapicuas7Aux xs =  map duplica1 ys\n                ++ map duplica2 ys\n                ++ capicuas7Aux [head xs * 10 .. last xs * 10 + 9]\n  where\n    ys       = map show xs\n    duplica1 = (++) <$> id <*> tail . reverse\n    duplica2 = (++) <$> id <*> reverse\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> capicuas1 !! 2000\n--    1001001\n--    (2.25 secs, 598,879,552 bytes)\n--    \u03bb> capicuas2 !! 2000\n--    1001001\n--    (0.05 secs, 28,630,552 bytes)\n--    \u03bb> capicuas3 !! 2000\n--    1001001\n--    (0.06 secs, 14,721,360 bytes)\n--    \u03bb> capicuas4 !! 2000\n--    1001001\n--    (0.01 secs, 0 bytes)\n--    \u03bb> capicuas5 !! 2000\n--    1001001\n--    (0.01 secs, 0 bytes)\n--    \u03bb> capicuas6 !! 2000\n--    1001001\n--    (0.01 secs, 0 bytes)\n--    \u03bb> capicuas7 !! 2000\n--    1001001\n--    (0.01 secs, 0 bytes)\n--    \n--    \u03bb> capicuas2 !! (10^5)\n--    900010009\n--    (2.03 secs, 1,190,503,952 bytes)\n--    \u03bb> capicuas3 !! (10^5)\n--    900010009\n--    (5.12 secs, 1,408,876,328 bytes)\n--    \u03bb> capicuas4 !! (10^5)\n--    900010009\n--    (0.21 secs, 8,249,296 bytes)\n--    \u03bb> capicuas5 !! (10^5)\n--    900010009\n--    (0.10 secs, 31,134,176 bytes)\n--    \u03bb> capicuas6 !! (10^5)\n--    900010009\n--    (0.14 secs, 55,211,272 bytes)\n--    \u03bb> capicuas7 !! (10^5)\n--    900010009\n--    (0.03 secs, 0 bytes)\n\n-- 1\u00aa definici\u00f3n de posicionCapicua\nposicionCapicua1 :: Integer -> Integer\nposicionCapicua1 x =\n  genericLength (takeWhile (< x) capicuas7)\n\n-- 2\u00aa definici\u00f3n\nposicionCapicua2 :: Integer -> Integer\nposicionCapicua2 x\n  | even n    = read ('1' : take (n `div` 2) xs) - 1\n  | otherwise = read (show (1 + read [y]) ++ take (n `div` 2) ys) - 1\n  where xs@(y:ys) = show x\n        n         = genericLength xs\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> posicionCapicua1 (10^9 - 1)\n--    109998\n--    (1.98 secs, 1,112,991,520 bytes)\n--    \u03bb> posicionCapicua2 (10^9 - 1)\n--    109998\n--    (0.01 secs, 0 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones capicuas :: [Integer] posicionCapicua :: Integer -> Integer tales que capicuas es la sucesi\u00f3n de los n\u00fameros capic\u00faas. Por ejemplo, \u03bb> 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] \u03bb> capicuas !! (10^5) 900010009 (posicionCapicua x) es la posici\u00f3n del n\u00famero capic\u00faa x en la sucesi\u00f3n de los capic\u00faas. Por ejemplo, \u03bb> posicionCapicua 353&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[8,30,91,258,11,95,6,32,33,47,34],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2800"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=2800"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2800\/revisions"}],"predecessor-version":[{"id":2838,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2800\/revisions\/2838"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2800"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2800"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2800"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}