El algoritmo de Damm
El algoritmo de Damm se usa en la detección de errores en códigos numéricos. Es un procedimiento para obtener un dígito de control, usando la siguiente matriz, como describimos en los ejemplos
| 0 1 2 3 4 5 6 7 8 9
--+---------------------------------------
0 | 0 3 1 7 5 9 8 6 4 2
1 | 7 0 9 2 1 5 4 8 6 3
2 | 4 2 0 6 8 7 1 3 5 9
3 | 1 7 5 0 9 8 3 4 2 6
4 | 6 1 2 3 0 4 5 9 7 8
5 | 3 6 7 4 2 0 9 5 8 1
6 | 5 8 6 9 7 2 0 1 3 4
7 | 8 9 4 5 3 6 2 0 1 7
8 | 9 4 3 8 6 1 7 2 0 5
9 | 2 5 8 1 4 3 6 7 9 0
Ejemplo 1: cálculo del dígito de control de 572
- se comienza con la fila 0 y columna 5 de la matriz -> 9
- a continuación, la fila 9 y columna 7 de la matriz -> 7
- a continuación, la fila 7 y columna 2 de la matriz -> 4
con lo que se llega al final del proceso. Entonces, el dígito de control de 572 es 4.
Ejemplo 2: cálculo del dígito de control de 57260
- se comienza con la fila 0 y columna 5 de la matriz -> 9
- a continuación, la fila 9 y columna 7 de la matriz -> 7
- a continuación, la fila 9 y columna 2 de la matriz -> 4
- a continuación, la fila 6 y columna 4 de la matriz -> 5
- a continuación, la fila 5 y columna 0 de la matriz -> 3
con lo que se llega al final del proceso. Entonces, el dígito de control de 57260 es 3.
Representamos las matrices como tablas cuyos índices son pares de números naturales.
type Matriz a = Array (Int,Int) a
Definimos la matriz:
mDamm :: Matriz Int mDamm = listArray ((0,0),(9,9)) [0,3,1,7,5,9,8,6,4,2, 7,0,9,2,1,5,4,8,6,3, 4,2,0,6,8,7,1,3,5,9, 1,7,5,0,9,8,3,4,2,6, 6,1,2,3,0,4,5,9,7,8, 3,6,7,4,2,0,9,5,8,1, 5,8,6,9,7,2,0,1,3,4, 8,9,4,5,3,6,2,0,1,7, 9,4,3,8,6,1,7,2,0,5, 2,5,8,1,4,3,6,7,9,0]
Definir la función
digitoControl :: Int -> Int
tal que (digitoControl n) es el dígito de control de n. Por ejemplo:
digitoControl 572 == 4 digitoControl 57260 == 3 digitoControl 12345689012 == 6 digitoControl 5724 == 0 digitoControl 572603 == 0 digitoControl 123456890126 == 0
Comprobar con QuickCheck que si añadimos al final de un número n su dígito de control, el dígito de control del número que resulta siempre es 0.
Soluciones
import Data.Array import Test.QuickCheck type Matriz a = Array (Int,Int) a mDamm :: Matriz Int mDamm = listArray ((0,0),(9,9)) [0,3,1,7,5,9,8,6,4,2, 7,0,9,2,1,5,4,8,6,3, 4,2,0,6,8,7,1,3,5,9, 1,7,5,0,9,8,3,4,2,6, 6,1,2,3,0,4,5,9,7,8, 3,6,7,4,2,0,9,5,8,1, 5,8,6,9,7,2,0,1,3,4, 8,9,4,5,3,6,2,0,1,7, 9,4,3,8,6,1,7,2,0,5, 2,5,8,1,4,3,6,7,9,0] -- 1ª solución digitoControl :: Int -> Int digitoControl n = aux (digitos n) 0 where aux [] d = d aux (x:xs) d = aux xs (mDamm ! (d,x)) digitos :: Int -> [Int] digitos n = [read [x] | x <- show n] -- 2ª solución: digitoControl2 :: Int -> Int digitoControl2 n = last (scanl f 0 (digitos n)) where f d x = mDamm ! (d,x) -- La propiedad es prop_DC :: Int -> Property prop_DC n = n >= 0 ==> digitoControl m == 0 where m = read (show n ++ show (digitoControl n)) -- La comprobación es -- ghci> quickCheck prop_DC -- +++ OK, passed 100 tests. -- 2ª expresión de la propiedad prop_DC2 :: Int -> Bool prop_DC2 n = digitoControl m == 0 where m = read (show (abs n) ++ show (digitoControl (abs n))) -- La comprobación es -- ghci> quickCheck prop_DC2 -- +++ OK, passed 100 tests. -- 3ª expresión de la propiedad prop_DC3 :: Int -> Bool prop_DC3 n = digitoControl (10 * n1 + digitoControl n1) == 0 where n1 = abs n -- La comprobación es -- ghci> quickCheck prop_DC3 -- +++ OK, passed 100 tests. -- 4ª expresión de la propiedad prop_DC4 :: (Positive Int) -> Bool prop_DC4 (Positive n) = digitoControl2 (10 * n + digitoControl2 n) == 0 -- La comprobación es -- ghci > quickCheck prop_DC4 -- +++ OK, passed 100 tests.