PWC 252 Special Numbers

Task 1: Special Numbers

You are given an array of integers, @ints.
Write a script to find the sum of the squares
of all special elements of the given array.

An element $int[i] of @ints is called special
if i divides n, i.e. n % i == 0.
Where n is the length of the given array.
Also the array is 1-indexed for the task.

Example 1

Input: @ints = (1, 2, 3, 4)
Output: 21

There are three special elements in the given array: $ints[1] since 1 divides 4, $ints[2] since 2 divides 4, and $ints[4] since 4 divides 4.
(1 * 1) + (2 * 2) + (4 * 4) = 21

Example 2

Input: @ints = (2, 7, 1, 19, 18, 3)
Output: 63
The special elements are at indices 1,2,3, and 6.
(2 * 2) + (7 * 7) + (1 * 1) + (3 * 3) = 63

Thoughts

[ Starts humming "Brass in Pocket" ... special, so special, give it to me ... ]

Indexing from 1 is a minor annoyance, but easily worked around by mapping a -1 in there somewhere; or we can rig the game by inserting an unused element to the beginning of the array.

What we seem to be doing here is finding the factors of the length of the array, and then using those factors to index the array. In example 1, the length is 4, and the factors of 4 are (1,2,4). In example 2, the length is 6, and the factors of 6 are (1,2,3,6).

So I see two direct solutions. One is to factor the length, and use a hash slice to extract the elements. The other is to iterate over the sequence from 1 to length and select elements from the array. Once the indices are known, squaring and adding is easily done.

The kind-of-mathy solution

Calculating the factors and then using them as indices is probably the less efficient solution, but let's do it for fun anyway. Suppose we have the function factorsOf($n) available; then we need to select the factors that are in the range of the array. How about this:

sub sn2(@ints)
{
    use List::MoreUtils qw/before/;
    my $len = @ints;
    return 0 if $len == 0;
    my @choose = map { $_ - 1 } before { $_ > $len } factorsOf($len)->@*;
    return sum0 map { $_ * $_ } @ints[@choose];
}

The interesting line here is the one that sets up the @choose array. Let's break it down.

• factorsOf($len)->@* -- our factoring function will return a reference to an array of the factors, in ascending order. This postfix notation will yield the list of numbers
• before { $_ > $len } ... -- Browsing through List::MoreUtils is always fun (for small values of fun). before is one of the partitioning utilities. We have a sorted list, and we want the part that will give us valid indices
• map { $_ - 1 } ... -- Here's that pesky shift from 1-based indexing to 0-based. Choosing your own index base was a popular feature of languages of the 1970's like PL/1 and Pascal. Perl used to have a special variable to change indexing, but it was deprecated in version 5.12 and disabled in version 5.30.

That leaves us with a list of indexes in the @choose variable. The rest is array operations.

• @ints[@choose] -- We select the array elements all at once with a hash slice
• map { $_ * $_ } -- Each selected element is transformed to its square
• sum0 -- from List::Util, this reduces an array to the sum of its elements. It's slightly different from sum because it yields 0 for an empty array, where sum would complain about undefined values.

I'll leave factorsOf as an exercise for the reader.

The more likely solution

The solution that's probably easier and more efficient is to iterate over the array and select based on testing divisibility. And by "iterate", I mean use array operations to avoid iteration.

sub specialNumbers(@ints)
{
    my $len = @ints;
    # Insert an extra element at the front to make it 1-indexed
    unshift @ints, $len+1;

    return sum0 map { $_ * $_ } @ints[ grep { $len % $_ == 0 } 1 .. $len ];
}

In this solution, I rid myself of the pesky 1-based indexing by putting an unused element at the front of the array with unshift. The solution collapses into one line. Let's unpack it from right to left.

• 1 .. $len -- We start with the list of possible indexes.
• grep { $len % $_ == 0 } 1 .. $len -- We're selecting from the list of indexes, using exactly the criteria from the problem statement.
• @ints[ grep...] -- Using the list of selected indexes, we take a hash slice of the original array
• sum0 map { $_ * $_ }... -- As before, we calculate the sum of the squares.