Fun challenges this week! But first: I’m honored to be mentioned in the Perl Weekly Newsletter for the second time now. I’m especially honored by the very flattering notion that I’m somehow becoming popular with these posts. It’s enouraging me to make some time to write about things beyond just these challenges.

Challenge 1

The numbers formed by adding one to the products of the smallest primes are called the Euclid Numbers (see wiki). Write a script that finds the smallest Euclid Number that is not prime. This challenge was proposed by Laurent Rosenfeld.

For this challenge, I decided to things in a bit more sophisticated manner than the approach I took earlier with the 1st challenge in PWC Week 9. Two fellow participants (Dave Jacoby and Laurent Rosenfeld) solved that challenge using a prime numbers iterator, with Laurent also using closures for the iterator. I love closures, so I took that approach as well. I also love modularizing code, so I have a few subs I used for this challenge:

sub is_prime {
    my $n = shift;

    return 0 if grep { $n % $_ == 0 } ( 2 .. sqrt($n) );

    return 1;
}

sub prime_iterator {
    my $n = 1;
    return sub {
        1 until is_prime ++$n;
        return $n;
        }
}

sub euclid_prime_iterator {
    my $prime_iter = prime_iterator();
    my $prime_prod = 1;
    return sub {
        $prime_prod *= $prime_iter->();
        return $prime_prod + 1;
        }
}

You’ve probably seen something like the is_prime function above somewhere on the internet or maybe a textbook. Basically, it goes through all integers between 2 and the square root of the input value and checks if any of those values can evenly divide the input. In scalar context, as above, the grep function will return how many times the expression in the block was true. So we should return 0 if grep returns any non-0 value since that means at least one value was able to divide the input.

prime_iterator also works fairly simply, but if you’ve never seen a closure in Perl, I suggest reading the appropriate section in chromatic’s Modern Perl (2016). I’ll briefly describe the concept here anyway, for completeness, but in a simplified way.

Basically, if you declare an anonymous subroutine (eg, my $anon_sub = sub {...}), it can “save” the variables of its enclosing scope. In the code above, I declared $n and initialized it to 1. The anonymous sub is returned to the caller. However, that sub still has access to $n with whatever value it had when the sub created. What’s more, it can modify the value of $n, and the next time you call the anonymous sub, the new value of $n is what will be used.

This lets us essentially save time: each time the sub above is called, the code inside is called starting with whatever the last value of $n was. If we were already up to $n = 257 , the next time the sub is called, we don’t have to rediscover the primes in the range 2 .. 256 before we look for the next prime after 257. The closure let us save the state of $n. And each call to prime_iterator has its own copy of $n, which is totally independent from any others, so you can have multiple iterators all with their own state.

We can use that iterator then for the next function, euclid_prime_iterator. That sub uses the iterator created by prime_iterator to generate its sequence, again making use of a closure. Anonymous subs can also be saved as scalar variables, so declaring an anonymous function after initializing the prime numbers iterator works the same way as it did with $n above. Since the iterator saved in $prime_iter and the variable $prime_prod keep their state, each call to the iterator generated by euclid_prime_iterator picks up right after the previous call, and generates the very next Euclid prime without needless recalculation.

The challenge itself is solved by this bit of code, at the end of my script:

# scen = Smallest Composite Euclid Number
my $iter = euclid_prime_iterator();
my $scen = 0;
$scen = $iter->() until ( is_prime($scen) == 0 );
say $scen;

As soon as the value returned by the iterator is non-prime (ie, composite), we stop the until loop and print the value to the screen. Since we know that this will reach a stop condition, I did not include some kind of bail-out condition to prevent it from running too long.

Challenge 2

Write a script that finds the common directory path, given a collection of paths and directory separator. For example, if the following paths are supplied.

My solutions tend to be far more verbose than other participants, but I’m OK with that ☺. This solution is no exception.

sub find_common_path {
    my ( $path_sep, $paths_ref ) = @_;
    my @common_path;

    for my $p ( @{$paths_ref} ) {
        my @split_p = split /$path_sep/, $p;
        unless (@common_path) {
            @common_path = @split_p;
            next;
        }

        if ( @split_p < @common_path ) {
            @common_path = @common_path[ 0 .. @split_p - 1 ];
        }

        for my $i ( 0 .. @common_path - 1 ) {

            # Stop processing this path as soon as we encounter
            # a directory not seen before
            if ( $split_p[$i] ne $common_path[$i] ) {

                # Save only the so-far shared path.
                # The array will always have one element
                # thanks to the fact that the first separator
                # is also the first character.
                @common_path = @common_path[ 0 .. $i - 1 ];
                last;
            }
        }

        return ('') if (@common_path == 1 && $common_path[0] eq '');
    }

    return @common_path;
}

I keep an array of the directories which are in common so far (@common_path). For the first item in the path list, this saves the entire array of directories into @common_path and moves on.

For subsequent paths, we simply check each directory in order, truncating the common path so far, if necessary because the common directory list can only be as long as the shortest path. In order to be a common path, the directories have to match both in names and in position. So we iterate over the @common_path array by index and compare both arrays at each index. As soon as we discover a different, we cut off the @common_path array so that only the shared directories are kept.

After the first path is processed, the first element of @common_path will always be '', since the split function will return elements around the separators. For example, you execute split "/", "/path", you will get a list composed of the elements ('', 'path') because split cuts at the separator /, and the empty string was to the left of the / in "/path". This means that @common_path is guaranteed to always have at least one element, ensuring the array slice I take above always works.

At the end of the outer for loop, I bail out and stop processing any remaining paths if there is no shared directories up to this point. Finally, the @common_path array is returned after all paths are processed successfully.

Challenge 3

Find out the synonyms of a given word using the Synonyms API. The API challenge is optional but would love to see your solution.

Will I get to challenge 3 this week? We shall see!