Verhoeff algorithm
- 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
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
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.
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.