PWC 300 › “You there, Perl, may you live forever!”

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

(Yes, the title is a reference to the 2006 Zach Snyder film.)

I’d say I can hardly believe we’ve hit the 300th week in a row of the Weekly Challenge. But, then again, knowing a little bit about the persistence and work ethic of Mohammad Anwar, it’s really no surprise. Let’s keep this going for a good while longer!

Task 1: Beautiful Arrangements

The first task this week has us take a positive $integer and look at every permutation @P of the numbers 1..$int. We then return the count of permutations where every element in @P is either divisible by its 1-based index, or the index is divisible by the element.

For example, beautiful(3) has six possible permutations. Note a|b means “a divides b”:

Therefore beautiful(3) = 3. Some other results:

beautiful(1)  =     1
beautiful(2)  =     2
beautiful(3)  =     3
beautiful(4)  =     8
beautiful(5)  =    10
beautiful(6)  =    36
beautiful(7)  =    41
beautiful(8)  =   132
beautiful(9)  =   250
beautiful(10) =   700
beautiful(11) =   750
beautiful(12) = 4,010

The code ends up being much more concise than my explanation:

use Algorithm::Permute;

sub beautiful($int) {
    my $perms = Algorithm::Permute->new([1..$int]);
    my $count = 0;

P:  while (my @P = $perms->next) {
        $P[$_-1] % $_ and $_ % $P[$_-1] and next P for 1..$int;
        $count++;
    }
    $count;
}

I’ve written code to generate permutations in previous tasks, and permutations are more of a side quest in this particular task. So, I chose to simply use the very popular Algorithm::Permute CPAN module instead.

Since we are checking every possible permutation of n = $int elements, the time complexity of this algorithm is an eye-wateringly bad O(n!), which is why I opted to stop after beautiful(12) looked at 12! = 479,001,600 permutations.

You’ll note the use of next P, which effectively short-circuits the inner loop as soon as any of the conditions aren’t met. This speeds things up considerably. Not enough to move the needle away from factorial big-O complexity, but in practical terms, beautiful(10) returned the correct answer in about a third of the time, compared to a non-short-circuiting version.

Line 8 (highlighted) uses the common technique with modulo arithmetic to handle the “divides” checks, since $b % $a will be a true value if and only if $a does not divide $b, since there would be a remainder.

ch-1.pl source code

Task 2: Nested Array

The second task this week has us take an arbitrary permutation, P, of n integers between (0..n-1) and return the length of the longest sequence generated by starting at some index i and chaining as follows, until we reach a cycle:

          i → P[i] → P[ P[i] ] → ⋯ → P[P[ … P[i] … ]]

That sequence is easy to generate iteratively:

use List::Util qw< max >;

sub longest_set_len(@ints) {
    max map {
        my %seen;
        $_ = $ints[$_] while not $seen{$_}++;
        scalar keys %seen;
    } 0..$#ints;
}

We detect a cycle by tracking %seen values in a hash. An array would work just as well, but it would not be significantly faster, and this way we don’t have to track some separate counter; we can just return the number of keys as our result for each starting point.

The use of (core module) List::Util here gives us some more expressive syntax with the max function. Each loop through (the body of map { ... }) represents one starting index into the sequence.

ch-2.pl source code