This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
OK, the title might need some explaining: Both tasks this week have us looking through lists of numbers and doubling some of them.
Task 1 › Double Exist
Task 1’s premise is simple enough: we take in a list of @ints and return a true value if the list contains a number and its double.
We also have the restriction that the same list element cannot be its own double. Zero is the only integer this can happen with. For example, (0) returns false even though 2×0 = 0, but (0,0) returns true because the second zero is a different list element.
We can solve this in O(n) time with a little bit of housekeeping: we will track whether we have seen the double of a number, and the half of a number (if that number is even). Tracking both doubles and halves ensures that we will find the 2k whether it comes before or after k in the list.
As we go through the list of @ints, we can return early as soon as we come across a number that we have either seen the double or the half of. Otherwise, we update %half_seen and %dubl_seen.
sub double_exist(@ints) {
my %dubl_seen; # $dubl_seen{$x} is true iff we've already seen 2*$x
my %half_seen; # $half_seen{$x} is true iff we've already seen $x/2
for (@ints) {
return 1 if $dubl_seen{$_} or $half_seen{$_};
$half_seen{2 * $_} = 1;
$dubl_seen{$_ / 2} = 1 if $_ % 2 == 0;
}
return # Double not found
}
Task 2 › Luhn’s Algorithm
Luhn’s Algorithm is a commonly used check digit algorithm that is employed to check various types of numbers (such as credit and debit card numbers) for (potential) validity or against accidental entry errors. It is not meant to provide any cryptographic security!
In my implementation, I compute the sum of:
- The check digit (last digit)
- The 2nd, 4th, 6th, etc. digits, starting from the end
- For the 1st, 3rd, 5th, etc. digits from the end:
- If that digit is >= 5, I compute the sum of its digits (simplified as
1 + ($_ * 2) % 10) - Else, I compute
($_ * 2)
- If that digit is >= 5, I compute the sum of its digits (simplified as
If the resulting $sum % 10 is equal to zero, the number is valid.
Verification that this is equivalent to the stated task description is left as an exercise to the reader.
use List::Util qw< sum0 >;
sub luhn($str) {
my $idx = 0;
my $sum = sum0 map {
$idx++;
$idx == 1 ? $_ # Check digit
: $idx % 2 ? $_ # Even digit
: $_ >= 5 ? (2 * $_) % 10 + 1 # Odd digit >= 5
: (2 * $_) # Odd digit < 5
} grep /\d/, reverse split '', $str;
$sum % 10 == 0
}
In a sum0() call, I iterate over every digit (\d) in the reversed input $string, and maintain an $idx as I go. This achieves the sum I outlined above. The last line returns true or false depending on whether $sum is a multiple of 10, and, hence, the number is valid.