18 October 2026

Challenge 012

Euclidean Paths

• Task 1: Smallest non-prime Euclid number
• Task 2: Common directory

Task 1: Smallest non-prime Euclid number

---

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.

---

Solution

My comment and solution dated 13 Mar 2023:

Build a generator for non-prime Euclid numbers and print the first N thereof (Default: N = 1)

use strict;
use warnings;
use bigint;
use List::Gen;
use Math::Prime::Util qw(is_prime pn_primorial);

<1..>->map(sub{pn_primorial($_)+1})->filter(sub{!is_prime($_)})->say(shift||1);

See the full solution to task 1.

Task 2: Common directory

---

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.

/a/b/c/d
/a/b/cd
/a/b/cc
/a/b/c/d/e

and the path separator is /. Your script should return /a/b as common directory path.

---

Solution

There is room for interpreting this task.

Here are some assumptions / decisions:

• Using / as the separator in the following examples.
• A path is a sequence of file names, optionally starting with and/or ending in the separator and separated by it.
• A file name is a sequence of characters different from the separator and NUL (or "\0"). It may contain any other character including e.g. newlines.
• A directory path of a path is a prefix of the path ending in the separator, but not including it. I.e. /a/b is a directory path from /a/b/c but /a/b/c is not. And /a/b/c is a directory path from /a/b/c/. One exception: the root path / is a directory path.
• Repeated separators are equivalent to a single separator, i.e. /a/b/c and /a///b//c are equivalent.
• The special file name . acts as a no-op: the paths /a/b/c and /a/b/./c are equivalent.
• The special file name .. steps up one level, i.e. the paths /a/b/c and /a/b/d/../c are equivalent. Furthermore, stepping above the root directory is regarded as a no-op, i.e. /../a/b/ and /a/b/ are equivalent, while ../a/b/ and a/b/ are not.

The solution consists in canonicalizing the given paths and finding the longest common directory prefix thereof. The root path shall be provided as the fallback when all paths are absolute but do not share any longer common directory path.

The NUL character is the only character that cannot be part of a path. Therefore all the given paths may be joined with the NUL character resulting in an unambiguous representation that can be matched against a regular expression to find the largest common directory prefix.

Using the (quoted) first character from the provided first argument as the separator. Most characters should work, though using a dot . will disable the usage of “stepping up” as .a....b will be canonicalized to .a.b instead of .b

use strict;
use warnings;
use experimental 'signatures';

sub common_path ($sep, @paths) {
    my $qs = quotemeta substr $sep, 0, 1;
    my $cp = qr{
        ^
        (?:
            ((?&P)+) (?&T)
            (?: \1 (?&T))*+
        |
            (?=((?&S))) (?&T)++
        )
        \z

        (?(DEFINE)
            (?<S> $qs)                   # Separator
            (?<P> $qs?+ [^$qs\0]++)      # path Part
            (?<T> $qs [^\0]*+ (?:\0|\z)) # path Tail
        )
    }x;
    for (@paths) {
        s/($qs)+/$1/g;
        s/(?:^|$qs)\K\.$qs//g;
        1 while s/(?:$qs|^)[^$qs]*+$qs\.\.(?=\z|$qs)//;
    }

    join("\0", @paths) =~ m{$cp};

    $1 // $2;
}

See the full solution to task 2.