{"id":4407,"date":"2014-09-10T16:00:11","date_gmt":"2014-09-10T14:00:11","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4407"},"modified":"2014-09-13T10:28:08","modified_gmt":"2014-09-13T08:28:08","slug":"i1m2013-7o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-7o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2013: 7\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 7\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica<\/a> (de 1\u00ba de Grado en Matem\u00e1ticas). Este es el examen de la convocatoria de septiembre. 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.List\nimport Data.Array\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. [2 puntos] En una Olimpiada matem\u00e1tica de este a\u00f1o se\n-- plante\u00f3 el siguiente problema \n--    Determinar el menor entero positivo M que tiene las siguientes\n--    propiedades a la vez: \n--    * El producto de los d\u00edgitos de M es 112.\n--    * El producto de los d\u00edgitos de M+6 tambi\u00e9n es 112.\n--\n-- Definir la funci\u00f3n\n--    especiales :: Int -> Int -> [Int]\n-- tal que (especiales k a) es la lista de los n\u00fameros naturales n tales\n-- que \n--    * El producto de los d\u00edgitos de n es a.\n--    * El producto de los d\u00edgitos de n+k tambi\u00e9n es a.\n-- Por ejemplo, \n--    take 3 (especiales 8 24) == [38,138,226]\n-- En efecto,   3*8 = 24,  38+8 = 46  y   4*6 = 24\n--            2*2*6 = 24, 226+8 = 234 y 2*3*4 = 24\n--\n-- Usando la funci\u00f3n especiales, calcular la soluci\u00f3n del problema.\n-- ---------------------------------------------------------------------\n\nespeciales :: Int -> Int -> [Int]\nespeciales k a = \n    [n | n <- [1..], product (digitos n) == a,\n                     product (digitos (n+k)) == a]\n\ndigitos :: Int -> [Int]\ndigitos n = [read [c] | c <- show n]\n\n-- La soluci\u00f3n del problema es\n--    ghci> head (especiales 6 112)\n--    2718\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. [2 puntos] Las expresiones aritm\u00e9ticas pueden\n-- representarse usando el siguiente tipo de datos \n--    data Expr = N Int | S Expr Expr | P Expr Expr  \n--              deriving Show\n-- Por ejemplo, la expresi\u00f3n 2*(3+7) se representa por\n--    P (N 2) (S (N 3) (N 7))\n-- La dual de una expresi\u00f3n es la expresi\u00f3n obtenida intercambiando las\n-- sumas y los productos. Por ejemplo, la dual de 2*(3+7) es 2+(3*7).\n-- \n-- Definir la funci\u00f3n\n--    dual :: Expr -> Expr\n-- tal que (dual e) es la dual de la expresi\u00f3n e. Por ejemplo,\n--    dual (P (N 2) (S (N 3) (N 7)))  ==  S (N 2) (P (N 3) (N 7))\n-- ---------------------------------------------------------------------\n\ndata Expr = N Int | S Expr Expr | P Expr Expr  \n          deriving Show\n\ndual :: Expr -> Expr\ndual (N x)     = N x\ndual (S e1 e2) = P (dual e1) (dual e2)\ndual (P e1 e2) = S (dual e1) (dual e2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. [2 puntos] La sucesi\u00f3n con saltos se obtiene a partir de\n-- los n\u00fameros naturales saltando 1, cogiendo 2, saltando 3, cogiendo 4,\n-- saltando 5, etc. Por ejemplo, \n--    (1), 2,3, (4,5,6), 7,8,9,10, (11,12,13,14,15), 16,17,18,19,20,21, \n-- en la que se ha puesto entre par\u00e9ntesis los n\u00fameros que se salta; los\n-- que quedan son \n--    2,3, 7,8,9,10, 16,17,18,19,20,21, ...\n-- \n-- Definir la funci\u00f3n\n--    saltos :: [Integer]\n-- tal que saltos es la lista de los t\u00e9rminos de la sucesi\u00f3n con saltos. \n-- Por ejemplo,\n--    ghci> take 22 saltos\n--    [2,3, 7,8,9,10, 16,17,18,19,20,21, 29,30,31,32,33,34,35,36, 46,47]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n:\nsaltos :: [Integer]\nsaltos = aux (tail (scanl (+) 0 [1..])) \n    where aux (a:b:c:ds) = [a+1..b] ++ aux (c:ds) \n\n-- 2\u00aa soluci\u00f3n:\nsaltos2 :: [Integer]\nsaltos2 = aux [1..] [1..]\n    where aux (m:n:ns) xs = take n (drop m xs) ++ aux ns (drop (m+n) xs)\n\n-- 3\u00aa soluci\u00f3n:\nsaltos3 :: [Integer]\nsaltos3 = aux pares [1..]\n    where pares             = [(x,x+1) | x <- [1,3..]]\n          aux ((m,n):ps) xs = take n (drop m xs) ++ aux ps (drop (m+n) xs)\n\n-- 4\u00aa soluci\u00f3n:\nsaltos4 :: [Integer]\nsaltos4 = concat (map sig pares)\n    where pares     = [(x,x+1) | x <-[1,3..]]\n          sig (m,n) = take n (drop (m*(m+1) `div` 2) [1..])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. [2 puntos] (Basado en el problema 362 del proyecto\n-- Euler). El n\u00famero 54 se puede factorizar de 7 maneras distintas con\n-- factores mayores que 1\n--    54, 2\u00d727, 3\u00d718, 6\u00d79, 3\u00d73\u00d76, 2\u00d73\u00d79 y 2\u00d73\u00d73\u00d73.\n-- Si exigimos que los factores sean libres de cuadrados (es decir, que\n-- no se puedan dividir por ning\u00fan cuadrado), entonces s\u00f3lo quedan dos\n-- factorizaciones \n--    3\u00d73\u00d76 y 2\u00d73\u00d73\u00d73.\n--  \n-- Definir la funci\u00f3n \n--    factorizacionesLibresDeCuadrados :: Int -> [[Int]]\n-- tal que (factorizacionesLibresDeCuadrados n) es la lista de las\n-- factorizaciones de n libres de cuadrados. Por ejemplo,\n--    factorizacionesLibresDeCuadrados 54  ==  [[2,3,3,3],[3,3,6]]\n-- ---------------------------------------------------------------------\n\nfactorizacionesLibresDeCuadrados :: Int -> [[Int]]\nfactorizacionesLibresDeCuadrados n =\n    [xs | xs <- factorizaciones n, listaLibreDeCuadrados xs] \n\n-- (factorizaciones n) es la lista creciente de n\u00fameros mayores que 1\n-- cuyo producto es n. Por ejemplo,\n--    factorizaciones 12  ==  [[2,2,3],[2,6],[3,4],[12]]\n--    factorizaciones 54  ==  [[2,3,3,3],[2,3,9],[2,27],[3,3,6],[3,18],[6,9],[54]]\nfactorizaciones ::  Int -> [[Int]]\nfactorizaciones n = aux n 2\n    where aux 1 _ = [[]]\n          aux n a = [m:xs | m <- [a..n],\n                            n `rem` m == 0,\n                            xs <- aux (n `div` m) m]\n\n\n-- (listaLibreDeCuadrados xs) se verifica si todos los elementos de xs\n-- son libres de cuadrados. Por ejemplo,\n--    listaLibreDeCuadrados [3,6,15,10]  ==  True\n--    listaLibreDeCuadrados [3,6,15,20]  ==  False\nlistaLibreDeCuadrados :: [Int] -> Bool\nlistaLibreDeCuadrados = all libreDeCuadrado\n\n-- (libreDeCuadrado n) se verifica si n es libre de cuadrado. Por\n-- ejemplo, \n--    libreDeCuadrado 10  ==  True\n--    libreDeCuadrado 12  ==  False\nlibreDeCuadrado :: Int -> Bool\nlibreDeCuadrado n =\n    null [m | m <- [2..n], rem n (m^2) == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. [2 puntos] (Basado en el problema 196 del proyecto\n-- Euler). Para cada n\u00famero n la matriz completa de orden n es la matriz\n-- cuadrada de orden n formada por los n\u00fameros enteros consecutivos. Por\n-- ejemplo, la matriz completa de orden 3 es\n--    |1 2 3|\n--    |4 5 6|\n--    |7 8 9|\n-- las ternas primas de orden n son los listas formadas por un\n-- elemento de la matriz junto con dos de sus vecinos de manera que los\n-- tres son primos. Por ejemplo, en la matriz anterior una terna prima\n-- es [2,3,5] (formada por el elemento 2, su vecino derecho 3 y su\n-- vecino inferior 5), otra es [5,2,7] (formada por el elemento 5, su\n-- vecino superior 2 y su vecino inferior-izquierda 7) y otra es [5,3,7]\n-- (formada por el elemento 5, su vecino superior-derecha 3 y y su\n-- vecino inferior-izquierda 7).\n-- \n-- Definir la funci\u00f3n \n--    ternasPrimasOrden :: Int -> [[Int]]\n-- tal que (ternasPrimasOrden n) es el conjunto de las ternas primas de\n-- la matriz completa de orden n. Por ejemplo,\n--    ghci> ternasPrimasOrden 3\n--    [[2,3,5],[3,2,5],[5,2,3],[5,2,7],[5,3,7]]\n--    ghci> ternasPrimasOrden 4\n--    [[2,3,5],[2,3,7],[2,5,7],[3,2,7],[7,2,3],[7,2,11],[7,3,11]]\n-- ---------------------------------------------------------------------\n\nimport Data.Array\nimport Data.List\n\ntype Matriz = Array (Int,Int) Int\n\nternasPrimasOrden :: Int -> [[Int]]\nternasPrimasOrden = ternasPrimas . matrizCompleta\n\n-- (ternasPrimas p) es la lista de las ternas primas de p. Por ejemplo,  \n--    ghci> ternasPrimas (listArray ((1,1),(3,3)) [2,3,7,5,4,1,6,8,9])\n--    [[2,3,5],[3,2,7],[3,2,5],[3,7,5],[5,2,3]]\nternasPrimas :: Matriz -> [[Int]]\nternasPrimas p = \n    [xs | xs <- ternas p, all esPrimo xs]\n\n-- (ternas p) es la lista de las ternas de p formadas por un elemento de\n-- p junto con dos vecinos. Por ejemplo,  \n--    ghci>  ternas (listArray ((1,1),(3,3)) [2,3,7,5,4,0,6,8,9])\n--     [[2,3,5],[2,3,4],[2,5,4],[3,2,7],[3,2,5],[3,2,4],[3,2,0],[3,7,5],\n--      [3,7,4],[3,7,0],[3,5,4],[3,5,0],[3,4,0],[7,3,4],[7,3,0],[7,4,0],\n--      [5,2,3],[5,2,4],[5,2,6],[5,2,8],[5,3,4],[5,3,6],[5,3,8],[5,4,6],\n--      [5,4,8],[5,6,8],[4,2,3],[4,2,7],[4,2,5],[4,2,0],[4,2,6],[4,2,8],\n--      [4,2,9],[4,3,7],[4,3,5],[4,3,0],[4,3,6],[4,3,8],[4,3,9],[4,7,5],\n--      [4,7,0],[4,7,6],[4,7,8],[4,7,9],[4,5,0],[4,5,6],[4,5,8],[4,5,9],\n--      [4,0,6],[4,0,8],[4,0,9],[4,6,8],[4,6,9],[4,8,9],[0,3,7],[0,3,4],\n--      [0,3,8],[0,3,9],[0,7,4],[0,7,8],[0,7,9],[0,4,8],[0,4,9],[0,8,9],\n--      [6,5,4],[6,5,8],[6,4,8],[8,5,4],[8,5,0],[8,5,6],[8,5,9],[8,4,0],\n--      [8,4,6],[8,4,9],[8,0,6],[8,0,9],[8,6,9],[9,4,0],[9,4,8],[9,0,8]]\nternas :: Matriz -> [[Int]]\nternas p = \n    [[p!(i1,j1),p!(i2,j2),p!(i3,j3)] | \n     (i1,j1) <- indices p,\n     ((i2,j2):ps) <- tails (vecinos (i1,j1) n),\n     (i3,j3) <- ps]\n    where (_,(n,_)) = bounds p\n\n-- (vecinos (i,j) n) es la lista de las posiciones vecinas de la (i,j)\n-- en una matriz cuadrada de orden n. Por ejemplo,\n--    vecinos (2,3) 4  ==  [(1,2),(1,3),(1,4),(2,2),(2,4),(3,2),(3,3),(3,4)]\n--    vecinos (2,4) 4  ==  [(1,3),(1,4),(2,3),(3,3),(3,4)]\n--    vecinos (1,4) 4  ==  [(1,3),(2,3),(2,4)]\nvecinos :: (Int,Int) -> Int -> [(Int,Int)]\nvecinos (i,j) n = [(a,b) | a <- [max 1 (i-1)..min n (i+1)],\n                           b <- [max 1 (j-1)..min n (j+1)],\n                           (a,b) \/= (i,j)]\n\n-- (esPrimo n) se verifica si n es primo. Por ejemplo,\n--    esPrimo  7  ==  True\n--    esPrimo 15  ==  False\nesPrimo :: Int -> Bool\nesPrimo n = [x | x <- [1..n], n `rem` x == 0] == [1,n]\n\n-- (matrizCompleta n) es la matriz completa de orden n. Por ejemplo,\n--    ghci> matrizCompleta 3\n--    array ((1,1),(3,3)) [((1,1),1),((1,2),2),((1,3),3),\n--                         ((2,1),4),((2,2),5),((2,3),6),\n--                         ((3,1),7),((3,2),8),((3,3),9)]\nmatrizCompleta :: Int -> Matriz\nmatrizCompleta n =\n    listArray ((1,1),(n,n)) [1..n*n]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nternasPrimasOrden2 :: Int -> [[Int]]\nternasPrimasOrden2 = ternasPrimas2 . matrizCompleta\n\nternasPrimas2 :: Matriz -> [[Int]]\nternasPrimas2 p = \n    [[p!(i1,j1),p!(i2,j2),p!(i3,j3)] | \n     (i1,j1) <- indices p,\n     esPrimo (p!(i1,j1)),\n     ((i2,j2):ps) <- tails (vecinos (i1,j1) n),\n     esPrimo (p!(i2,j2)),\n     (i3,j3) <- ps,\n     esPrimo (p!(i3,j3))]\n    where (_,(n,_)) = bounds p\n\n-- Comparaci\u00f3n:\n--    ghci> length (ternasPrimasOrden 30)\n--    51\n--    (5.52 secs, 211095116 bytes)\n--    ghci> length (ternasPrimasOrden2 30)\n--    51\n--    (0.46 secs, 18091148 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 7\u00ba examen del curso de Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas). Este es el examen de la convocatoria de septiembre. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n","protected":false},"author":2,"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":[222],"tags":[270,300],"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\/4407"}],"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=4407"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4407\/revisions"}],"predecessor-version":[{"id":4408,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4407\/revisions\/4408"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4407"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4407"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4407"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}