Damm and Cyclops

Weekly challenge 177 — 8 August 2022

;

Task 1

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 1Input: $n = 5724 Output: 1 as it is valid numberExample 2Input: $n = 5727 Output: 0 as it is invalid number

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).

#!/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]; }

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