Python and Perl solutions to the weekly challenge 327

Task 1: Missing Integers:

You are given an array of n integers.

Write a script to find all the missing integers in the range 1..n in the given array.

Just offhand, I can think of several approaches to this problem:

• loop over the range and for each number loop over the input
• dict/hash the input and loop over the range
• sort the input and iterate over it
• store in a Judy1 set and iterate over missing values in the range
• set difference
• store the input in a bitarray and find the 0's

bitarrays are something I haven't used recently, so I went with that.

In Python, there seem to be a couple of main choices for bitarrays, bitarray and BitVector, while Perl has builtin support (using vec and bitwise string operators) but also Bit::Vector and Algorithm::BitVector. Unfortunately, most of these expect to do input and output in the form of a single string or number representing the bits, not a list of indices. Since that's what I want, I'll use the ones that come closest.

In Python, using bitarray, first we make the object, with a size of the number of inputs plus one (since we will not use the lowest bit, for convenience of not having to shift between 1..n and 0..n-1):

a = bitarray(len(ints)+1)

Then we sadly have to set each bit one by one (you can set a slice but not a list):

for i in ints:
    if 0 < i <= len(ints):
        a[i] = 1

Now we just need to get the list of 0 bits. bitarray provides a powerful search method returning an iterator that can find a particular bit sequence, optionally with a start and end and optionally in reverse. Here we'll search for 0, starting from 1, the second lowest bit:

print(list(a.search(0, 1)))

In Perl, using Bit::Vector, first make the object (again, using size n+1), but initialize the lowest bit to 1 so we don't find it when we look for the 0's:

my $v = Bit::Vector->new_Bin(@ints + 1, 1);

Bit::Vector does provide a way to set bits from a list of indices:

$v->Index_List_Store(grep $_ > 0 && $_ <= @ints, @ints);

It doesn't provide a way to get the indices where the value is 0 though, so invert all the bits and find the 1's:

$v->Flip();
say for $v->Index_List_Read();

full script, Python
full script, Perl

Task 2: MAD:

You are given an array of distinct integers.

Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.

(My first thought was I'd need two essentially separate sets of code, one for if the MAD is 0 and one for if it is non-zero, with the 0 MAD code properly returning e.g. 6 pairs from (1,1,1,1). Then I saw the "distinct" in the problem description.)

Here, I don't see a lot of options, just sorting the input and looping over it. Any solution that doesn't involve sorting seems likely to be less quick and simple.

Sort the input:

ints.sort()

We'll iterate over overlapping pairs, keeping track of the minimum difference found so far and all the lower numbers of each pair with that minimum difference:

min_difference = None
pair_starts = []

itertools pairwise makes the iteration simple:

for x,y in itertools.pairwise(ints):
    if min_difference is None or y - x < min_difference:
        min_difference = y - x
        pair_starts = [x]
    elif y - x == min_difference:
        pair_starts.append(x)

and output the pairs:

for i in pair_starts:
    print([i, i + min_difference])

The Perl is pretty much the same. Sort, and declare our tracking variables (Perl's sort doesn't do anything useful except in list context:

@ints = sort { $a <=> $b } @ints;
my $min_difference;
my @pair_starts;

In Perl, the easiest way to loop over overlapping pairs in an array is with a C-style for loop:

for (my $i = 1; $i < @ints; ++$i) {

Since our loop gives us indices rather than pairs of values, go ahead and use another variable for the difference, to avoid lots of extra array fetches:

    my $difference = $ints[$i] - $ints[$i-1];
    if (! defined $min_difference || $difference < $min_difference) {
        $min_difference = $difference;
        @pair_starts = ($ints[$i-1]);
    }
    elsif ($difference == $min_difference) {
        push @pair_starts, $ints[$i-1];
    }
}

And output:

for my $int (@pair_starts) {
    say sprintf '[%d, %d]', $int, $int + $min_difference;
}

full script, Python
full script, Perl

See you next week.