El algoritmo de Damm

PorJosé A. Alonso 15-mayo-20172-agosto-2023

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

| 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

1	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]

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

1	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

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

[schedule expon=’2017-05-22′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 22 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-22′ at=»06:00″]

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.

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.

[/schedule]

8 Comentarios

mDamm :: M.Matrix Int
mDamm = M.fromList 10 10 [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,9,
                          2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int
digitoControl x = last (aux (digitoFila x))
          where aux (x:xs) = buscaNumero 1 (x:xs)

buscaNumero :: Int -> [Int] -> [Int]
buscaNumero y [] = []
buscaNumero y [x] = [mDamm M.! (y,x)]
buscaNumero y (x:xs) = (mDamm M.! (y,x)):(buscaNumero (mDamm M.! (y,x) +1) xs)

digitoFila n = map (+1) (digitos n)

digitos :: Int -> [Int]
digitos n = [read [x] | x <- show n ]



prop x = x>0 ==> digitoControl (read((show x)++show(digitoControl x)))==0
-- λ> quickCheck prop
-- +++ OK, passed 100 tests.

mDamm :: M.Matrix Int

mDamm = M.fromList 10 10 [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,9,

2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int

digitoControl x = last (aux (digitoFila x))

where aux (x:xs) = buscaNumero 1 (x:xs)

buscaNumero :: Int -> [Int] -> [Int]

buscaNumero y [] = []

buscaNumero y [x] = [mDamm M.! (y,x)]

buscaNumero y (x:xs) = (mDamm M.! (y,x)):(buscaNumero (mDamm M.! (y,x) +1) xs)

digitoFila n = map (+1) (digitos n)

digitos :: Int -> [Int]

digitos n = [read [x] | x <- show n ]

prop x = x>0 ==> digitoControl (read((show x)++show(digitoControl x)))==0

-- λ> quickCheck prop

-- +++ OK, passed 100 tests.

Responder

import Data.Array
import Data.Char (digitToInt)
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,9,
                                 2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int
digitoControl = foldl (curry (mDamm !)) 0 . map digitToInt . show

propDamm :: Int -> Property
propDamm x = x > 0 ==> digitoControl (x * 10 + digitoControl x) == 0

import Data.Array

import Data.Char (digitToInt)

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,9,

2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int

digitoControl = foldl (curry (mDamm !)) 0 . map digitToInt . show

propDamm :: Int -> Property

propDamm x = x > 0 ==> digitoControl (x * 10 + digitoControl x) == 0

Responder

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,9,
                                    2,5,8,1,4,3,6,7,9,0]

digitoControl :: Integer -> Int
digitoControl = aux 0.map digitToInt.show
  where aux t [] = t
        aux t (x:xs) = aux (mDamm!(t,x)) xs

prop_control :: Integer -> Property
prop_control x = x >= 0 && 9 >= x  ==> 0 == digitoControl (read ((show x) ++ show (digitoControl x)))

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,9,

2,5,8,1,4,3,6,7,9,0]

digitoControl :: Integer -> Int

digitoControl = aux 0.map digitToInt.show

where aux t [] = t

aux t (x:xs) = aux (mDamm!(t,x)) xs

prop_control :: Integer -> Property

prop_control x = x >= 0 && 9 >= x ==> 0 == digitoControl (read ((show x) ++ show (digitoControl x)))

Responder

import Data.Char
import Data.Array
import Data.List
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,9,
                                 2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int
digitoControl  = foldl' (curry (mDamm !)) 0 . map digitToInt . show

prop_digitoControl :: Positive Int -> Bool
prop_digitoControl (Positive n) = digitoControl (10*n + digitoControl n) == 0

-- *Main> quickCheck prop_digitoControl
-- +++ OK, passed 100 tests.

import Data.Char

import Data.Array

import Data.List

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,9,

2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int

digitoControl = foldl' (curry (mDamm !)) 0 . map digitToInt . show

prop_digitoControl :: Positive Int -> Bool

prop_digitoControl (Positive n) = digitoControl (10*n + digitoControl n) == 0

-- *Main> quickCheck prop_digitoControl

-- +++ OK, passed 100 tests.

Responder

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,9,
                                    2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int
digitoControl n = aux 0 (show n)
  where aux n [c] = mDamm ! (n,read [c])
        aux n (c:cs) = aux n' cs
          where n' = mDamm ! (n, read [c])

prop_DC :: Int -> Bool
prop_DC n = digitoControl(read(show n' ++ show (digitoControl n'))) == 0
  where n' = abs n

-- λ> quickCheck prop_DC
-- +++ OK, passed 100 tests.

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,9,

2,5,8,1,4,3,6,7,9,0]

digitoControl :: Int -> Int

digitoControl n = aux 0 (show n)

where aux n [c] = mDamm ! (n,read [c])

aux n (c:cs) = aux n' cs

where n' = mDamm ! (n, read [c])

prop_DC :: Int -> Bool

prop_DC n = digitoControl(read(show n' ++ show (digitoControl n'))) == 0

where n' = abs n

-- λ> quickCheck prop_DC

-- +++ OK, passed 100 tests.

Responder

import Data.Array
import Test.QuickCheck

digitoControl :: Int -> Int
digitoControl n = aux m mDamm 0
              where m = [read [a] | a <- show n]
                    aux [] p n = n
                    aux (x:xs) p n = aux xs p (p!(n,x))

prop_dig :: Int -> Property
prop_dig n = n >= 0 ==>
             digitoControl (read (show n ++ show (digitoControl n))) == 0

-- *Main> quickCheck prop_dig
-- +++ OK, passed 100 tests.

import Data.Array

import Test.QuickCheck

digitoControl :: Int -> Int

digitoControl n = aux m mDamm 0

where m = [read [a] | a <- show n]

aux [] p n = n

aux (x:xs) p n = aux xs p (p!(n,x))

prop_dig :: Int -> Property

prop_dig n = n >= 0 ==>

digitoControl (read (show n ++ show (digitoControl n))) == 0

-- *Main> quickCheck prop_dig

-- +++ OK, passed 100 tests.

Responder

irenlinea dice:

18-julio-2023 a las 03:24

El valor en la posición: (8,9) es incorrecto (#9), el valor que falta y cual es correcto es el #5

Responder
1. José A. Alonso dice:
  
  2-agosto-2023 a las 13:51
  
  Gracias, ya está corregido.
  
  Responder

El algoritmo de Damm

Soluciones

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico