In this article, we will address two engaging tasks from the Perl Weekly Challenge #290: checking for double existence in an array and implementing Luhn's Algorithm for validation. We'll implement solutions in both Perl and Go.
Table of Contents
Double Existence
The first task involves finding if there exist two indices $i and $j such that:
1. $i != $j
2. 0 <= ($i, $j) < scalar @ints
3. $ints[i] = 2 * $ints[j]
Task Description
Input: An array of integers, @ints.
Output: true if the condition is met; otherwise, false.
Examples:
Input: @ints = (6, 2, 3, 3)
Output: true
For $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 => 2 * $ints[$j]
Input: @ints = (3, 1, 4, 13)
Output: false
Input: @ints = (2, 1, 4, 2)
Output: true
For $i = 2, $j = 3
$ints[$i] = 4 => 2 * 2 => 2 * $ints[$j]
Solution
Perl Implementation
In the Perl implementation, we use a hash to track seen integers and check if either half or double of the current number exists in the hash.
sub double_exist {
my %seen;
foreach my $num (@_) {
return 1 if exists $seen{$num / 2} || exists $seen{$num * 2};
$seen{$num} = 1;
}
return 0;
}
Go Implementation
The Go implementation follows a similar logic, using a map to keep track of unique integers.
func doubleExist(ints []int) bool {
seen := make(map[int]bool)
for _, num := range ints {
if (num%2 == 0 && seen[num/2]) || seen[num*2] {
return true
}
seen[num] = true
}
return false
}
Luhn's Algorithm
The second task involves implementing Luhn's Algorithm to validate a string of digits, ignoring non-digit characters. The last digit is considered separately as the payload.
Task Description
You are given a string str containing digits (and possibly other characters which can be ignored). The last digit is considered as the payload and handled 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 the one that, when added to the sum of all values, brings the total modulo 10 to zero.
Return true if the payload equals the correct check digit; otherwise, return false.
Examples:
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.
Input: "4137 8947 1175 5904"
Output: true
Input: "4137 8974 1175 5904"
Output: false
Solution
Perl Implementation
The Perl implementation processes the input string to ignore non-digit characters, then applies Luhn's algorithm to validate the number.
sub luhn_check {
my ($str) = @_;
$str =~ s/[^0-9]//g;
my $payload = substr($str, -1);
my $sum = 0;
my $length = length($str);
for (my $i = 0; $i < $length - 1; $i++) {
my $digit = substr($str, $length - 2 - $i, 1);
if ($i % 2 == 0) {
$digit *= 2;
$digit -= 9 if $digit > 9;
}
$sum += $digit;
}
my $check_digit = (10 - ($sum % 10)) % 10;
return $payload == $check_digit ? 1 : 0;
}
Go Implementation
The Go version implements the same logic, utilizing the unicode package to filter out non-digit characters.
func luhnCheck(str string) bool {
sum := 0
payload := 0
digits := []int{}
for _, char := range str {
if unicode.IsDigit(char) {
digit := int(char - '0')
digits = append(digits, digit)
}
}
if len(digits) == 0 {
return false
}
payload = digits[len(digits)-1]
for i := 0; i < len(digits)-1; i++ {
digit := digits[i]
if (len(digits)-2-i)%2 == 0 {
digit *= 2
if digit > 9 {
digit -= 9
}
}
sum += digit
}
checkDigit := (10 - (sum % 10)) % 10
return payload == checkDigit
}
Conclusion
In this article, we explored two interesting programming challenges: finding double existence in an array and implementing Luhn's Algorithm for validation. These tasks highlight how different programming languages can tackle similar problems with their own unique approaches. I hope these examples inspire you to delve deeper into both Perl and Go!
You can find the complete code, including tests, on GitHub.
Top comments (0)