Is the digit sequence valid, according to the Luhn algorithm?
Many numerical and data transmission tasks involve the use of a check sum, as a simple guard against inadvertent data corruption or transposition.1 Some of these techniques—e.g. casting out nines (summing a list of numbers, then summing the digit sums of those numbers while optionally ignoring 9s, and comparing the results of both sums, mod 9)—predate electronic computers by centuries. Some of these check sums are used to verify the digits of a number (or digit string) by computing a single check digit: A given formula is applied to all of the digits apart from the check digit, and if the result matches the check digit, then the full number is accepted. Alternatively, a formula may be applied to all of the digits, including the check digit, and if the resulting value doesn’t match the expected value (usually zero), then the full number is not accepted.
One of the most widely used check-digit algorithms is the Luhn algorithm, invented in the 1950s by Hans Peter Luhn, a scientist at IBM. This algorithm is used for computing the check digits on most types of credit cards, as well as SIM card serial numbers. Your task is to implement this algorithm to validate a String
of digit characters.
The Luhn algorithm can be stated in a few different ways. For our purposes, we’ll state it as follows:
Let sum = 0.
Let count = 0
Starting with the right-most digit of the digit string to be checked, and continuing to the left-most, do the following with each digit:
count = count + 1
If count is odd,
otherwise,
let temp = 2 * current digit
if temp > 9,
sum = sum + temp
If sum is evenly divisible by 10,
otherwise,
In the edu.cnm.deepdive.Luhn
class, the isValid
method is declared with the following signature, return type, and modifiers:
public static boolean isValid(String digits) throws IllegalArgumentException
The implementation must not change the modifiers, return type, method name, parameter types/number/order, or possible exceptions shown above. For more method declaration details, see the Javadoc documentation.
For the basic task, complete this method by implementing the algorithm described above, with these specific requirements:
Before computing and validating the sum, all whitespace must be removed, along with all other non-alphanumeric characters (such as “-“, the most commonly used credit card number group delimiter).
If any of remaining characters is not, in fact, a digit character, IllegalArgumentException
must be thrown. That is, after removing whitespace and non-alphanumeric characters, any letters left in the digit string should trigger the exception.
If the digit string is empty, then the sum is 0, which is divisible by 10; therefore, an empty string should be considered valid. (Obviously, such a credit card number is invalid for other reasons, but not because the check-digit calculation fails.)
If the digit string is valid, according to the Luhn algorithm, the method must return true
; otherwise, it must return false
.
The String.replaceAll
method can be used to remove characters from a String
, using a regular expression.2 Remember, however, that it does not modify a string in-place; instead, it returns a new string, with the modified contents. Also, remember that the \W
(non-word) regex character class matches almost all, but not all, non-alphanumeric characters: it considers the underscore to be an alphanumeric character.
Consider the fact that all char
values are numeric. For example, '0'
has a numeric value of 48, '1'
has a numeric value of 49, etc. Consider using this to update the sum without a switch
statement?
You may find it useful to create one or more additional static
methods as “helpers”; the problem can be solved without doing so, however.
Don’t hesitate to declare any constants (static final
fields) that you feel might simplify or clarify your code.
The method to be completed includes a TODO
comment to that effect.
For unit testing credit, these test cases will be used:
digits |
Expected return value of Luhn.isValid(digits) |
Exception |
---|---|---|
"4242424242424242" |
true |
(none) |
"4242-4242-4242-4242" |
true |
(none) |
"4242_4242_4242_4242" |
true |
(none) |
"4000056655665556" |
true |
(none) |
" 4000056655665556 " |
true |
(none) |
"3782 822463 10005" |
true |
(none) |
"" |
true |
(none) |
"4242-4242-4242-4224" |
false |
(none) |
"4000056655665565" |
false |
(none) |
"4000056655656556" |
false |
(none) |
"4000056565665556" |
false |
(none) |
"4242x4242x4242x4242" |
(none) | IllegalArgumentException |
"40000565656655S6" |
(none) | IllegalArgumentException |
"3782-822463-10005L" |
(none) | IllegalArgumentException |
We’re not concerning ourselves here with protection against malicious or otherwise deliberate forms of data corruption. ↩
A regular expression (usually abbreviated to regex or regexp) is a text pattern—expressed as a combination of literal values, quantitifers, character classes (shorthand symbols for groups of characters), and other elements—that can be used to search to filter text, validate input, extract key portions, etc. Regular-Expressions.info provides a very good overview of regular expression syntax; the API documentation for the java.util.regex.Pattern
class summarizes the regex syntax supported by the JCL. ↩