Un camino es una sucesi\u00f3n de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una direcci\u00f3n y a continuaci\u00f3n en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].<\/p>\n
Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.<\/p>\n
En Haskell, las direcciones y los caminos se pueden definir por<\/p>\n
\n data Direccion = N | S | E | O deriving (Show, Eq)\n type Camino = [Direccion]\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n reducido :: Camino -> Camino\n<\/pre>\ntal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,<\/p>\n
\n reducido [] == []\n reducido [N] == [N]\n reducido [N,O] == [N,O]\n reducido [N,O,E] == [N]\n reducido [N,O,E,S] == [] \n reducido [N,O,S,E] == [N,O,S,E]\n reducido [N,S,S,E,O,N] == []\n reducido [N,S,S,E,O,N,O] == [O]\n reducido (take (10^7) (cycle [N,E,O,S])) == []\n<\/pre>\nN\u00f3tese que en el pen\u00faltimo ejemplo las reducciones son<\/p>\n
\n [N,S,S,E,O,N,O] \n --> [S,E,O,N,O] \n --> [S,N,O] \n --> [O] \n<\/pre>\nSoluciones<\/h4>\n\ndata Direccion = N | S | E | O deriving (Show, Eq)\n\ntype Camino = [Direccion]\n\n-- 1\u00aa soluci\u00f3n (por recursi\u00f3n):\nreducido1 :: Camino -> Camino\nreducido1 [] = []\nreducido1 (d:ds) | null ds' = [d]\n | d == opuesta (head ds') = tail ds'\n | otherwise = d:ds'\n where ds' = reducido1 ds\n\nopuesta :: Direccion -> Direccion\nopuesta N = S\nopuesta S = N\nopuesta E = O\nopuesta O = E\n\n-- 2\u00aa soluci\u00f3n (por plegado)\nreducido2 :: Camino -> Camino\nreducido2 = foldr aux []\n where aux N (S:xs) = xs\n aux S (N:xs) = xs\n aux E (O:xs) = xs\n aux O (E:xs) = xs\n aux x xs = x:xs\n\n-- 3\u00aa soluci\u00f3n \nreducido3 :: Camino -> Camino\nreducido3 [] = []\nreducido3 (N:S:ds) = reducido3 ds\nreducido3 (S:N:ds) = reducido3 ds\nreducido3 (E:O:ds) = reducido3 ds\nreducido3 (O:E:ds) = reducido3 ds\nreducido3 (d:ds) | null ds' = [d]\n | d == opuesta (head ds') = tail ds'\n | otherwise = d:ds'\n where ds' = reducido3 ds\n\n-- 4\u00aa soluci\u00f3n\nreducido4 :: Camino -> Camino\nreducido4 ds = reverse (aux ([],ds)) where \n aux (N:xs, S:ys) = aux (xs,ys)\n aux (S:xs, N:ys) = aux (xs,ys)\n aux (E:xs, O:ys) = aux (xs,ys)\n aux (O:xs, E:ys) = aux (xs,ys)\n aux ( xs, y:ys) = aux (y:xs,ys)\n aux ( xs, []) = xs\n\n-- Comparaci\u00f3n de eficiencia\n-- ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))\n-- []\n-- (3.87 secs, 460160736 bytes)\n-- ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))\n-- []\n-- (1.16 secs, 216582880 bytes)\n-- ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))\n-- []\n-- (0.58 secs, 98561872 bytes)\n-- ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))\n-- []\n-- (0.64 secs, 176154640 bytes)\n-- \n-- ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))\n-- []\n-- (5.43 secs, 962694784 bytes)\n-- ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))\n-- []\n-- (9.29 secs, 1722601528 bytes)\n-- \n-- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])\n-- 400002\n-- (4.52 secs, 547004960 bytes)\n-- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])\n-- 400002\n-- (2.17 secs, 379049224 bytes)\n-- \n-- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)\n-- []\n-- (7.35 secs, 537797096 bytes)\n-- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)\n-- []\n-- (2.30 secs, 244553404 bytes)\n-- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)\n-- []\n-- (8.08 secs, 545043608 bytes)\n-- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)\n-- []\n-- (1.96 secs, 205552240 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Un camino es una sucesi\u00f3n de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una direcci\u00f3n y a continuaci\u00f3n en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur]. Un camino se dice que es reducido si no tiene dos…<\/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":[7],"tags":[94,71,11,6,45],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1346"}],"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=1346"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1346\/revisions"}],"predecessor-version":[{"id":6339,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1346\/revisions\/6339"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1346"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1346"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1346"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}