RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved list analysis and Luhn's checksum algorithm. (Note that this ends today.)

Task 1: Double Exist

You are given an array of integers, @ints.

Write a script to find 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]

Where the language had a built-in combination function (Ruby, Crystal, Raku) I used it, but althrough I've written combination generators for the other languages nested loops seemed just as viable.

PostScript:

/doubleexist {
    0 dict begin
    /a exch def

The default return value is false.

    false

Run the i index from 0 to the last-but-one element;

    0 1 a length 2 sub {
        /i exch def

Then the j index from i+1 to the end. This gives us each pair once.

        i 1 a length 1 sub {
            /j exch def

Get the pair out of the array, then check for a[i] being twice a[j] or vice versa. If so, flip the answer to true and exit.

            a i get a j get
            2 copy
            2 mul eq
            3 1 roll
            exch 2 mul eq or {
                pop true
                exit
            } if
        } for
        dup {
            exit
        } if
    } for
    end
} bind def

With combinations, in Ruby, it's rather less verbose:

def doubleexist(a)
  a.combination(2).each do |i|
    if i[0] == 2 * i[1] || i[1] == 2 * i[0]
      return true
    end
  end
  false
end

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.

I decided to do this piecewise as laid out in the specification. There might be efficiency gains to be had by taking a single pass through the digit list, amending the value if appropriate, and adding it to a running sum.

To demonstrate how trivial it is, all my code will ignore non-numeric characters. I still see web sites today that insist on having, or on not having, the cosmetic spaces in a credit card or telephone number.

Raku:

sub luhnalgorithm($a) {

Each digit becomes a list entry.

    my @digits = $a.comb.grep(/\d/);

Last digit is the payload; reverse the rest for convenience.

    my $payload = @digits.pop;
    @digits = @digits.reverse;

Double and if necessary reduce every second digit.

    loop (my $i = 0; $i < @digits.elems; $i += 2) {
        @digits[$i] *= 2;
        if (@digits[$i] > 9) {
            @digits[$i] -= 9;
        }
    }

Calculate and verify the checksum.

    10 - (@digits.sum % 10) == $payload;
}

Full code on github.