Finding Double Existence and Applying Luhn's Algorithm

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
• Luhn's Algorithm
• Conclusion

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.

1. Counting from the right, double the value of the first, third, etc., of the remaining digits.
2. For each value now greater than 9, sum its digits.
3. 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.