Skip to content

Commit bfa30ca

Browse files
BoiarshinovBoiarshinov
authored
Add Verhoeff Algorithm (Fixes: TheAlgorithms#2754) (TheAlgorithms#2755)
1 parent 794719c commit bfa30ca

File tree

1 file changed

+158
-0
lines changed

1 file changed

+158
-0
lines changed

‎Others/Verhoeff.java

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
package Others;
2+
3+
import java.util.Objects;
4+
5+
/**
6+
* The Verhoeff algorithm is a checksum formula for error detection developed
7+
* by the Dutch mathematician Jacobus Verhoeff and was first published in 1969.
8+
* It was the first decimal check digit algorithm which detects all single-digit
9+
* errors, and all transposition errors involving two adjacent digits.
10+
*
11+
* <p>The strengths of the algorithm are that it detects all transliteration and
12+
* transposition errors, and additionally most twin, twin jump, jump transposition
13+
* and phonetic errors.
14+
* The main weakness of the Verhoeff algorithm is its complexity.
15+
* The calculations required cannot easily be expressed as a formula.
16+
* For easy calculation three tables are required:</p>
17+
* <ol>
18+
* <li>multiplication table</li>
19+
* <li>inverse table</li>
20+
* <li>permutation table</li>
21+
* </ol>
22+
*
23+
* @see <a href="https://en.wikipedia.org/wiki/Verhoeff_algorithm">Wiki. Verhoeff algorithm</a>
24+
*/
25+
public class Verhoeff {
26+
27+
/**
28+
* Table {@code d}.
29+
* Based on multiplication in the dihedral group D5 and is simply the Cayley table of the group.
30+
* Note that this group is not commutative, that is, for some values of {@code j} and {@code k},
31+
* {@code d(j,k) ≠ d(k, j)}.
32+
*
33+
* @see <a href="https://en.wikipedia.org/wiki/Dihedral_group">Wiki. Dihedral group</a>
34+
*/
35+
private static final byte[][] MULTIPLICATION_TABLE = {
36+
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
37+
{1, 2, 3, 4, 0, 6, 7, 8, 9, 5},
38+
{2, 3, 4, 0, 1, 7, 8, 9, 5, 6},
39+
{3, 4, 0, 1, 2, 8, 9, 5, 6, 7},
40+
{4, 0, 1, 2, 3, 9, 5, 6, 7, 8},
41+
{5, 9, 8, 7, 6, 0, 4, 3, 2, 1},
42+
{6, 5, 9, 8, 7, 1, 0, 4, 3, 2},
43+
{7, 6, 5, 9, 8, 2, 1, 0, 4, 3},
44+
{8, 7, 6, 5, 9, 3, 2, 1, 0, 4},
45+
{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
46+
};
47+
48+
/**
49+
* The inverse table {@code inv}.
50+
* Represents the multiplicative inverse of a digit, that is, the value that satisfies
51+
* {@code d(j, inv(j)) = 0}.
52+
*/
53+
private static final byte[] MULTIPLICATIVE_INVERSE = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};
54+
55+
/**
56+
* The permutation table {@code p}.
57+
* Applies a permutation to each digit based on its position in the number.
58+
* This is actually a single permutation {@code (1 5 8 9 4 2 7 0)(3 6)} applied iteratively;
59+
* i.e. {@code p(i+j,n) = p(i, p(j,n))}.
60+
*/
61+
private static final byte[][] PERMUTATION_TABLE = {
62+
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
63+
{1, 5, 7, 6, 2, 8, 3, 0, 9, 4},
64+
{5, 8, 0, 3, 7, 9, 6, 1, 4, 2},
65+
{8, 9, 1, 6, 0, 4, 3, 5, 2, 7},
66+
{9, 4, 5, 3, 1, 2, 6, 8, 7, 0},
67+
{4, 2, 8, 6, 5, 7, 3, 9, 0, 1},
68+
{2, 7, 9, 3, 8, 0, 6, 4, 1, 5},
69+
{7, 0, 4, 6, 9, 1, 3, 2, 5, 8}
70+
};
71+
72+
/**
73+
* Check input digits by Verhoeff algorithm.
74+
*
75+
* @param digits input to check
76+
* @return true if check was successful, false otherwise
77+
* @throws IllegalArgumentException if input parameter contains not only digits
78+
* @throws NullPointerException if input is null
79+
*/
80+
public static boolean verhoeffCheck(String digits) {
81+
checkInput(digits);
82+
int[] numbers = toIntArray(digits);
83+
84+
// The Verhoeff algorithm
85+
int checksum = 0;
86+
for (int i = 0; i < numbers.length; i++) {
87+
int index = numbers.length - i - 1;
88+
byte b = PERMUTATION_TABLE[i % 8][numbers[index]];
89+
checksum = MULTIPLICATION_TABLE[checksum][b];
90+
}
91+
92+
return checksum == 0;
93+
}
94+
95+
/**
96+
* Calculate check digit for initial digits and add it tho the last position.
97+
*
98+
* @param initialDigits initial value
99+
* @return digits with the checksum in the last position
100+
* @throws IllegalArgumentException if input parameter contains not only digits
101+
* @throws NullPointerException if input is null
102+
*/
103+
public static String addVerhoeffChecksum(String initialDigits) {
104+
checkInput(initialDigits);
105+
106+
// Add zero to end of input value
107+
var modifiedDigits = initialDigits + "0";
108+
109+
int[] numbers = toIntArray(modifiedDigits);
110+
111+
int checksum = 0;
112+
for (int i = 0; i < numbers.length; i++) {
113+
int index = numbers.length - i - 1;
114+
byte b = PERMUTATION_TABLE[i % 8][numbers[index]];
115+
checksum = MULTIPLICATION_TABLE[checksum][b];
116+
}
117+
checksum = MULTIPLICATIVE_INVERSE[checksum];
118+
119+
return initialDigits + checksum;
120+
}
121+
122+
public static void main(String[] args) {
123+
System.out.println("Verhoeff algorithm usage examples:");
124+
var validInput = "2363";
125+
var invalidInput = "2364";
126+
checkAndPrint(validInput);
127+
checkAndPrint(invalidInput);
128+
129+
System.out.println("\nCheck digit generation example:");
130+
var input = "236";
131+
generateAndPrint(input);
132+
}
133+
134+
private static void checkAndPrint(String input) {
135+
String validationResult = Verhoeff.verhoeffCheck(input)
136+
? "valid"
137+
: "not valid";
138+
System.out.println("Input '" + input + "' is " + validationResult);
139+
}
140+
141+
private static void generateAndPrint(String input) {
142+
String result = addVerhoeffChecksum(input);
143+
System.out.println("Generate and add checksum to initial value '" + input + "'. Result: '" + result + "'");
144+
}
145+
146+
private static void checkInput(String input) {
147+
Objects.requireNonNull(input);
148+
if (!input.matches("\\d+")) {
149+
throw new IllegalArgumentException("Input '" + input + "' contains not only digits");
150+
}
151+
}
152+
153+
private static int[] toIntArray(String string) {
154+
return string.chars()
155+
.map(i -> Character.digit(i, 10))
156+
.toArray();
157+
}
158+
}

0 commit comments

Comments
 (0)