Find the shortest unique prefix

This is a solution of the Task 2 from Week 57 of the Perl Weekly Challenge. Find the shortest unique prefixes for the given list of words.

This is a solution of the Task 2 from Week 57 of the Perl Weekly Challenge.

Find the shortest unique prefixes for the given list of words.

In other words, for every word from a list, find its shortest prefix that is not a prefix of any other word in the same list.

Here is the list of words:

my @words = < alphabet book carpet cadmium cadeau alpine >;

Let us just loop over it and prepare the list of other words:

for @words -> $word {
    my @other_words = @words.grep: * ne $word;

    . . .
}

The @other_words array contains everything from the original array except the current word.

Now, loop over all possible prefixes of the current word:

for 1..$word.chars -> $length {
    my $prefix = $word.substr(0, $length);
    . . .
}

Finally, test if this prefix can be a prefix of any other word:

unless @other_words.first: * ~~ /^$prefix/ {
    say $prefix;
    last;
}

If there is no such prefix, this is what we are looking at. So we can stop any further searches for the current word. Here, the two elements help to stop the iteration asap: these are using the first method and the last keyword.

Here is the whole program together:

my @words = < alphabet book carpet cadmium cadeau alpine >;

for @words -> $word {
    my @other_words = @words.grep: * ne $word;

    for 1..$word.chars -> $length {
        my $prefix = $word.substr(0, $length);

        unless @other_words.first: * ~~ /^$prefix/ {
            say $prefix;
            last;
        }
    }
}

This program prints the following output:

$ raku ch-2.raku 
alph
b
car
cadm
cade
alpi

GitHub repository
Navigation to the Raku challenges post series

Leave a Reply

Your email address will not be published. Required fields are marked *

Retype the CAPTCHA code from the image
Change the CAPTCHA codeSpeak the CAPTCHA code