Finally, for Perl Weekly Challenge 243 I get my musical association mojo back, and the first challenge immediately made me think of King Crimson’s Three of a Perfect Pair.

I’m listening to the album while I write these solutions.

Task 1: Reverse Pairs

You are given an array of integers.

Write a script to return the number of reverse pairs in the given array.

A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].

Example 1

Input: @nums = (1, 3, 2, 3, 1)
Output: 2

(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2

Input: @nums = (2, 4, 3, 5, 1)
Output: 3

(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Approach

This is a pretty straightforward nested loop over an array: one loop for i from 0 to array length – 1, and an inner loop for j from i to array length. Just to make things easier to read, I’m going to make the test a function, isReversePair(), so the code is more expressive.

Raku

sub isReversePair(@arr, $i, $j) {
  return @arr[$i] > 2 * @arr[$j];
}

sub findReversePairs(@arr) {
  my @pairs;
  for 0 .. @arr.elems - 2 -> $i {
    for $i+1 .. @arr.elems - 1 -> $j {
      @pairs.push([$i, $j]) if isReversePair(@arr, $i, $j);
    }
  }
  return @pairs;
}

Now, I don’t have to test condition a) of the definition of a reverse pair, because the way I’m looping, 0 <= i < j < nums.length will always be true.

But you know what? That’s boring. I feel like, in Raku, at least, I should be able to make isReversePair() a method call on the array… and in Raku, I can. It took a little bit of searching for examples of how to extend the Array class, but I found it in the Raku Advent Calendar for Dec 8, 2013: Array-based Objects. In retrospect, it seems obvious that all I would need to do in a method to access the array elements is self[].

class ReversePairArray is Array {
  method isReversePair($i, $j) {
    return self[$i] > 2 * self[$j];
  }
}

sub findReversePairs(@arr) {
  my @pairs;
  my @rpArray := ReversePairArray.new(@arr);
  for 0 .. @rpArray.elems - 2 -> $i {
    for $i+1 .. @rpArray.elems - 1 -> $j {
      @pairs.push([$i, $j]) if @rpArray.isReversePair($i, $j);
    }
  }
  return @pairs;
}

The one thing that I’m glad the advent calendar entry addressed was the need for := instead of = if I wanted to use the sigil @ on my variable. Without the colon, a positional container (a variable with the sigil @) will be created as an empty Array whose contained values are then set to the list after the =. I could have used a $ for a variable that would hold any type and used a =, but I wanted to make this feel as array-like as possible.

View the entire Raku script for this task on GitHub.

Perl

sub isReversePair {
  my ($arr, $i, $j) = @_;
  return $arr->[$i] > 2 * $arr->[$j];
}

sub findReversePairs {
  my @arr = @_;
  my @pairs;
  foreach my $i ( 0 .. $#arr - 1) {
    foreach my $j ( $i+1 .. $#arr) {
      push @pairs, [$i, $j] if isReversePair(\@arr, $i, $j);
    }
  }
  return @pairs;
}

For Perl, however, I arrays aren’t built-in classes that I can easily override, so I’m just going with the boring function-based approach where I’m passing in a reference to the array and the two indices I’m checking.

If I was concerned with performance over expressiveness, I could just inline the condition and forgo the function isReversePair():

sub findReversePairs {
  my @arr = @_;
  my @pairs;
  foreach my $i ( 0 .. $#arr - 1) {
    foreach my $j ( $i+1 .. $#arr) {
      push @pairs, [$i, $j] if $arr[$i] > 2 * $arr[$j];
    }
  }
  return @pairs;
}

View the entire Perl script for this task on GitHub.

Python

from collections import UserList

class ReversePairArray(UserList):
    def isReversePair(self, i, j):
        return self.data[i] > 2 * self.data[j]

def findReversePairs(nums):
    pairs = []
    rpArray = ReversePairArray(nums)
    for i in range(0, len(nums) - 1):
        for j in range(i+1, len(nums)):
            if rpArray.isReversePair(i, j):
                pairs.append([i, j])
    return pairs

I had to do a bunch of Googling to figure out the best way to extend arrays, and it seems that collections.UserList was the best candidate:

This class acts as a wrapper around list objects. It is a useful base class for your own list-like classes which can inherit from them and override existing methods or add new ones. In this way, one can add new behaviors to lists.

View the entire Python script for this task on GitHub.

Task 2: Floor Sum

You are given an array of positive integers (>=1).

Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.

Example 1

Input: @nums = (2, 5, 9)
Output: 10

floor(2 / 5) = 0
floor(2 / 9) = 0
floor(5 / 9) = 0
floor(2 / 2) = 1
floor(5 / 5) = 1
floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1

Example 2

Input: @nums = (7, 7, 7, 7, 7, 7, 7)
Output: 49

Approach

Another nested loop over an array. This time we’re just summing the results of performing integer division on each of the elements against each other. I don’t quite grok the arrangement of the explanatory text in Example 1; I feel like it should be sorted like this:

floor(2 / 2) = 1
floor(2 / 5) = 0
floor(2 / 9) = 0
floor(5 / 2) = 2
floor(5 / 5) = 1
floor(5 / 9) = 0
floor(9 / 2) = 4
floor(9 / 5) = 1
floor(9 / 9) = 1

For the second example, it’s just going to be dividing 7 by itself each time, yielding 1. Since there’s 7 elements in the input list, we’re doing this division 49 (7²) times.

Raku

sub floorSum(@arr) {
  my $sum = 0;
  for 0 .. @arr.elems - 1 -> $i {
    for 0 .. @arr.elems - 1 -> $j {
      $sum += (@arr[$i] / @arr[$j]).truncate;
    }
  }
  return $sum;
}

View the entire Raku script for this task on GitHub.

Perl

sub floorSum {
  my @arr = @_;
  my $sum = 0;
  foreach my $i (0 .. $#arr) {
    foreach my $j (0 .. $#arr) {
      $sum += int($arr[$i] / $arr[$j]);
    }
  }
  return $sum;
}

View the entire Perl script for this task on GitHub.

Python

from math import trunc

def floorSum(nums):
    sum = 0;
    for i in range(0, len(nums)):
        for j in range(0, len(nums)):
            sum += trunc(nums[i] / nums[j])
    return sum

View the entire Python script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-243/packy-anderson