PWC 056 › Diff-K

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.)

Task #1 this week is to implement the Diff-K algorithm, as explained by Mohammad:

You are given an array @N of positive integers (sorted) and another non negative integer k. Write a script to find if there exists 2 indices i and j such that A[i] – A[j] = k and i != j.

This one is pretty easy. We can boil down the solution into two operations for each element ($_) of @N:

• First, filter @N for elements where $k+$_ exists in @N.
• For the remaining elements, return an array containing the indexes of $k+$_ and $_.

To make this easier and more efficient, we’ll create an %idx_of hash to store the index of each element in @N. This can be created in linear time, and gives us O(1) lookups for both operations, above.

I really like how easy it is to create a reverse hash like this in Raku:

my %idx_of = @N.antipairs;

In Perl, the procedure is familiar and comfortable, but I have to admit, not as nice!

my %idx_of = map { $_[$_] => $_ } 0..$#_;

Note that reverse is quite often used to reverse hashes in Perl, but isn’t useful in this particular case, because we didn’t have a hash to reverse yet. Thus, it was easier to simply build the hash I wanted from scratch.

Here’s how the full implementation looks in Raku and Perl:

Raku

#| Diff-K in O(n) time
sub diff_k( $k, @N ) {
    my %idx_of = @N.antipairs;

     @N.grep( {   %idx_of{ $k+$_ }:exists  } )
     ==> map( { [ %idx_of{ $k+$_,$_ } ]    } )
}

Usage is easy:

my @list = < 0  2  3  5  6  7  9 10 11 14 15 16 17 18 19 21 22
            25 28 29 31 32 33 34 35 37 38 40 41 44 46 47 48 49>;
say @list;

say diff_k(30, @list);

Output:

[0 2 3 5 6 7 9 10 11 14 15 16 17 18 19 21 22 25 28 29 31 32 33 34 35 37 38 40 41 44 46 47 48 49]
([21 1] [22 2] [24 3] [25 5] [27 7] [28 8] [29 9] [30 11] [31 12] [32 13] [33 14])

Perl

The Perl code only differs syntactically.

sub diff_k {
    my $k = shift;
    my %idx_of = map { $_[$_] => $_ } 0..$#_;

    map  {      [ @idx_of{ $k+$_, $_ } ] }
    grep { exists $idx_of{ $k+$_ }       } @_;
}

In both cases, the list is fed through grep first, then map. Note the use of hash slices to pull out values of %idx_of{ $k+$_ } and %idx_of{ $_ } at once.

Efficiency Analysis

Both the Raku and Perl versions follow the same operations, and both languages have the same big-O efficiency for those operations, so it suffices to look at just one. (OK, the Perl version does have an additional step in the my $k = shift line, but shift is a constant-time operation in Perl, so we can ignore it.)

• The %idx_of = map { ... } line is O(n) on the size of @N. The map block is just an array lookup and a list, which are both constant-time operations.
• The grep also is O(n) on the size of @N. Its block only has an addition and O(1) hash lookup, so O(n) holds.
• The map operates on whatever made it through grep, so it certainly can’t be larger than n elements. The block has two hash lookups and an array ref creation, which are all O(1), thus this line is O(n) as well.

Therefore, this entire routine’s worst case performance is O(n). I don’t believe it is possible to obtain a better growth rate.

That’s it for this task! See you on the next one.