{"id":5368,"date":"2016-03-16T15:44:25","date_gmt":"2016-03-16T14:44:25","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5368"},"modified":"2016-03-21T15:45:25","modified_gmt":"2016-03-21T14:45:25","slug":"i1m2015-4o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-4o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2015: 4\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 4\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica<\/a> (de 1\u00ba de Grado en Matem\u00e1ticas). Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n<p><!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.Array\nimport Data.Char\nimport Data.Numbers.Primes\nimport qualified Data.Matrix as M\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    siguiente :: Eq a => a -> [a] -> Maybe a\n-- tal que (siguiente x ys) es justo el elemento siguiente a la primera \n-- ocurrencia de x en ys o Nothing si x no pertenece a ys. Por ejemplo,\n--    siguiente 5 [3,5,2,5,7]                       ==  Just 2\n--    siguiente 9 [3,5,2,5,7]                       ==  Nothing\n--    siguiente 'd' \"afdegdb\"                       ==  Just 'e'\n--    siguiente \"todo\" [\"En\",\"todo\",\"la\",\"medida\"]  ==  Just \"la\"\n--    siguiente \"nada\" [\"En\",\"todo\",\"la\",\"medida\"]  ==  Nothing\n--    siguiente 999999 [1..1000000]                 ==  Just 1000000\n--    siguiente 1000000 [1..1000000]                ==  Nothing\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n (por recursi\u00f3n):\nsiguiente1 :: Eq a => a -> [a] -> Maybe a\nsiguiente1 x (y1:y2:ys) | x == y1   = Just y2\n                        | otherwise = siguiente1 x (y2:ys)\nsiguiente1 x _ = Nothing\n\n-- 2\u00aa soluci\u00f3n (por comprensi\u00f3n):\nsiguiente2 :: Eq a => a -> [a] -> Maybe a\nsiguiente2 x ys \n    | null zs   = Nothing\n    | otherwise = Just (snd (head zs))\n    where zs = [(u,v) | (u,v) <- zip ys (tail ys), u == x]  \n\n-- 3\u00aa soluci\u00f3n (con dropWhile)\nsiguiente3 :: Eq a => a -> [a] -> Maybe a\nsiguiente3 x = aux . drop 1 . dropWhile (\/=x)\n    where aux []    = Nothing\n          aux (y:_) = Just y\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    ghci> let n=10^6 in siguiente1 (n-1) [1..n]\n--    Just 1000000\n--    (1.34 secs, 277352616 bytes)\n--    \n--    ghci> let n=10^6 in siguiente2 (n-1) [1..n]\n--    Just 1000000\n--    (1.45 secs, 340836576 bytes)\n--    \n--    ghci> let n=10^6 in siguiente3 (n-1) [1..n]\n--    Just 1000000\n--    (0.26 secs, 84987544 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Un n\u00famero n es k-belga si la sucesi\u00f3n cuyo primer\n-- elemento es k y cuyos elementos se obtienen sumando reiteradamente\n-- los d\u00edgitos de n contiene a n. Por ejemplo,\n-- + El 18 es 0-belga, porque a partir del 0 vamos a ir sumando\n--   sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1,\n--   9, 10, 18, ... Como se alcanza el 18, resulta que el 18 es 0-belga. \n-- + El 19 no es 1-belga, porque a partir del 1 vamos a ir sumando\n--   sucesivamente 1, 9, 1, 9, ... hasta llegar o sobrepasar el 18: 1, 2,\n--   11, 12, 21, 22, ... Como no se alcanza el 19, resulta que el 19 no es\n--   1-belga. \n--\n-- Definir la funci\u00f3n \n--    esBelga :: Int -> Int -> Bool\n-- tal que (esBelga k n)  se verifica si n es k-belga. Por ejemplo,\n--    esBelga 0 18                              ==  True\n--    esBelga 1 19                              ==  False\n--    esBelga 0 2016                            ==  True\n--    [x | x <- [0..30], esBelga 7 x]           ==  [7,10,11,21,27,29]\n--    [x | x <- [0..30], esBelga 10 x]          ==  [10,11,20,21,22,24,26]\n--    length [n | n <- [1..9000], esBelga 0 n]  ==  2857\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesBelga1 :: Int -> Int -> Bool\nesBelga1 k n =\n    n == head (dropWhile (<n) (scanl (+) k (cycle (digitos n))))\n\ndigitos :: Int -> [Int]\ndigitos n = map digitToInt (show n)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesBelga2 :: Int -> Int -> Bool\nesBelga2 k n =\n    k <= n &#038;&#038; n == head (dropWhile (<n) (scanl (+) (k + q * s) ds))\n    where ds = digitos n\n          s  = sum ds\n          q  = (n - k) `div` s\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> length [n | n <- [1..9000], esBelga1 0 n]\n--    2857\n--    (2.95 secs, 1,115,026,728 bytes)\n--    \u03bb> length [n | n <- [1..9000], esBelga2 0 n]\n--    2857\n--    (0.10 secs, 24,804,480 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Los \u00e1rboles binarios con datos en los nodos y hojas se\n-- definen por \n--    data Arbol a = H a\n--                 | N a (Arbol a) (Arbol a) \n--                 deriving (Eq, Show)\n-- Por ejemplo, el \u00e1rbol \n--           3\n--          \/ \\\n--         \/   \\\n--        4     7\n--       \/ \\   \/ \\\n--      5   0 0   3\n--     \/ \\\n--    2   0   \n-- se representa por\n--    ejArbol :: Arbol Integer\n--    ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))\n--\n-- Anotando cada elemento del \u00e1rbol anterior con su profundidad, se\n-- obtiene el \u00e1rbol siguiente  \n--           3-0\n--           \/ \\\n--          \/   \\\n--         \/     \\\n--       4-1     7-1\n--       \/ \\     \/ \\\n--     5-2 0-2 0-2 3-2\n--     \/ \\\n--   2-3 0-3   \n--\n-- Definir la funci\u00f3n \n--    anotado :: Arbol a -> Arbol (a,Int)\n-- tal que (anotado x) es el \u00e1rbol obtenido anotando los elementos de x\n-- con su profundidad. Por ejemplo,\n--    \u03bb> anotado ejArbol\n--    N (3,0) \n--      (N (4,1) \n--         (N (5,2) (H (2,3)) (H (0,3))) \n--         (H (0,2))) \n--      (N (7,1) (H (0,2)) (H (3,2)))\n-- ---------------------------------------------------------------------\n\ndata Arbol a = H a \n             | N a (Arbol a) (Arbol a) \n             deriving (Eq, Show)\n\nejArbol :: Arbol Integer\nejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nanotado1 :: Arbol a -> Arbol (a,Int)\nanotado1 (H x)     = H (x,0)\nanotado1 (N x i d) = aux (N x i d) 0\n    where aux (H x)     n = H (x,n)\n          aux (N x i d) n = N (x,n) (aux i (n+1)) (aux d (n+1))  \n\n-- 2\u00aa soluci\u00f3n\nanotado2 :: Arbol a -> Arbol (a, Int)\nanotado2 a = aux a [0..]\n    where aux (H a)     (n:_ ) = H (a,n)\n          aux (N a i d) (n:ns) = N (a,n) (aux i ns) (aux d ns)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. El pasado 11 de marzo se ha publicado el art\u00edculo\n-- \"Unexpected biases in the distribution of consecutive primes\" en el\n-- que muestra que los n\u00fameros primos repelen a otros primos que\n-- terminan en el mismo d\u00edgito. \n--\n-- La lista de los \u00faltimos d\u00edgitos de los 30 primeros n\u00fameros es\n--    [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3]\n-- Se observa que hay 6 n\u00fameros que su \u00faltimo d\u00edgito es un 1 y de sus\n-- consecutivos 4 terminan en 3 y 2 terminan en 7.\n--\n-- Definir la funci\u00f3n \n--    distribucionUltimos :: Int -> M.Matrix Int\n-- tal que (distribucionUltimos n) es la matriz cuyo elemento (i,j)\n-- indica cu\u00e1ntos de los n primeros n\u00fameros primos terminan en i y su\n-- siguiente n\u00famero primo termina en j. Por ejemplo,\n--    \u03bb> distribucionUltimos 30\n--    ( 0 0 4 0 0 0 2 0 0 )\n--    ( 0 0 1 0 0 0 0 0 0 )\n--    ( 0 0 0 0 1 0 4 0 4 )\n--    ( 0 0 0 0 0 0 0 0 0 )\n--    ( 0 0 0 0 0 0 1 0 0 )\n--    ( 0 0 0 0 0 0 0 0 0 )\n--    ( 4 0 1 0 0 0 0 0 2 )\n--    ( 0 0 0 0 0 0 0 0 0 )\n--    ( 2 0 3 0 0 0 1 0 0 )\n--    \n--    \u03bb> distribucionUltimos (10^5)\n--    ( 4104    0 7961    0    0    0 8297    0 4605 )\n--    (    0    0    1    0    0    0    0    0    0 )\n--    ( 5596    0 3604    0    1    0 7419    0 8387 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    (    0    0    0    0    0    0    1    0    0 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 6438    0 6928    0    0    0 3627    0 8022 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 8830    0 6513    0    0    0 5671    0 3995 )\n--\n-- Nota: Se observa c\u00f3mo se \"repelen\" ya que en las filas del 1, 3, 7 y\n-- 9 el menor elemento es el de la diagonal.\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndistribucionUltimos1 :: Int -> M.Matrix Int\ndistribucionUltimos1 n =\n    M.matrix 9 9 \n             (\\(i,j) -> length (filter (==(i,j)) (take n ultimosConsecutivos)))\n\n-- (ultimo n) es el \u00faltimo d\u00edgito de n.    \nultimo :: Int -> Int\nultimo n = n `mod` 10\n\n-- ultimos es la lista de el \u00faltimo d\u00edgito de los primos.\n--    \u03bb> take 20 ultimos\n--    [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1]\nultimos :: [Int]\nultimos = map ultimo primes\n\n-- ultimosConsecutivos es la lista de los \u00faltimos d\u00edgitos de los primos\n-- consecutivos. \n--    \u03bb> take 10 ultimosConsecutivos\n--    [(2,3),(3,5),(5,7),(7,1),(1,3),(3,7),(7,9),(9,3),(3,9),(9,1)]\nultimosConsecutivos :: [(Int,Int)]\nultimosConsecutivos = zip ultimos (tail ultimos)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndistribucionUltimos2 :: Int -> M.Matrix Int\ndistribucionUltimos2 n =\n    M.fromList 9 9 \n               (elems (histograma ((1,1),(9,9)) (take n ultimosConsecutivos)))\n\n-- (histograma r is) es el vector formado contando cuantas veces\n-- aparecen los elementos del rango r en la lista de \u00edndices is. Por\n-- ejemplo, \n--    ghci> histograma (0,5) [3,1,4,1,5,4,2,7]\n--    array (0,5) [(0,0),(1,2),(2,1),(3,1),(4,2),(5,1)]\nhistograma :: (Ix a, Num b) => (a,a) -> [a] -> Array a b\nhistograma r is = \n    accumArray (+) 0 r [(i,1) | i <- is, inRange r i]\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\ndistribucionUltimos3 :: Int -> M.Matrix Int\ndistribucionUltimos3 n \n    | n < 4 = distribucionUltimos1 n\n    | otherwise =  M.matrix 9 9 (\\(i,j) -> f i j)\n    where f i j | elem (i,j) [(2,3),(3,5),(5,7)] = 1\n                | even i || even j = 0\n                | otherwise = length (filter (==(i,j))\n                                             (take n ultimosConsecutivos))\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> distribucionUltimos1 (10^5)\n--    ( 4104    0 7961    0    0    0 8297    0 4605 )\n--    (    0    0    1    0    0    0    0    0    0 )\n--    ( 5596    0 3604    0    1    0 7419    0 8387 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    (    0    0    0    0    0    0    1    0    0 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 6438    0 6928    0    0    0 3627    0 8022 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 8830    0 6513    0    0    0 5671    0 3995 )\n--    \n--    (3.51 secs, 941,474,520 bytes)\n--    \u03bb> distribucionUltimos2 (10^5)\n--    ( 4104    0 7961    0    0    0 8297    0 4605 )\n--    (    0    0    1    0    0    0    0    0    0 )\n--    ( 5596    0 3604    0    1    0 7419    0 8387 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    (    0    0    0    0    0    0    1    0    0 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 6438    0 6928    0    0    0 3627    0 8022 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 8830    0 6513    0    0    0 5671    0 3995 )\n--    \n--    (1.75 secs, 560,891,792 bytes)\n--    \u03bb> distribucionUltimos3 (10^5)\n--    ( 4104    0 7961    0    0    0 8297    0 4605 )\n--    (    0    0    1    0    0    0    0    0    0 )\n--    ( 5596    0 3604    0    1    0 7419    0 8387 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    (    0    0    0    0    0    0    1    0    0 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 6438    0 6928    0    0    0 3627    0 8022 )\n--    (    0    0    0    0    0    0    0    0    0 )\n--    ( 8830    0 6513    0    0    0 5671    0 3995 )\n--    \n--    (1.70 secs, 623,371,360 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 4\u00ba examen del curso de Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas). Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[250],"tags":[270,310],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5368"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5368"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5368\/revisions"}],"predecessor-version":[{"id":5369,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5368\/revisions\/5369"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}