{"id":6835,"date":"2019-11-13T11:26:21","date_gmt":"2019-11-13T10:26:21","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6835"},"modified":"2019-11-17T11:27:03","modified_gmt":"2019-11-17T10:27:03","slug":"i1m2019-el-algoritmo-de-luhn","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2019-el-algoritmo-de-luhn\/","title":{"rendered":"I1M2019: El algoritmo de Luhn"},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado soluciones a ejercicios de la relaci\u00f3n 6 sobre el algoritmo de Luhn.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Introducci\u00f3n                                                     --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es estudiar un algoritmo para validar\n-- algunos identificadores num\u00e9ricos como los n\u00fameros de algunas tarjetas\n-- de cr\u00e9dito; por ejemplo, las de tipo Visa o Master Card.  \n--\n-- El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente\n-- en aplicar los siguientes pasos a los d\u00edgitos del n\u00famero de la\n-- tarjeta.    \n--    1. Se invierten los d\u00edgitos del n\u00famero; por ejemplo, [9,4,5,5] se\n--       transforma en [5,5,4,9].\n--    2. Se duplican los d\u00edgitos que se encuentra en posiciones impares\n--       (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma\n--       en [5,10,4,18].\n--    3. Se suman los d\u00edgitos de cada n\u00famero; por ejemplo, [5,10,4,18]\n--       se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.\n--    4. Si el \u00faltimo d\u00edgito de la suma es 0, el n\u00famero es v\u00e1lido; y no\n--       lo es, en caso contrario. \n--\n-- A los n\u00fameros v\u00e1lidos, los llamaremos n\u00fameros de Luhn. \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    digitosInv :: Integer -> [Integer]\n-- tal que (digitosInv n) es la lista de los d\u00edgitos del n\u00famero n. en\n-- orden inverso. Por ejemplo, \n--    digitosR 320274  ==  [4,7,2,0,2,3]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\ndigitosInv :: Integer -> [Integer]\ndigitosInv n\n  | n < 10    = [n]\n  | otherwise = (n `rem` 10) : digitosInv (n `div` 10)\n\n-- 2\u00aa soluci\u00f3n\ndigitosInv2 :: Integer -> [Integer]\ndigitosInv2 n = [read [x] | x <- reverse (show n)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    doblePosImpar :: [Integer] -> [Integer]\n-- tal que (doblePosImpar ns) es la lista obtenida doblando los\n-- elementos en las posiciones impares (empezando a contar en cero y\n-- dejando igual a los que est\u00e1n en posiciones pares. Por ejemplo,\n--    doblePosImpar [4,9,5,5]    ==  [4,18,5,10] \n--    doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\ndoblePosImpar :: [Integer] -> [Integer]\ndoblePosImpar []       = []\ndoblePosImpar [x]      = [x]\ndoblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n)\ndoblePosImpar2 :: [Integer] -> [Integer]\ndoblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs\ndoblePosImpar2 xs       = xs\n\n-- 3\u00aa definici\u00f3n (por comprensi\u00f3n)\ndoblePosImpar3 :: [Integer] -> [Integer]\ndoblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]\n  where f n x | odd n     = 2*x \n              | otherwise = x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    sumaDigitos :: [Integer] -> Integer\n-- tal que (sumaDigitos ns) es la suma de los d\u00edgitos de ns. Por\n-- ejemplo, \n--    sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =\n--                            = 19\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n):\nsumaDigitos :: [Integer] -> Integer\nsumaDigitos ns = sum [sum (digitosInv n) | n <- ns]\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n):\nsumaDigitos2 :: [Integer] -> Integer\nsumaDigitos2 []     = 0\nsumaDigitos2 (n:ns) = sum (digitosInv n) + sumaDigitos2 ns\n\n-- 3\u00aa definici\u00f3n (con orden superior):\nsumaDigitos3 :: [Integer] -> Integer\nsumaDigitos3 = sum . map (sum . digitosInv)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n  \n--    ultimoDigito :: Integer -> Integer\n-- tal que (ultimoDigito n) es el \u00faltimo d\u00edgito de n. Por ejemplo,\n--    ultimoDigito 123 == 3\n--    ultimoDigito   0 == 0\n-- ---------------------------------------------------------------------\n\nultimoDigito :: Integer -> Integer\nultimoDigito n = n `rem` 10\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n \n--    luhn :: Integer -> Bool\n-- tal que (luhn n) se verifica si n es un n\u00famero de Luhn. Por ejemplo,\n--    luhn 5594589764218858  ==  True\n--    luhn 1234567898765432  ==  False\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nluhn :: Integer -> Bool\nluhn n = \n  ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0\n\n-- 2\u00aa soluci\u00f3n\nluhn2 =\n  (==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Referencias                                                      --\n-- ---------------------------------------------------------------------\n\n-- Esta relaci\u00f3n es una adaptaci\u00f3n del primer trabajo del curso \"CIS 194:\n-- Introduction to Haskell (Spring 2015)\" de la Univ. de Pensilvania,\n-- impartido por Noam Zilberstein. El trabajo se encuentra en\n-- http:\/\/www.cis.upenn.edu\/~cis194\/hw\/01-intro.pdf  \n-- \n-- En el art\u00edculo [Algoritmo de Luhn](http:\/\/bit.ly\/1FGGWsC) de la\n-- Wikipedia se encuentra informaci\u00f3n del algoritmo\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado soluciones a ejercicios de la relaci\u00f3n 6 sobre el algoritmo de Luhn. Los ejercicios y su soluci\u00f3n 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":[331],"tags":[],"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\/6835"}],"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=6835"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6835\/revisions"}],"predecessor-version":[{"id":6836,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6835\/revisions\/6836"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6835"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6835"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6835"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}