This is my response to the Perl Weekly Challenge #096.
$S.
Input: $S = "The Weekly Challenge"
Output: "Challenge Weekly The"
Input: $S = " Perl and Raku are part of the same family "
Output: "family same the of part are Raku and Perl"
#! /usr/bin/env raku
unit sub MAIN ($S);
say '"' ~ $S.words.reverse.join(" ") ~ '"';
This is easy. We start with the string (in $S), split it to an array of
"words" (with words, which splits on space(s)), reverse that array
(with reverse) to get the words in (you guessed it) reverse order.
And finally, we join the words together to a single string (with join)
with a single space between them before printing that string - in quotes.
Running it:
$ ./reverse-words "The Weekly Challenge"
"Challenge Weekly The"
$ ./reverse-words " Perl and Raku are part of the same family "
"family same the of part are Raku and Perl"
Looking good.
We can have a go at a one liner:
File: reverse-words-oneliner
#! /usr/bin/env raku
unit sub MAIN ($S where $S.words.reverse.join(" ").map({ '"' ~ $_ ~ '"' }).join.say);
I had to use map to ensure a single value (the string
with quotes). The second join is there to get rid of the resulting array
(with one element), as printing an array gives a pair of parens.
Running it:
$ ./reverse-words-oneliner "The Weekly Challenge"
"Challenge Weekly The"
"Challenge Weekly The"
It would seem that the where
clause is executed twice (as we get the modified string printed twice).
Looking at the documentation (always a good idea, if all else fails...) at docs.raku.org/type/Signature#index-entry-where_clausedoes indeed tell us that this is the case: «type constraints are enforced at two different levels: the first level checks if it belongs to the type in which the subset is based (…) Once that filter is cleared, the constraint that defined the subset is checked.».
Conclusion: Using a where clause with side effects is not a good
idea.
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
my $N = $ARGV[0] // die "Specify a string";
say '"', join(" ", reverse(split(/\s+/, $N))), '"';
[1] Perl does not have words, but split on
whitespace(s) is the same thing.
Running it gives the same result as the Raku version:
$ ./reverse-words-perl "The Weekly Challenge"
"Challenge Weekly The"
$ ./reverse-words-perl " Perl and Raku are part of the same family "
"family same the of part are Raku and Perl "
$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.
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
Input: $S1 = "sunday"; $S2 = "monday"
Output: 2
Operation 1: replace 's' with 'm'
Operation 2: replace 'u' with 'o'
The «Types of edit distance» section of the Wikipedia page tells us that we have to use the Levenshtein distance, as that is ine only type that supports all of deletion, insertion and substitution, and nothing more. The end of the article shows the Wagner–Fischer algorithm in pseudocode. I have translated that algorithm to Raku:
File: edit-distance
#! /usr/bin/env raku
sub MAIN ($S1, $S2)
{
say wagner-fischer($S1, $S2);
}
sub wagner-fischer (Str $s, Str $t)
{
my $m = $s.chars;
my $n = $t.chars;
my @s = " $s".comb;
my @t = " $t".comb;
my @d;
for 1 .. $m -> $i
{
@d[$i][0] = $i;
for 1 .. $n -> $j
{
@d[$i][$j] = 0; # [1]
}
}
for 0 .. $n -> $j
{
@d[0][$j] = $j;
}
for 1 .. $m -> $i
{
for 1 .. $n -> $j
{
my $cost = @s[$i] eq @t[$j]
?? 0
!! 1;
@d[$i][$j] = min( @d[$i-1][$j] +1, # Deletion
@d[$i][$j-1] +1, # Insertion
@d[$i-1][$j-1] +$cost); # Deletion
}
}
return @d[$m][$n];
}
[1] It is a straigh forward translation, except that I have placed the «set each element in d to zero» part inside the first for loop from the pseudocode to save myself a loop.
Running it:
$ ./edit-distance kitten sitting
3
$ ./edit-distance sunday monday
2
Looking good.
The reverse transformations give the same number of operations:
$ ./edit-distance monday sunday
2
$ ./edit-distance sitting kitten
3
#! /usr/bin/env perl
use strict;
use warnings;
use List::Util 'min';
use feature 'say';
use feature 'signatures';
no warnings qw(experimental::signatures);
my $S1 = shift(@ARGV) // die 'Please specify $S1 and $S2';
my $S2 = shift(@ARGV) // die 'Please specify $S2';
say wagner_fischer($S1, $S2);
sub wagner_fischer ($s, $t)
{
my $m = length $s;
my $n = length $t;
my @s = ( "", split("", $s) );
my @t = ( "", split("", $t) );
my @d;
for my $i (1 .. $m)
{
$d[$i][0] = $i;
for my $j (1 .. $n)
{
$d[$i][$j] = 0;
}
}
for my $j (0 .. $n)
{
$d[0][$j] = $j;
}
for my $i (1 .. $m)
{
for my $j (1 .. $n)
{
my $cost = $s[$i] eq $t[$j]
? 0
: 1;
$d[$i][$j] = min( $d[$i-1][$j] +1, # Deletion
$d[$i][$j-1] +1, # Insertion
$d[$i-1][$j-1] +$cost); # Deletion
}
}
return $d[$m][$n];
}
Running it gives the same result as the Raku version:
$ ./edit-distance-perl kitten sitting
3
$ ./edit-distance-perl sunday monday
2
And that's it.