Yet Another Damm Algorithm

Wherein, stressed to the limit, we return to the salt mine to grind, grind, grind… one sodium — one chlorine — one sodium — one chlorine — assemble the parts according to the recipe, day in, day out.

THE WEEKLY CHALLENGE – PERL & RAKU #177 Task 1

---

“I drank because I wanted to drown my sorrows, but now the damned things have learned to swim.”

— Frida Kahlo

---

Damm Algorithm

Submitted by: Mohammad S Anwar

You are given a positive number, $n.

Write a script to validate the given number against the included check digit.

Please checkout the wikipedia page for information.

Example 1

Input : $n = 5724
Output: 1 as it is valid number

Example 2

Input : $n = 5727
Output: 0 as it is invalid number

What It Is

The Damm algorithm is used in data transmission error correction, and generates check digits within a stream of numbers. Given a numeric sequence, a period is pre-selected and then after every n-th digit a new computed digit is inserted; this digit can be used to verify that the values of the group before it have been accurately reported and remain unchanged. The algorithm is fast, operates on any selected length groupings, and uses the same core procedure for both encoding and decoding.

The basic stepwise process of the algorithm involves multiple lookups in a 10×10 table of digits derived from mathematical group theory. The same table is used for encoding and validation, and the algorithm is not bound to the use of one specific table. Rather a certain type of table is required, constructed from what is known as a quasigroup.

ANALYSIS

The selection of a certain type of quasigroup grid is required for this particular error-checking technique to work, for mathematical reasons known to Damm and left here as an exercise to the reader. For now, we will note the criteria-of-convenience that the major diagonal is set to 0s, for reasons which will become clear later. Strictly speaking this is not even required; if we select some other form for the matrix we would need to explicitly look up the correct value instead to check the result — given a range of valid quasi group matrices available we may as well use one with 0s on the major diagonal to facilitate this final lookup step.

The actual use of the algorithm, once we have this magic Sudoku square¹, is both remarkably straightforward, and quite quick, which I would suppose to be the focus of its utility. To validate a number with an already appended check digit, the number is processed digit-wise, including the check digit. The process here is replacing a temporary value with the the new element from the grid, with the row coordinate determined by the temporary variable, starting at 0, and the column by the input digit, continuing until the end of the number is reached.

At the end of the process, the value of the intrim will have returned to 0 if the check digit is correct. If the check digit is not correct, the numeric string can be assumed to have been corrupted.

This describes the decoding process before the encoding, but the encoding is done exactly the same — we step through the digits updating a temporary variable and after the selected number of steps we insert the temporary value as the check digit, resetting it to 0 before we begin again.

As we’ve said, one interesting beauty of this process is that when the check digit is computed it is affixed to the original value, and decoding is performed exactly as encoding. Because the check digit has been inserted after the group, and we know the values before the check digit produce the check digit, the row and column intersection for the final step will always be the same value, and fall along the major diagonal of the grid. This is why we select the grid such that this diagonal is composed of 0s: no further lookup is required in the last step.

---

¹ not really a Sudoku square

METHOD

For the quasigroup we will use Damm’s original form.

PERL 5 SOLUTION

The algorithm is the continuous reassignment of the interim variable as each digit in the input number is processed. The result is either the check digit or 0, depending on whether we’re encoding or decoding. After producing the validation routine requested I went ahead to make an encoder — as you can see the code is nearly identical, save for what is returned.

The requested validation routine is presented first, followed by a check digit assignment form.

Good practice tells us that these two routines should be refactored into one, but because the challenge asks specifically to verify I have left them separate to demonstrate how similar the two processes are, highlighting the small differences between the two stages.

perluse warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


my $num   = shift @ARGV;
say validate( $num ) if defined $num ;



sub validate ( $num ) {
    my $quasigroup =
        [   [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]  ];
    my $interim = 0;

    $interim = $quasigroup->[$interim][$_] for (split //, $num) ;

    return ($interim == 0 ? 1 : 0);    
}

sub addcheck ( $num ) {
    my $quasigroup =
        [   [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]  ];
    my $interim = 0;

    $interim = $quasigroup->[$interim][$_] for (split //, $num) ;

    return "$num$interim";        
}