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

Go

Translation of: Wren

<lang go>package main

import "fmt"

var d = [][]int{

   {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 = []int{0, 4, 3, 2, 1, 5, 6, 7, 8, 9}

var p = [][]int{

   {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},

}

func verhoeff(s string, validate, table bool) interface{} {

   if table {
       t := "Check digit"
       if validate {
           t = "Validation"
       }
       fmt.Printf("%s calculations for '%s':\n\n", t, s)
       fmt.Println(" i  nᵢ  p[i,nᵢ]  c")
       fmt.Println("------------------")
   }
   if !validate {
       s = s + "0"
   }
   c := 0
   le := len(s) - 1
   for i := le; i >= 0; i-- {
       ni := int(s[i] - 48)
       pi := p[(le-i)%8][ni]
       c = d[c][pi]
       if table {
           fmt.Printf("%2d  %d      %d     %d\n", le-i, ni, pi, c)
       }
   }
   if table && !validate {
       fmt.Printf("\ninv[%d] = %d\n", c, inv[c])
   }
   if !validate {
       return inv[c]
   }
   return c == 0

}

func main() {

   ss := []string{"236", "12345", "123456789012"}
   ts := []bool{true, true, false, true}
   for i, s := range ss {
       c := verhoeff(s, false, ts[i]).(int)
       fmt.Printf("\nThe check digit for '%s' is '%d'\n\n", s, c)
       for _, sc := range []string{s + string(c+48), s + "9"} {
           v := verhoeff(sc, true, ts[i]).(bool)
           ans := "correct"
           if !v {
               ans = "incorrect"
           }
           fmt.Printf("\nThe validation for '%s' is %s\n\n", sc, ans)
       }
   }

}</lang>

Output:

Identical to Wren example

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.