laurent_r

These are some answers to the Week 290, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on October 13, 2024, at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Luhn’s Algorithm

You are given a string $str containing digits (and possibly other characters which can be ignored). The last digit is the payload; consider it separately. Counting from the right, double the value of the first, third, etc. of the remaining digits.

For each value now greater than 9, sum its digits.

The correct check digit is that which, added to the sum of all values, would bring the total mod 10 to zero.

Return true if and only if the payload is equal to the correct check digit.

It was originally posted on reddit.

Example 1

Input: "17893729974"
Output: true

Payload is 4.

Digits from the right:

7 * 2 = 14, sum = 5
9 = 9
9 * 2 = 18, sum = 9
2 = 2
7 * 2 = 14, sum = 5
3 = 3
9 * 2 = 18, sum = 9
8 = 8
7 * 2 = 14, sum = 5
1 = 1

Sum of all values = 56, so 4 must be added to bring the total mod 10 to zero. The payload is indeed 4.

Example 2

Input: "4137 8947 1175 5904"
Output: true

Example 3

Input: "4137 8974 1175 5904"
Output: false

The Luhn algorithm is a simple check digit formula (or checksum) used to validate a variety of identification numbers.

The algorithm was invented in 1960 and is in wide use today. It is aimed at protecting against accidental typing errors. Most credit cards and many government identification numbers use the algorithm as a simple method of distinguishing valid numbers from mistyped or otherwise incorrect numbers.

This task has real life applications. In my professional career as a contractor for a tier-one cell phone operator for 26 years, I implemented the Luhn algorithm at least three times (in three different programming languages, including Perl, but I no longer have the code developed then, so I had to re-implement it from scratch for this task). In the mobile phone industry, the Luhn formula is used for validating at least two identification numbers: the International Mobile Equipment Identity (IMEI), an identifier for the phone itself, and the Integrated Circuit Card Identifier (ICCID) for the SIM card (or eSIM profile).

The algorithm described above can be simplified. Rather than performing the calculations on the identification number without the trailing check digit, we can do it directly on the whole number (with the check digit). This modified algorithm goes as follows:

• Reverse the order of the digits in the number.

• Take the second, fourth ... and every other even digit in the reversed digits, multiply them by two and sum the digits if the answer is greater than nine.

• Add all the digits; if the sum is a multiple of 10 (ends in zero), then the original number is a valid identification number.

Luhn’s Algorithm in Raku

This program implements the modified algorithm described just above. First, the program uses a regex to remove characters that are not digits from the input string. Then it reverses the resulting string, using the flip method, and splitted into an array of individual characters (@digits), using the comb method. Then, it multiplies by 2 the values of @digits with and even index, and sums the digits of the resulting number (using a comb and sum combination. Finally, the original number is validl if the sum of all digits can be evenly divided by 10.

sub luhn ($in is copy) {
    $in ~~ s:g/\D+//;  # remove non-digits
    my @digits = $in.flip.comb;  # reverse and split
    for 0..@digits.end -> $i {
        # values for even indices don't change
        @digits[$i] = (2 * @digits[$i]).comb.sum unless $i %% 2;
    }
    return @digits.sum %% 10; # valid if sum end with a 0
}

for "17893729974", "178az93r729974", "178 9372 9 9  74",
    "4137 8947 1175 5904", "4137 8974 1175 5904" -> $test {
    printf "%-25s => ", $test;
    say luhn $test;
}

This program displays the following output:

$ raku ./luhn.raku
17893729974               => True
178az93r729974            => True
178 9372 9 9  74          => True
4137 8947 1175 5904       => True
4137 8974 1175 5904       => False

Luhn’s Algorithm in Perl

This is a port to Perl of the above Raku program. Please refer to the previous sections if you need explanations. The comb built-in is replaced by split and we implemented our own sum and sum_digits auxiliary subroutines.

use strict;
use warnings;
use feature 'say';

sub sum {
    my $sum = 0;
    for my $n (@_) {
        $sum += $n;
    }
    return $sum;
}
sub sum_digits {
    return sum split //, shift;
}

sub luhn {
    my $in = shift;
    $in =~ s/\D+//g;             # remove non-digits
    my @digits = reverse split //, $in; # reverse and split
    for my $i (0..$#digits) {
        next unless $i % 2;   #skip even indices
        my $val = 2 * $digits[$i];
        $digits[$i] = sum_digits $val;
    }
    # valid luhn if sum ends with a 0 (multiple of 10)
    return (sum @digits) % 10 == 0 ? "True" : "False"; 
}

for my $test ("17893729974", "178a93r729974", "178 9372 9 9 74",
    "4137 8947 1175 5904", "4137 8974 1175 5904") {
    printf "%-25s => ", $test;
    say luhn $test;
}

This program displays the following output:

$ perl  ./luhn.pl
17893729974               => True
178a93r729974             => True
178 9372 9 9 74           => True
4137 8947 1175 5904       => True
4137 8974 1175 5904       => False

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on October 20, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.