Peter
Peter Campbell Smith

Damm and Cyclops

Weekly challenge 177 — 8 August 2022

Week 177: 8 Aug 2022

Task 1

Task — Damm algorithm

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.

Examples


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

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

Analysis

The Damm algorithm takes a sequence of n digits and results in a check digit, m. If the check digit is appended to the original sequence, applying the Damm algorithm to the new sequence of n+1 digits results in a check digit of 0.

The algorithm uses a weakly totally anti-symmetric quasigroup of order 10. I'm sure we're all familiar with those, but in case we don't have one to hand, Wikipedia has kindly purloined one from Dr Damm's PhD thesis, and luckily Mohammad has used that one for his example.

Armed with the quasigroup and holding it in Perl's simulation of a two-dimensional array, the algorithm is very simple: start with an 'interim digit' of 0 and then replace the interim digit with the value in the 2D array at [$interim_digit, $digit] where $digit is successive digits of the supplied number.

We are given a number to test which already has the check digit appended, so if the final value of $interim_digit is zero, the check digit is correct - ie the original digit sequence is valid.

We can check our working by taking a long string of digits, adding its check digit, and then verifying that swapping two digits or altering a single digit results in a non-zero result from the algorithm.

Even in my rather verbose programming style that's only 5 lines of code (apart from initialising the table).

Try it 

Try running the script with any input:



example: 5724

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-08-08
# PWC 177 task 1

use v5.28;
use utf8;
use warnings;

my (@table, @tests, $test, $interim_digit);

@table = (
[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]);
             
@tests = (5724, 5725, 85670934565, 85760934565, 85680934565);

for $test (@tests) {
    
    # start with zero
    $interim_digit = 0;
    
    # loop over digits
    while ($test =~ m|(\d)|g) {
        $interim_digit = $table[$interim_digit][$1];
    }
    
    # number is valid if $interim_digit is zero
    say qq[\nInput:  $test];
    say qq[Output: is ] . ($interim_digit ? 'not ' : '') . qq[valid];
}
        

Output


Input:  5724
Output: is valid

Input:  5725
Output: is not valid

Input:  85670934565
Output: is valid

Input:  85760934565
Output: is not valid

Input:  85680934565
Output: is not valid

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain