Verhoeff algorithm

Verhoeff algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Description

The Verhoeff algorithm is a checksum formula for error detection developed by the Dutch mathematician Jacobus Verhoeff and first published in 1969. It was the first decimal check digit algorithm which detects all single-digit errors, and all transposition errors involving two adjacent digits, which was at the time thought impossible with such a code.

As the workings of the algorithm are clearly described in the linked Wikipedia article they will not be repeated here.

Task

Write routines, methods, procedures etc. in your language to generate a Verhoeff checksum digit for non-negative integers of any length and to validate the result. A combined routine is also acceptable.

The more mathematically minded may prefer to generate the 3 tables required from the description provided rather than to hard-code them.

Write your routines in such a way that they can optionally display digit by digit calculations as in the Wikipedia example.

Use your routines to calculate check digits for the integers: 236, 12345 and 123456789012 and then validate them. Also attempt to validate the same integers if the check digits in all cases were 9 rather than what they actually are.

Display digit by digit calculations for the first two integers but not for the third.

Related task

•   Damm algorithm

Wren

Library: Wren-fmt

<lang ecmascript>import "/fmt" for Fmt

var d = [

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

]

var inv = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9]

var p = [

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

]

var verhoeff = Fn.new { |s, validate, table|

   if (table) {
       System.print("%(validate ? "Validation" : "Check digit") calculations for '%(s)':\n")
       System.print(" i  nᵢ  p[i,nᵢ]  c")
       System.print("------------------")
   }
   if (!validate) s = s + "0"
   var c = 0
   var le = s.count - 1
   for (i in le..0) {
       var ni = s[i].bytes[0] - 48
       var pi = p[(le-i) % 8][ni]
       c = d[c][pi]
       if (table) Fmt.print("$2d  $d      $d     $d", le-i, ni, pi, c)           
   }
   if (table && !validate) System.print("\ninv[%(c)] = %(inv[c])")
   return !validate ? inv[c] : c == 0

}

var sts = [["236", true], ["12345", true], ["123456789012", false]] for (st in sts) {

   var c = verhoeff.call(st[0], false, st[1])
   System.print("\nThe check digit for '%(st[0])' is '%(c)'\n")
   for (stc in [st[0] + c.toString, st[0] + "9"]) {
       var v = verhoeff.call(stc, true, st[1])
       System.print("\nThe validation for '%(stc)' is %(v ? "correct" : "incorrect").\n")
   }

}</lang>

Output:

Check digit calculations for '236':

 i  nᵢ  p[i,nᵢ]  c
------------------
 0  0      0     0
 1  6      3     3
 2  3      3     1
 3  2      1     2

inv[2] = 3

The check digit for '236' is '3'

Validation calculations for '2363':

 i  nᵢ  p[i,nᵢ]  c
------------------
 0  3      3     3
 1  6      3     1
 2  3      3     4
 3  2      1     0

The validation for '2363' is correct.

Validation calculations for '2369':

 i  nᵢ  p[i,nᵢ]  c
------------------
 0  9      9     9
 1  6      3     6
 2  3      3     8
 3  2      1     7

The validation for '2369' is incorrect.

Check digit calculations for '12345':

 i  nᵢ  p[i,nᵢ]  c
------------------
 0  0      0     0
 1  5      8     8
 2  4      7     1
 3  3      6     7
 4  2      5     2
 5  1      2     4

inv[4] = 1

The check digit for '12345' is '1'

Validation calculations for '123451':

 i  nᵢ  p[i,nᵢ]  c
------------------
 0  1      1     1
 1  5      8     9
 2  4      7     2
 3  3      6     8
 4  2      5     3
 5  1      2     0

The validation for '123451' is correct.

Validation calculations for '123459':

 i  nᵢ  p[i,nᵢ]  c
------------------
 0  9      9     9
 1  5      8     1
 2  4      7     8
 3  3      6     2
 4  2      5     7
 5  1      2     5

The validation for '123459' is incorrect.


The check digit for '123456789012' is '0'


The validation for '1234567890120' is correct.


The validation for '1234567890129' is incorrect.