Perl Weekly Challenge: Week 96

Challenge 1:

Reverse Words

You are given a string $S.

Write a script to reverse the order of words in the given string. The string may contain leading/trailing spaces. The string may have more than one space between words in the string. Print the result without leading/trailing spaces and there should be only one space between words.

Example 1

Input: $S = "The Weekly Challenge"
Output: "Challenge Weekly The"

Example 2

Input: $S = "    Perl and   Raku are  part of the same family  "
Output: "family same the of part are Raku and Perl"

This is a one-liner in Perl...

say join q{ }, (reverse @ARGV);

(Full code on Github.)

...and in Raku

@*ARGS.reverse.join(q{ }).say;

(Full code on Github.)

Challenge 2:

Edit Distance

You are given two strings $S1 and $S2.

Write a script to find out the minimum operations required to convert $S1 into $S2. The operations can be insert, remove or replace a character. Please check out Wikipedia page for more information.

Example 1

Input: $S1 = "kitten"; $S2 = "sitting"
Output: 3

Operation 1: replace 'k' with 's'
Operation 2: replace 'e' with 'i'
Operation 3: insert 'g' at the end

Example 2

Input: $S1 = "sunday"; $S2 = "monday"
Output: 2

Operation 1: replace 's' with 'm'
Operation 2: replace 'u' with 'o'

Now solving this problem was a little more complicated. The wikipedia page mentioned in the spec described various algorithms for edit distance and I picked Levenshtein Distance as the seemingly easiest to implement. This is it in Raku:

sub levenshtein(Str $from, Str $to) {
    my $fromLength = $from.chars;
    my $toLength = $to.chars;

    if $fromLength == 0 {
        return $toLength;
    }

    if $toLength == 0 {
         return $fromLength;
    }

    my $fromTail = $from.substr(1, $fromLength - 1);
    my $toTail = $to.substr(1, $toLength - 1);

    if $from.substr(0, 1) eq $to.substr(0, 1) {
        return levenshtein($fromTail, $toTail);
    }

    return 1 + (
        levenshtein($from, $toTail),    # Insert
        levenshtein($fromTail, $to),    # Remove
        levenshtein($fromTail, $toTail) # Replace
    ).min;
}

A small disappointment I had is that Raku has .head() and .tail() methods but only for sequences not strings so I had to use .substr() instead.

(Full code on Github.)

This is the Perl version:

sub levenshtein {
    my ($from, $to) = @_;
    my $fromLength = length $from;
    my $toLength = length $to;

    if ($fromLength == 0) {
        return $toLength;
    }

    if ($toLength == 0) {
        return $fromLength;
    }

    my $fromTail = substr($from, 1, $fromLength - 1);
    my $toTail = substr($to, 1, $toLength - 1);

    if (substr($from, 0, 1) eq substr($to, 0, 1)) {
        return levenshtein($fromTail, $toTail);
    }

    return 1 + min(
        levenshtein($from, $toTail), # Insert
        levenshtein($fromTail, $to), # Remove
        levenshtein($fromTail, $toTail) # Replace
    );
}

Perl doesn't have a builtin .min() method like Raku but it is easy to emulate it like this:

sub min {
    return (sort { $a <=> $b } @_)[0];
}

(Full code on Github.)