El algoritmo de Luhn
El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores numéricos como los números de algunas tarjetas de crédito; por ejemplo, las de tipo Visa o Master Card.
El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente en aplicar los siguientes pasos a los dígitos del número de la tarjeta.
- Se invierten los dígitos del número; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].
- Se duplican los dígitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].
- Se suman los dígitos de cada número; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.
- Si el último dígito de la suma es 0, el número es válido; y no lo es, en caso contrario.
A los números válidos, se les llama números de Luhn.
Definir las siguientes funciones:
|
1 2 3 4 5 |
digitosInv :: Integer -> [Integer] doblePosImpar :: [Integer] -> [Integer] sumaDigitos :: [Integer] -> Integer ultimoDigito :: Integer -> Integer luhn :: Integer -> Bool |
tales que
digitosInv nes la lista de los dígitos del númeron, en orden inverso. Por ejemplo,
|
1 |
digitosInv 320274 == [4,7,2,0,2,3] |
doblePosImpar nses la lista obtenida doblando los elementos densen las posiciones impares (empezando a contar en cero y dejando igual a los que están en posiciones pares. Por ejemplo,
|
1 2 |
doblePosImpar [4,9,5,5] == [4,18,5,10] doblePosImpar [4,9,5,5,7] == [4,18,5,10,7] |
sumaDigitos nses la suma de los dígitos dens. Por ejemplo,
|
1 2 |
sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 = = 19 |
ultimoDigito nes el último dígito den. Por ejemplo,
|
1 2 |
ultimoDigito 123 == 3 ultimoDigito 0 == 0 |
luhn nse verifica sines un número de Luhn. Por ejemplo,
|
1 2 |
luhn 5594589764218858 == True luhn 1234567898765432 == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
-- Definición de digitosInv -- ======================== digitosInv :: Integer -> [Integer] digitosInv n = [read [x] | x <- reverse (show n)] -- Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T -- se presentan otras definiciones. -- Definiciones de doblePosImpar -- ============================= -- 1ª definición doblePosImpar :: [Integer] -> [Integer] doblePosImpar [] = [] doblePosImpar [x] = [x] doblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs -- 2ª definición doblePosImpar2 :: [Integer] -> [Integer] doblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs doblePosImpar2 xs = xs -- 3ª definición doblePosImpar3 :: [Integer] -> [Integer] doblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs] where f n x | odd n = 2*x | otherwise = x -- Definiciones de sumaDigitos -- =========================== sumaDigitos :: [Integer] -> Integer sumaDigitos ns = sum [sum (digitosInv n) | n <- ns] -- Nota: En el ejercicio "Suma de los dígitos de un número" -- https://bit.ly/3U4u7WR se presentan otras definiciones. -- Definición de ultimoDigito -- ========================== ultimoDigito :: Integer -> Integer ultimoDigito n = n `rem` 10 -- Definiciones de luhn -- ==================== -- 1ª definición luhn1 :: Integer -> Bool luhn1 n = ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0 -- 2ª definición luhn2 :: Integer -> Bool luhn2 = (==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Definición de digitosInv # ======================== def digitosInv(n: int) -> list[int]: return [int(x) for x in reversed(str(n))] # Nota: En el ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T # se presentan otras definiciones. # Definiciones de doblePosImpar # ============================= # 1ª definición def doblePosImpar(xs: list[int]) -> list[int]: if len(xs) <= 1: return xs return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:]) # 2ª definición def doblePosImpar2(xs: list[int]) -> list[int]: def f(n: int, x: int) -> int: if n % 2 == 1: return 2 * x return x return [f(n, x) for (n, x) in enumerate(xs)] # Definiciones de sumaDigitos # =========================== def sumaDigitos(ns: list[int]) -> int: return sum((sum(digitosInv(n)) for n in ns)) # Nota: En el ejercicio "Suma de los dígitos de un número" # https://bit.ly/3U4u7WR se presentan otras definiciones. # Definición de ultimoDigito # ========================== def ultimoDigito(n: int) -> int: return n % 10 # Definiciones de luhn # ==================== def luhn(n: int) -> bool: return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0 |