The Luhn algorithm is a standard algorithm used by almost every system that allows you to manually enter a credit card number, along with certain other types of identification numbers. The last digit of such numbers is reserved for the Luhn check digit, which is calculated from the other digits.

It’s a pretty simple algorithm overall, the verification goes something like this: Double every second digit from the right of the number. If any digits are greater than 9, subtract 9. Sum all the digits. Check that the result is divisible by 10.

There are a few edge cases related to input format that I need to account for in the Exercism task, but the core of the Luhn algorithm really is that simple.

Languages

TypeScript

Back in week 2, I used JavaScript to reverse a string. TypeScript is JavaScript… plus types. Created by Microsoft, it aims to reduce the chance of type-related bugs in JavaScript by extending it with a powerful static typing system.

Despite the addition of static types, a lot of TypeScript code looks identical to JavaScript code, thanks to the ability to infer and narrow types automatically. Because of that, my TypeScript code only has types on two lines – the two function definitions.

First, I define a function to handle both doubling, and possibly subtracting nine from a digit:

function double(digit: number): number {
  return digit < 5 ? digit * 2 : digit * 2 - 9;
}

Here we see the first line with types – double takes a number and returns a number (there is only one number type). The code here just checks if the digit is high enough to go past 9 when doubled, then either returns digit * 2, or digit * 2 - 9.

The actual valid function has three parts. First, I do some initial processing on the digits:

export function valid(digitString: string): boolean {
  const digits = [...digitString]
    .filter(d => d.match(/\S/))
    .map(d => parseInt(d, 10));
  digits.reverse();

This has the second, equally simple use of types – take a card number as a string, return a boolean indicating validity. [...digitString] is the same way I split strings into characters back in week 2, and it works fine here (no grapheme-related pain). I remove whitespace, attempt to convert each character to an integer, and reverse all the digits. Note that I said attempt to convert the characters. What happens if something other than a digit makes it in? The next bit of code handles that case:

  if (digits.includes(NaN)) return false;
  if (digits.length < 2) return false;

Invalid digits will result in NaN (not a number), and in this step I filter those out, along with empty strings and those containing only a single digit – these formats just aren’t valid. At this point, digits should just be an array of numbers (number[] in TypeScript terms). The final step is to perform the actual Luhn check:

  const sum = digits
    .map((digit, i) => i % 2 == 0 ? digit : double(digit))
    .reduce((a, b) => a + b);
  return sum % 10 == 0;
}

I do it all in a few lines, with the help of the double function from earlier. In JS and TS, map passes not just each element, but the index of that element. Since the array is reversed, the numbers we want to double should have indices 1, 3, 5, … – all odd numbers. Using the index, I choose whether or not to double each number. reduce sums all the updated digits and the final line can just check if the sum is divisible by 10.

So that’s Luhn in TypeScript (which looks like plain JavaScript since types aren’t used much here). I’m not entirely happy with the structure of it, particularly the use of NaN to check the input format. This is something that I’ve done quite differently in the following solutions.

Perl

Perl is a scripting language, originally targeting Unix scripting. It has strong support for text processing, but sees limited use outside of that area. My Perl solution to Luhn takes advantage of a few of the features that make Perl work well for text processing.

sub is_luhn_valid ($number) {
    $number =~ s/ //g;
    return 0 if length($number) < 2;
    return 0 if $number =~ /[^0-9]/;

The start of the function has some similar ideas to the TypeScript version, but written in a slightly different style. Perl handles regular expressions natively, and in fact Perl invented several features now common in regular expressions (e.g. non-greedy matches, backreferences). The first line replaces all spaces in number with nothing, which just removes spaces. The second line uses a postfix if to fail early if the string is too short, and the third line does the same to fail if the string contains any non-digit characters.

Notice that I didn’t convert explicitly convert the string to numbers. You’ll see why in the main summation code:

    my $sum = 0;
    for (my $i = 0; $i < length($number); $i++) {
        my $digit = substr($number, length($number) - $i - 1, 1);
        $digit *= 2 if $i % 2 == 1;
        $digit -= 9 if $digit > 9;
        $sum += $digit;
    }
    return $sum % 10 == 0;
}

This code loops backwards over the string, taking substrings to get each digit. Then, without any explicit conversion, it treats those digits as numeric data. This implicit type conversion is why it was left as a string, and is one of the features I mentioned that makes processing text-based data easier.

The doubling code once again uses postfix if for compact code, doubling where necessary, then subtracting 9 if the number is too big. The rest of the code should look familiar. Keep this code structure in mind, as my last solution works in the exact same way.

AWK

AWK is one of the languages that Perl aimed to replace, though it’s still widely used. AWK never really attempted to move beyond being a text processing tool, so it too has syntax that is heavily centered around this use case.

My AWK solution is this:

gsub(" ", "")
if (length() < 2 || $0 ~ /[^0-9]/) {
    print "false"
    exit
}
sum = 0
for (i = 0; i < length(); i++) {
    digit = substr($0, length() - i, 1)
    if (i % 2 == 1) { digit *= 2 }
    if (digit > 9) { digit -= 9 }
    sum += digit
}
print sum % 10 == 0 ? "true" : "false"

Just like in Perl, I start off with a substitution, then the length check and digit check. Because the code required to exit early is a bit longer in AWK, I chose to combine these two checks here. Exercism’s AWK exercises don’t use functions (I don’t even know whether this is possible), so I have to take input from $0, then print either “true” or “false” and explicitly exit if returning early.

The code is largely the same as in Perl, though I’d like to draw attention to the substr line: this is one of the few times I’ve seen 1-indexing make code simpler – normally it either stays the same or gets a little more complicated. This is only true because I still started the loop at zero though. If I hadn’t, the code would look no different to the Perl version.

Summary

This task was quite well suited to languages designed for processing text, even given its slightly more numerical nature, and this can be seen in the short solutions for both Perl and AWK. I probably could have written a TypeScript version that functions similarly, but this was a good chance to use some more simple functional programming.

You can find my complete solutions published on Exercism: TypeScript, Perl, and AWK. Thanks for reading!

#48in24 – Week 12: Luhn

Languages

TypeScript

Perl

AWK

Summary