{"id":6284,"date":"2021-04-20T06:00:47","date_gmt":"2021-04-20T04:00:47","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6284"},"modified":"2021-04-27T08:33:22","modified_gmt":"2021-04-27T06:33:22","slug":"cuadriseguidos-y-numeros-encadenados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/cuadriseguidos-y-numeros-encadenados\/","title":{"rendered":"Cuadriseguidos y n\u00fameros encadenados"},"content":{"rendered":"<p>El enunciado del <a href=\"https:\/\/bit.ly\/3wEcB0h\">primer problema de este mes de la RSME<\/a> es el siguiente:<\/p>\n<blockquote><p>\n  Un entero positivo de dos o m\u00e1s cifras se denomina <strong>cuadriseguido<\/strong> si cada par de  d\u00edgitos consecutivos que tenga es un cuadrado perfecto. Por ejemplo,<\/p>\n<ul>\n<li>364 es cuadriseguido, pues 36 = 6^2 y 64 = 8^2<\/li>\n<li>3642 no lo es porque 42 no es un cuadrado perfecto.<\/li>\n<\/ul>\n<p>  Obt\u00e9n todos los n\u00fameros cuadriseguidos posibles.\n  <\/p><\/blockquote>\n<\/blockquote>\n<p>El concepto de cuadriseguido se puede generalizar como sigue: Un entero positivo n de dos o m\u00e1s cifras se denomina <strong>encadenado<\/strong> respecto de una lista de n\u00fameros de dos d\u00edgitos xs si cada par de d\u00edgitos consecutivos que tenga es un elemento distinto de xs. Por ejemplo,<\/p>\n<ul>\n<li>364 es encadenado respecto de xs = [36,64,15], porque 36 y 64 pertenecen a xs<\/li>\n<li>3642 no es encadenado respecto de xs = [36,64,15], porque 42 no pertenece a xs<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   encadenados :: [Integer] -> [Integer]\n<\/pre>\n<p>tal que (encadenados xs) es la lista de los n\u00fameros encadenados respecto de xs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> encadenados [12,23,31]\n   [12,23,31,123,231,312,1231,2312,3123]\n   \u03bb> encadenados [12,22,31]\n   [12,22,31,122,312,3122]\n   \u03bb> take 14 (encadenados [n^2 | n <- [4..9]])\n   [16,25,36,49,64,81,164,364,649,816,1649,3649,8164,81649]\n   \u03bb> length (encadenados [10..42])\n   911208\n<\/pre>\n<p>Calcular todos los n\u00fameros cuadriseguidos posibles usando la funci\u00f3n encadenados.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (delete, sort)\nimport Data.Tree (Tree (Node), drawTree)\nimport Test.QuickCheck (Gen, choose, sublistOf, quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nencadenados :: [Integer] -> [Integer]\nencadenados xs =\n  filter (esEncadenado xs) [10..10^(2 * length xs) - 1]\n\n-- (esEncadenado xs n) se verifica si n es un n\u00famero encadenado respecto\n-- de xs. Por ejemplo,\n--    esEncadenado [36,64,15] 364   ==  True\n--    esEncadenado [36,64,15] 3642  ==  False\n--    esEncadenado [36,63] 3636     ==  False\nesEncadenado :: [Integer] -> Integer -> Bool\nesEncadenado xs n =\n  dosConsecutivos n `contenido` xs\n\n-- (dosConsecutivos n) es la lista de los n\u00fameros formados por dos\n-- d\u00edgitos consecutivos de xs. Por ejemplo,\n--    dosConsecutivos 81649  ==  [81,16,64,49]\ndosConsecutivos :: Integer -> [Integer]\ndosConsecutivos n =\n  map read [[x,y] | (x,y) <- zip xs (tail xs)]\n  where xs = show n\n\n-- Otra definici\u00f3n alternativa\ndosConsecutivos2 :: Integer -> [Integer]\ndosConsecutivos2 = reverse . aux\n  where aux n\n          | n < 10    = []\n          | otherwise = n `mod` 100 : aux (n `div` 10)\n\n-- (contenido xs ys) se verifica si xs est\u00e1 contenido en ys. Por\n-- ejemplo,\n--    contenido [2,5] [3,5,2]  ==  True\n--    contenido [2,5,5] [3,5,2]  ==  False\ncontenido :: [Integer] -> [Integer] -> Bool\ncontenido [] _      = True\ncontenido (x:xs) ys = x `elem` ys && xs `contenido` (delete x ys)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nencadenados2 :: [Integer] -> [Integer]\nencadenados2 xs =\n  sort (map (digitosAnumero . cadenaReducida) (tail (nodos (arbolCadenas ps))))\n  where ps = map (`divMod` 10) xs\n\n-- (arbolCadenas ps) es el \u00e1rbol de las cadenas formadas con los\n-- elementos de ps. Por ejemplo,\n--    \u03bb> putStrLn (drawTree (fmap show (arbolCadenas [(1,2),(2,3),(3,1)])))\n--    []\n--    |\n--    +- [(1,2)]\n--    |  |\n--    |  `- [(3,1),(1,2)]\n--    |     |\n--    |     `- [(2,3),(3,1),(1,2)]\n--    |\n--    +- [(2,3)]\n--    |  |\n--    |  `- [(1,2),(2,3)]\n--    |     |\n--    |     `- [(3,1),(1,2),(2,3)]\n--    |\n--    `- [(3,1)]\n--       |\n--       `- [(2,3),(3,1)]\n--          |\n--          `- [(1,2),(2,3),(3,1)]\narbolCadenas :: Eq a => [(a,a)] -> Tree [(a,a)]\narbolCadenas ps = aux []\n  where\n    aux xs = Node xs (map aux (extensiones xs))\n    extensiones [] =\n      [[p] | p <- ps]\n    extensiones ((x,y):rs) =\n      [(a,b):(x,y):rs | (a,b) <- ps,\n                        b == x,\n                        (a,b) `notElem` ((x,y):rs)]\n\n-- (nodos a) es la lista de los nodos del \u00e1rbol a. Por ejemplo,\n--    \u03bb> nodos (arbolCadenas [(1,6),(6,4),(8,1)])\n--    [[],[(1,6)],[(8,1),(1,6)],[(6,4)],[(1,6),(6,4)],[(8,1),(1,6),(6,4)],[(8,1)]]\nnodos :: Tree [(a,a)] -> [[(a,a)]]\nnodos (Node x ys) =\n  x : concatMap nodos ys\n\n-- (cadenaReducida ps) es la lista de los elementos la cadena ps donde\n-- los enlaces solo se escriben una vez. Por ejemplo,\n--    cadenaReducida [(8,1),(1,6),(6,4),(4,9)]  ==  [8,1,6,4,9]\ncadenaReducida :: [(a,a)] -> [a]\ncadenaReducida [] = []\ncadenaReducida ((x,y):ps) = x : y : map snd ps\n\n-- (digitosAnumero xs) es el n\u00famero cuya lista de d\u00edgitos es xs. Por\n-- ejemplo,\n--    digitosAnumero [8,1,6,4,9]  ==  81649\ndigitosAnumero :: [Integer] -> Integer\ndigitosAnumero xs =\n  read (concatMap show xs)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nencadenados3 :: [Integer] -> [Integer]\nencadenados3 xs =\n  sort (map read (aux [(p,delete p ps) | p <- ps]))\n  where\n    ps = map show xs\n    aux [] = []\n    aux ((as,qs):yss)\n      | null zss  = as : aux yss\n      | otherwise = as : aux (zss ++ yss)\n      where zss = extensiones (as,qs)\n    extensiones (x:xs,cs) =\n      [(a:x:xs,delete [a,b] cs) | [a,b] <- cs, b == x]\n\n-- C\u00e1lculo de cuadriseguidos\n-- =========================\n\n-- El c\u00e1lculo es\n--    \u03bb> encadenados2 [n^2 | n <- [4..9]]\n--    [16,25,36,49,64,81,164,364,649,816,1649,3649,8164,81649]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_encadenados :: Gen Bool\nprop_encadenados = do\n  n <- choose (2,9)\n  xs <- sublistOf [10..99]\n  let ys = take n xs\n      as = encadenados3 ys\n      m  = length as\n  return (take m (encadenados ys) == as &#038;&#038;\n          encadenados2 ys == as)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_encadenados\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> encadenados [12,24,41]\n--    [12,24,41,124,241,412,1241,2412,4124]\n--    (2.23 secs, 5,189,736,248 bytes)\n--    \u03bb> encadenados2 [12,24,41]\n--    [12,24,41,124,241,412,1241,2412,4124]\n--    (0.00 secs, 188,496 bytes)\n--    \u03bb> encadenados3 [12,24,41]\n--    [12,24,41,124,241,412,1241,2412,4124]\n--    (0.01 secs, 176,376 bytes)\n--\n--    \u03bb> length (encadenados2 [10..42])\n--    911208\n--    (13.59 secs, 14,104,867,760 bytes)\n--    \u03bb> length (encadenados3 [10..42])\n--    911208\n--    (10.62 secs, 10,164,004,808 bytes)\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>El enunciado del primer problema de este mes de la RSME es el siguiente: Un entero positivo de dos o m\u00e1s cifras se denomina cuadriseguido si cada par de d\u00edgitos consecutivos que tenga es un cuadrado perfecto. Por ejemplo, 364 es cuadriseguido, pues 36 = 6^2 y 64 = 8^2 3642 no lo es porque&#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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6284"}],"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=6284"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6284\/revisions"}],"predecessor-version":[{"id":6367,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6284\/revisions\/6367"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}