RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved reversing words in a string and calculating Levenshtein distance. (Note that this is open until 24 January 2021.)

TASK #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.

In Perl, this reduces trivially to "do you know how the split function works", a bit like the tr test back in #90.

sub rw {
  my $n=shift;
  return join(' ',reverse split ' ',$n);
}

In other languages it gets a little more interesting. Raku lets me put things in a sensible order:

  return $n.comb(/\S+/).reverse.join(' ');

Python makes me separate them:

def rw(n):
    t=n.split()
    t.reverse()
    return ' '.join(t)

Ruby lets me keep them in order:

  return n.split(' ').reverse.join(' ')

And Rust is… the only one of these languages that doesn't special-case split with a single space parameter to elide multiple spaces. Hey ho. But at least I have a grep-equivalent. I have to reverse in place as I do with Python.

fn rw(n: &str) -> String {
    let mut nr: Vec<&str>=n.split(' ').filter(|x| x.len()>0).collect();
    nr.reverse();
    let k=nr.join(" ");
    return k;
}

TASK #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.

So this is Levenshtein distance (I do not think I have ever, in my computing career, had an actual use for this as distinct from the simpler "how many characters differ"), and therefore I shall stand on the feet of giants and implement Wagner-Fischer. There are lots of ways of making this less demanding of time and storage, which I do not use here. Here's the Raku version; they pretty much all look the same.

sub ed($s,$t) {
  my @ss=(0,$s.comb).flat;
  my @tt=(0,$t.comb).flat;
  my @d;
  for 0..@ss.end {
    push @d,[(0) xx (@tt.elems)];
  }
  map {@d[$_][0]=$_}, 1..@ss.end;
  map {@d[0][$_]=$_}, 1..@tt.end;
  for 1..@tt.end -> $j {
    for 1..@ss.end -> $i {
      my $sc=0;
      if (@ss[$i] ne @tt[$j]) {
        $sc=1;
      }
      @d[$i][$j]=min(
        @d[$i-1][$j]+1,
        @d[$i][$j-1]+1,
        @d[$i-1][$j-1]+$sc,
          );
    }
  }
  return @d[@ss.end][@tt.end];
}

(Except that, I find, Rust does have a built-in min function… but it takes only two parameters, or an iterator, not an arbitrary list of things. Feels wrong to turn this list into an iterator…)

            d[i][j]=min(
                d[i-1][j]+1,
                min(
                    d[i][j-1]+1,
                    d[i-1][j-1]+sc
                )
            );

Full code on github.