PWC 252 Special Numbers
Tags: perl, perlweeklychallenge, pwc
Published: 2024-01-28 14:36:16

## [Task 1: Special Numbers](https://theweeklychallenge.org/blog/perl-weekly-challenge-252/#TASK1)

```text
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"](https://www.youtube.com/watch?v=0H6re3PCP3E) ... 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:
```perl
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](https://perldoc.perl.org/perlvar#$%5B) 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.
```perl
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.