{"id":3136,"date":"2017-03-27T06:00:07","date_gmt":"2017-03-27T04:00:07","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3136"},"modified":"2017-04-03T08:29:18","modified_gmt":"2017-04-03T06:29:18","slug":"orden-simetrico","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/orden-simetrico\/","title":{"rendered":"Orden sim\u00e9trico"},"content":{"rendered":"<p>Dada una lista de cadenas ordenadas por longitud, se puede ordenar de manera sim\u00e9trica colocando la primera cadena en primer lugar, la segunda en el \u00faltimo, la tercera en el segundo, la cuarta en el pen\u00faltimo y as\u00ed sucesivamente.<\/p>\n<p>Por ejemplo, dada la lista<\/p>\n<pre lang=\"text\">\n   Pi\n   Eva\n   Luis\n   Paula\n   Alberto\n   Francisco\n<\/pre>\n<p>su ordenaci\u00f3n sim\u00e9trica es<\/p>\n<pre lang=\"text\">\n   Pi\n   Luis\n   Alberto\n   Francisco\n   Paula\n   Eva\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   simetrica :: [String] -> [String]\n<\/pre>\n<p>tal que (simetrica xs) es la ordenaci\u00f3n sim\u00e9trica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> simetrica [\"Pi\",\"Eva\",\"Luis\",\"Paula\",\"Alberto\",\"Francisco\"]\n   [\"Pi\",\"Luis\",\"Alberto\",\"Francisco\",\"Paula\",\"Eva\"]\n   \u03bb> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^6]]\n   \"a\"\n<\/pre>\n<p><strong>Nota<\/strong>: Este ejercicio est\u00e1 basado en el problema <a href=\"http:\/\/bit.ly\/2mEEipG\">Symmetric order<\/a> de <a href=\"https:\/\/open.kattis.com\">Kattis<\/a>.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa definici\u00f3n\nsimetrica1 :: [String] -> [String]\nsimetrica1 []       = []\nsimetrica1 [x]      = [x]\nsimetrica1 (x:y:xs) = x : simetrica1 xs ++ [y]\n\n-- 2\u00aa definici\u00f3n\nsimetrica2 :: [String] -> [String]\nsimetrica2 xs = aux xs []\n  where aux (x:y:xs) ys = x : aux xs (y:ys)\n        aux (x:xs) ys   = x : aux xs ys\n        aux [] ys       = ys\n\n\n-- 3\u00aa definici\u00f3n\nsimetrica3 :: [String] -> [String]\nsimetrica3 xs = aux xs []\n  where aux (x:y:xs) ys = x : aux xs (y:ys)\n        aux xs ys       = xs ++ ys\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> minimum $ simetrica1 [replicate k 'a' | k <- [1..2*10^4]]\n--    \"a\"\n--    (11.30 secs, 8,600,879,688 bytes)\n--    \u03bb> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^4]]\n--    \"a\"\n--    (0.06 secs, 12,419,568 bytes)\n--    \u03bb> minimum $ simetrica3 [replicate k 'a' | k <- [1..2*10^4]]\n--    \"a\"\n--    (0.06 secs, 11,320,264 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Dada una lista de cadenas ordenadas por longitud, se puede ordenar de manera sim\u00e9trica colocando la primera cadena en primer lugar, la segunda en el \u00faltimo, la tercera en el segundo, la cuarta en el pen\u00faltimo y as\u00ed sucesivamente. Por ejemplo, dada la lista Pi Eva Luis Paula Alberto Francisco su ordenaci\u00f3n sim\u00e9trica es Pi&#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":[6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3136"}],"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=3136"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3136\/revisions"}],"predecessor-version":[{"id":3170,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3136\/revisions\/3170"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3136"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3136"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}