Verhoeff algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
- 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
11l
<lang 11l>V MULTIPLICATION_TABLE = [[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]]
V INV = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9]
V PERMUTATION_TABLE = [[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]]
F verhoeffchecksum(n, validate = 1B, terse = 1B, verbose = 0B)
‘ Calculate the Verhoeff checksum over `n`. Terse mode or with single argument: return True if valid (last digit is a correct check digit). If checksum mode, return the expected correct checksum digit. If validation mode, return True if last digit checks correctly. ’ I verbose print(("\n"(I validate {‘Validation’} E ‘Check digit’))‘ ’(‘calculations for ’n":\n\n i ni p[i,ni] c\n------------------")) V (c, dig) = (0, Array(String(I validate {n} E 10 * n))) L(ni) reversed(dig) V i = L.index V p = :PERMUTATION_TABLE[i % 8][Int(ni)] c = :MULTIPLICATION_TABLE[c][p] I verbose print(f:‘{i:2} {ni} {p} {c}’)
I verbose & !validate print("\ninv("c‘) = ’:INV[c]) I !terse print(I validate {"\nThe validation for '"n‘' is ’(I c == 0 {‘correct’} E ‘incorrect’)‘.’} E "\nThe check digit for '"n‘' is ’:INV[c]‘.’) R I validate {c == 0} E :INV[c]
L(n, va, t, ve) [(Int64(236), 0B, 0B, 1B),
(Int64(2363), 1B, 0B, 1B), (Int64(2369), 1B, 0B, 1B), (Int64(12345), 0B, 0B, 1B), (Int64(123451), 1B, 0B, 1B), (Int64(123459), 1B, 0B, 1B), (Int64(123456789012), 0B, 0B, 0B), (Int64(1234567890120), 1B, 0B, 0B), (Int64(1234567890129), 1B, 0B, 0B)] verhoeffchecksum(n, va, t, ve)</lang>
- Output:
The same as in Python.
C
<lang c>#include <assert.h>
- include <stdbool.h>
- include <stdio.h>
- include <string.h>
static const int d[][10] = {
{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},
};
static const int inv[] = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};
static const int p[][10] = {
{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},
};
int verhoeff(const char* s, bool validate, bool verbose) {
if (verbose) { const char* t = validate ? "Validation" : "Check digit"; printf("%s calculations for '%s':\n\n", t, s); puts(u8" i n\xE1\xB5\xA2 p[i,n\xE1\xB5\xA2] c"); puts("------------------"); } int len = strlen(s); if (validate) --len; int c = 0; for (int i = len; i >= 0; --i) { int ni = (i == len && !validate) ? 0 : s[i] - '0'; assert(ni >= 0 && ni < 10); int pi = p[(len - i) % 8][ni]; c = d[c][pi]; if (verbose) printf("%2d %d %d %d\n", len - i, ni, pi, c); } if (verbose && !validate) printf("\ninv[%d] = %d\n", c, inv[c]); return validate ? c == 0 : inv[c];
}
int main() {
const char* ss[3] = {"236", "12345", "123456789012"}; for (int i = 0; i < 3; ++i) { const char* s = ss[i]; bool verbose = i < 2; int c = verhoeff(s, false, verbose); printf("\nThe check digit for '%s' is '%d'.\n", s, c); int len = strlen(s); char sc[len + 2]; strncpy(sc, s, len + 2); for (int j = 0; j < 2; ++j) { sc[len] = (j == 0) ? c + '0' : '9'; int v = verhoeff(sc, true, verbose); printf("\nThe validation for '%s' is %s.\n", sc, v ? "correct" : "incorrect"); } } return 0;
}</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.
F#
<lang fsharp> // Verhoeff algorithm. Nigel Galloway: August 26th., 2021 let d,inv,p=let 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|]
let 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|] let inv=[|0;4;3;2;1;5;6;7;8;9|] in (fun n g->d.[10*n+g]),(fun g->inv.[g]),(fun n g->p.[10*(n%8)+g])
let fN g=Seq.unfold(fun(i,g,l)->if i=0I then None else let ni=int(i%10I) in let l=d l (p g ni) in Some((ni,l),(i/10I,g+1,l)))(g,0,0) let csum g=let _,g=Seq.last(fN g) in inv g let printTable g=printfn $"Work Table for %A{g}\n i nᵢ p[i,nᵢ] c\n--------------"; fN g|>Seq.iteri(fun i (n,g)->printfn $"%d{i} %d{n} %d{p i n} %d{g}") printTable 2360I printfn $"\nThe CheckDigit for 236 is %d{csum 2360I}\n" printTable 2363I printfn $"\nThe assertion that 2363 is valid is %A{csum 2363I=0}\n" printTable 2369I printfn $"\nThe assertion that 2369 is valid is %A{csum 2369I=0}\n" printTable 123450I printfn $"\nThe CheckDigit for 12345 is %d{csum 123450I}\n" printTable 123451I printfn $"\nThe assertion that 123451 is valid is %A{csum 123451I=0}\n" printTable 123459I printfn $"\nThe assertion that 123459 is valid is %A{csum 123459I=0}" printfn $"The CheckDigit for 123456789012 is %d{csum 1234567890120I}" printfn $"The assertion that 1234567890120 is valid is %A{csum 1234567890120I=0}" printfn $"The assertion that 1234567890129 is valid is %A{csum 1234567890129I=0}" </lang>
- Output:
Work Table for 2360 i nᵢ p[i,nᵢ] c -------------- 0 0 0 0 1 6 3 3 2 3 3 1 3 2 1 2 The CheckDigit for 236 is 3 Work Table 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 assertion that 2363 is valid is true Work Table 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 assertion that 2369 is valid is false Work Table for 123450 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 The CheckDigit for 12345 is 1 Work Table 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 assertion that 123451 is valid is true Work Table 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 assertion that 123459 is valid is false The CheckDigit for 123456789012 is 0 The assertion that 1234567890120 is valid is true The assertion that 1234567890129 is valid is false
Go
<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
J
Implementation:
<lang J>cyc=: | +/~@i. NB. cyclic group, order y ac=: |(+-/~@i.) NB. anticyclic group, order y a2n=: (+#)@ NB. add 2^n di=: (cyc,.cyc a2n),((ac a2n),.ac)
D=: di 5 INV=: ,I.0=D P=: {&(C.1 5 8 9 4 2 7 0;3 6)^:(i.8) i.10
verhoeff=: {{
c=. 0 for_N. |.10 #.inv y do. c=. D{~<c,P{~<(8|N_index),N end.
}}
traceverhoeff=: {{
r=. EMPTY c=. 0 for_N. |.10 #.inv y do. c0=. c c=. D{~<c,p=.P{~<(j=.8|N_index),N r=. r, c,p,j,N_index,N,c0 end. labels=. cut 'cᵢ p[i,nᵢ] i nᵢ n cₒ' 1 1}.}:~.":labels,(<;._1"1~[:*/' '=])' ',.":r
}}
checkdigit=: INV {~ verhoeff@*&10 valid=: 0 = verhoeff</lang>
Task examples: <lang J> checkdigit 236 12345 123456789012 3 1 0
valid 2363
1
valid 123451
1
valid 1234567890120
1
valid 2369
0
valid 123459
0
valid 1234567890129
0
traceverhoeff 2363
cᵢ│p[i,nᵢ]│i│nᵢ│n│cₒ│ ──┼───────┼─┼──┼─┼──┤ 3 │3 │0│0 │3│0 │ 1 │3 │1│1 │6│3 │ 4 │3 │2│2 │3│1 │ 0 │1 │3│3 │2│4 │
traceverhoeff 123451
cᵢ│p[i,nᵢ]│i│nᵢ│n│cₒ│ ──┼───────┼─┼──┼─┼──┤ 1 │1 │0│0 │1│0 │ 9 │8 │1│1 │5│1 │ 2 │7 │2│2 │4│9 │ 8 │6 │3│3 │3│2 │ 3 │5 │4│4 │2│8 │ 0 │2 │5│5 │1│3 │ </lang>
jq
Works with gojq, the Go implementation of jq <lang jq>def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def 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]
];
def inv: [0, 4, 3, 2, 1, 5, 6, 7, 8, 9];
def 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]
];
- Output: an object: {emit, c}
def verhoeff($s; $validate; $table):
{emit: (if $table then ["\(if $validate then "Validation" else "Check digit" end) calculations for '\($s)':\n", " i nᵢ p[i,nᵢ] c", "------------------"] else [] end), s: (if $validate then $s else $s + "0" end), c: 0 } | ((.s|length) - 1) as $le | reduce range($le; -1; -1) as $i (.; (.s[$i:$i+1]|explode[] - 48) as $ni | (p[($le-$i) % 8][$ni]) as $pi | .c = d[.c][$pi] | if $table then .emit += ["\($le-$i|lpad(2)) \($ni) \($pi) \(.c)"] else .
end )
| if $table and ($validate|not) then .emit += ["\ninv[\(.c)] = \(inv[.c])"] else . end | .c = (if $validate then (.c == 0) else inv[.c] end);
def sts: [
["236", true], ["12345", true], ["123456789012", false]];
def task:
sts[] | . as $st | verhoeff($st[0]; false; $st[1]) as {c: $c, emit: $emit} | $emit[], "\nThe check digit for '\($st[0])' is '\($c)'\n", ( ($st[0] + ($c|tostring)), ($st[0] + "9") | . as $stc | verhoeff($stc; true; $st[1]) as {emit: $emit, c: $v} | (if $v then "correct" else "incorrect" end) as $v | $emit[], "\nThe validation for '\($stc)' is \($v).\n" );
task</lang>
- Output:
As for #Wren.
Julia
<lang julia>const multiplicationtable = [
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]
const permutationtable = [
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]
const inv = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9]
"""
verhoeffchecksum(n::Integer, validate=true, terse=true, verbose=false)
Calculate the Verhoeff checksum over `n`. Terse mode or with single argument: return true if valid (last digit is a correct check digit). If checksum mode, return the expected correct checksum digit. If validation mode, return true if last digit checks correctly. """ function verhoeffchecksum(n::Integer, validate=true, terse=true, verbose=false)
verbose && println("\n", validate ? "Validation" : "Check digit", " calculations for '$n':\n\n", " i nᵢ p[i,nᵢ] c\n------------------") # transform number list c, dig = 0, reverse(digits(validate ? n : 10 * n)) for i in length(dig):-1:1 ni = dig[i] p = permutationtable[(length(dig) - i) % 8 + 1, ni + 1] c = multiplicationtable[c + 1, p + 1] verbose && println(lpad(length(dig) - i, 2), " $ni $p $c") end verbose && !validate && println("\ninv($c) = $(inv[c + 1])") !terse && println(validate ? "\nThe validation for '$n' is $(c == 0 ? "correct" : "incorrect")." : "\nThe check digit for '$n' is $(inv[c + 1]).") return validate ? c == 0 : inv[c + 1]
end
for args in [(236, false, false, true), (2363, true, false, true), (2369, true, false, true),
(12345, false, false, true), (123451, true, false, true), (123459, true, false, true), (123456789012, false, false), (1234567890120, true, false), (1234567890129, true, false)] verhoeffchecksum(args...)
end
</lang>
- Output:
Same as Wren example.
Nim
<lang Nim>import strformat
const
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]]
Inv = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9]
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]]
type Digit = 0..9
proc verhoeff[T: SomeInteger](n: T; validate, verbose = false): T =
## Compute or validate a check digit. ## Return the check digit if computation or the number with the check digit ## removed if validation. ## If not in verbose mode, an exception is raised if validation failed.
doAssert n >= 0, "Argument must not be negative."
# Extract digits. var digits: seq[Digit] if not validate: digits.add 0 var val = n while val != 0: digits.add val mod 10 val = val div 10
if verbose: echo if validate: &"Check digit validation for {n}:" else: &"Check digit computation for {n}:" echo " i ni p(i, ni) c"
# Compute c. var c = 0 for i, ni in digits: let p = P[i mod 8][ni] c = D[c][p] if verbose: echo &"{i:2} {ni} {p} {c}"
if validate: if verbose: let verb = if c == 0: "is" else: "is not" echo &"Validation {verb} successful.\n" elif c != 0: raise newException(ValueError, &"Check digit validation failed for {n}.") result = n div 10
else: result = Inv[c] if verbose: echo &"The check digit for {n} is {result}.\n"
for n in [236, 12345]:
let d = verhoeff(n, false, true) discard verhoeff(10 * n + d, true, true) discard verhoeff(10 * n + 9, true, true)
let n = 123456789012 let d = verhoeff(n) echo &"Check digit for {n} is {d}." discard verhoeff(10 * n + d, true) echo &"Check digit validation was successful for {10 * n + d}." try:
discard verhoeff(10 * n + 9, true)
except ValueError:
echo getCurrentExceptionMsg()</lang>
- Output:
Check digit computation for 236: i ni p(i, ni) c 0 0 0 0 1 6 3 3 2 3 3 1 3 2 1 2 The check digit for 236 is 3. Check digit validation for 2363: i ni p(i, ni) c 0 3 3 3 1 6 3 1 2 3 3 4 3 2 1 0 Validation is successful. Check digit validation for 2369: i ni p(i, ni) c 0 9 9 9 1 6 3 6 2 3 3 8 3 2 1 7 Validation is not successful. Check digit computation for 12345: i ni p(i, ni) 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 The check digit for 12345 is 1. Check digit validation for 123451: i ni p(i, ni) 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 Validation is successful. Check digit validation for 123459: i ni p(i, ni) 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 Validation is not successful. Check digit for 123456789012 is 0. Check digit validation was successful for 1234567890120. Check digit validation failed for 1234567890129.
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Verhoeff_algorithm use warnings;
my @inv = qw(0 4 3 2 1 5 6 7 8 9);
my @d = map [ split ], split /\n/, <<END; 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 END
my @p = map [ split ], split /\n/, <<END; 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 END
my $debug;
sub generate
{ local $_ = shift() . 0; my $c = my $i = 0; my ($n, $p); $debug and print "i ni d(c,p(i%8,ni)) c\n"; while( length ) { $c = $d[ $c ][ $p = $p[ $i % 8 ][ $n = chop ] ]; $debug and printf "%d%3d%7d%10d\n", $i, $n, $p, $c; $i++; } return $inv[ $c ]; }
sub validate { shift =~ /(\d+)(\d)/ and $2 == generate($1) }
for ( 236, 12345, 123456789012 )
{ print "testing $_\n"; $debug = length() < 6; my $checkdigit = generate($_); print "check digit for $_ is $checkdigit\n"; $debug = 0; for my $cd ( $checkdigit, 9 ) { print "$_$cd is ", validate($_ . $cd) ? : 'not ', "valid\n"; } print "\n"; }</lang>
- Output:
testing 236 i ni d(c,p(i%8,ni)) c 0 0 0 0 1 6 3 3 2 3 3 1 3 2 1 2 check digit for 236 is 3 2363 is valid 2369 is not valid testing 12345 i ni d(c,p(i%8,ni)) 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 check digit for 12345 is 1 123451 is valid 123459 is not valid testing 123456789012 check digit for 123456789012 is 0 1234567890120 is valid 1234567890129 is not valid
Phix
The tables were generated in case 1-based index versions of them would help, tbh, but in the end I didn't even try that, aka start with tagset(10).
with javascript_semantics sequence d = {tagset(9,0)}, inv = tagset(9,0), p = {tagset(9,0)} for i=1 to 4 do d = append(d,extract(d[$],{2,3,4,5,1,7,8,9,10,6})) end for for i=5 to 8 do d = append(d,reverse(d[-4])) end for d = append(d,reverse(d[1])) inv[2..5] = reverse(inv[2..5]) for i=1 to 7 do p = append(p,extract(p[$],{2,6,8,7,3,9,4,1,10,5})) end for -- alternatively, if you prefer: --constant 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}}, -- inv = {0,4,3,2,1,5,6,7,8,9}, -- 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}} function verhoeff(string n, bool validate=false, show_workings=false) string {s,t} = iff(validate?{n,"Validation"}:{n&'0',"Check digit"}) if show_workings then printf(1,"%s calculations for `%s`:\n", {t, n}) printf(1," i ni p(i,ni) c\n") printf(1,"------------------\n") end if integer c = 0 for i=1 to length(s) do integer ni = s[-i]-'0', pi = p[remainder(i-1,8)+1][ni+1] c = d[c+1][pi+1] if show_workings then printf(1,"%2d %d %d %d\n", {i-1, ni, pi, c}) end if end for integer ch = inv[c+1]+'0' string r = iff(validate?iff(c=0?"":"in")&"correct" :"`"&ch&"`") printf(1,"The %s for `%s` is %s\n\n",{lower(t),n,r}) return ch end function constant tests = {"236", "12345", "123456789012"} for i=1 to length(tests) do bool show_workings = (i<=2) integer ch = verhoeff(tests[i],false,show_workings) assert(verhoeff(tests[i]&ch,true,show_workings)=='0') assert(verhoeff(tests[i]&'9',true,show_workings)!='0') end for
- Output:
Check digit calculations for `236`: i ni p(i,ni) c ------------------ 0 0 0 0 1 6 3 3 2 3 3 1 3 2 1 2 The check digit for `236` is `3` Validation calculations for `2363`: i ni p(i,ni) 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 ni p(i,ni) 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 ni p(i,ni) 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 The check digit for `12345` is `1` Validation calculations for `123451`: i ni p(i,ni) 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 ni p(i,ni) 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
Python
<lang python>MULTIPLICATION_TABLE = [
(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),
]
INV = (0, 4, 3, 2, 1, 5, 6, 7, 8, 9)
PERMUTATION_TABLE = [
(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),
]
def verhoeffchecksum(n, validate=True, terse=True, verbose=False):
""" Calculate the Verhoeff checksum over `n`. Terse mode or with single argument: return True if valid (last digit is a correct check digit). If checksum mode, return the expected correct checksum digit. If validation mode, return True if last digit checks correctly. """ if verbose: print(f"\n{'Validation' if validate else 'Check digit'}",\ f"calculations for {n}:\n\n i nᵢ p[i,nᵢ] c\n------------------") # transform number list c, dig = 0, list(str(n if validate else 10 * n)) for i, ni in enumerate(dig[::-1]): p = PERMUTATION_TABLE[i % 8][int(ni)] c = MULTIPLICATION_TABLE[c][p] if verbose: print(f"{i:2} {ni} {p} {c}")
if verbose and not validate: print(f"\ninv({c}) = {INV[c]}") if not terse: print(f"\nThe validation for '{n}' is {'correct' if c == 0 else 'incorrect'}."\ if validate else f"\nThe check digit for '{n}' is {INV[c]}.") return c == 0 if validate else INV[c]
if __name__ == '__main__':
for n, va, t, ve in [ (236, False, False, True), (2363, True, False, True), (2369, True, False, True), (12345, False, False, True), (123451, True, False, True), (123459, True, False, True), (123456789012, False, False, False), (1234567890120, True, False, False), (1234567890129, True, False, False)]: verhoeffchecksum(n, va, t, ve)
</lang>
- Output:
Output same as Wren example.
Raku
Generate the tables rather than hard coding, They're not all that complex.
<lang perl6>my @d = [^10] xx 5; @d[$_][^5].=rotate($_), @d[$_][5..*].=rotate($_) for 1..4; push @d: [@d[$_].reverse] for flat 1..4, 0;
my @i = 0,4,3,2,1,5,6,7,8,9;
my %h = flat (0,1,5,8,9,4,2,7,0).rotor(2 =>-1).map({.[0]=>.[1]}), 6=>3, 3=>6; my @p = [^10],; @p.push: [@p[*-1].map: {%h{$_}}] for ^7;
sub checksum (Int $int where * ≥ 0, :$verbose = True ) {
my @digits = $int.comb; say "\nCheckdigit calculation for $int:"; say " i ni p(i, ni) c" if $verbose; my ($i, $p, $c) = 0 xx 3; say " $i 0 $p $c" if $verbose; for @digits.reverse { ++$i; $p = @p[$i % 8][$_]; $c = @d[$c; $p]; say "{$i.fmt('%2d')} $_ $p $c" if $verbose; } say "Checkdigit: {@i[$c]}"; +($int ~ @i[$c]);
}
sub validate (Int $int where * ≥ 0, :$verbose = True) {
my @digits = $int.comb; say "\nValidation calculation for $int:"; say " i ni p(i, ni) c" if $verbose; my ($i, $p, $c) = 0 xx 3; for @digits.reverse { $p = @p[$i % 8][$_]; $c = @d[$c; $p]; say "{$i.fmt('%2d')} $_ $p $c" if $verbose; ++$i; } say "Checkdigit: {'in' if $c}correct";
}
- TESTING
for 236, 12345, 123456789012 -> $int {
my $check = checksum $int, :verbose( $int.chars < 8 ); validate $check, :verbose( $int.chars < 8 ); validate +($check.chop ~ 9), :verbose( $int.chars < 8 );
}</lang>
- Output:
Checkdigit calculation for 236: i ni p(i, ni) c 0 0 0 0 1 6 3 3 2 3 3 1 3 2 1 2 Checkdigit: 3 Validation calculation for 2363: i ni p(i, ni) c 0 3 3 3 1 6 3 1 2 3 3 4 3 2 1 0 Checkdigit: correct Validation calculation for 2369: i ni p(i, ni) c 0 9 9 9 1 6 3 6 2 3 3 8 3 2 1 7 Checkdigit: incorrect Checkdigit calculation for 12345: i ni p(i, ni) 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 Checkdigit: 1 Validation calculation for 123451: i ni p(i, ni) 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 Checkdigit: correct Validation calculation for 123459: i ni p(i, ni) 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 Checkdigit: incorrect Checkdigit calculation for 123456789012: Checkdigit: 0 Validation calculation for 1234567890120: Checkdigit: correct Validation calculation for 1234567890129: Checkdigit: incorrect
Wren
<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.