RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a string $S. Write a script to reverse the order of words in the given string.

Solution

use strict;
use warnings;

sub reverse_words{
    my($words) = @_; 
    if(@{$words}){
        my $word = $words->[0];
        my $a = reverse_words([@{$words}[1 .. (@{$words} - 1)]]);
        $a->[@{$a}] = $word;
        return $a;
    }
    return [];
}

MAIN:{
    my($S, $reversed);
    $S = "The Weekly Challenge";
    $reversed = reverse_words([split(/\s+/, $S)]);
    print join(" ", @{$reversed}) . "\n";
    
    $S = "    Perl and   Raku are  part of the same family  ";
    $reversed = reverse_words([split(/\s+/, $S)]);
    print join(" ", @{$reversed}) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
Challenge Weekly The
family same the of part are Raku and Perl 

Notes

My solution is done using recursion with the self-imposed restrictions

• do not use the reverse function.
• only access array elements in an ordinary way, without using any functions

Other than being a bit over engineered it works as required!

Part 2

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.

Solution

use strict;
use warnings;

use Memoize;
memoize("edit_distance");

sub edit_distance{
    my($s, $t) = @_;
    if(length($s) == 0){
        return length($t);
    }
    if(length($t) == 0){
        return length($s);
    }
    my($s0, $t0) = (substr($s, 0, 1), substr($t, 0, 1));
    if($s0 eq $t0){
        return edit_distance(substr($s, 1), substr($t, 1));
    }
    my @sorted_distances = sort {$a <=> $b} (
        edit_distance($s, substr($t, 1)),
        edit_distance(substr($s, 1), $t),
        edit_distance(substr($s, 1), substr($t, 1)),
    );
    return 1 + $sorted_distances[0];
}

MAIN:{
    my $distance;
    
    $distance = edit_distance("kitten", "sitting");
    print "$distance\n";

    $distance = edit_distance("sunday", "monday");
    print "$distance\n";
}

Sample Run

$ perl perl/ch-2.pl
3
2

Notes

This code is a pretty faithful Perl translation of the algorithm presented in Haskell in the Wikipedia article for Levenshtein_distance. Like the code for Part 1 of this weeks Challenge this is a recursive procedure.

As noted in that article this algorithm is inefficient in that substrings are checked repeatedly. This code can be made more efficient by the use of Memoization so that the results for each substring are saved and re-used. In the interest of improving performance Memoize is used with the edit_distance function. While the code is now more efficient it really doesn’t have much effect on execution time for these short test strings. However, the code is now ready to handle much more significant sized strings.

References

Memoization

Levenshtein distance